Digital Logic Help (Mastermind)

Discussion in 'Homework Help' started by Gourbot3000, Jun 10, 2012.

  1. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Hello everyone!! I'm new to this forum and this is my first post. So I beg your pardon for any wrong I may commit.

    I have a project for school where we are required to recreate the game Mastermind using AND, OR, and NOT gates (Only NAND gates for extra credit). Here is the information from the project:

    "Our game will only involve two "colors", (0 or 1) and we will focus only on determining whether the color and positions of those pins are
    correct. We will be using digital logic circuits to build the portion of this game which gives the guessing player feedback about his/her guess. In digital logic a "true" value is represented by the number 1 and a "false" value by the number 0.

    Your game should use a 5 binary digit code. You should be able to display:
     -Output pins showing whether the "color" is correct at each position.
     -An output pin showing whether the entire code is correct."



    I'm really just asking if anyone would be able to help me get started or pointed in the right direction because I don't know where or how to begin. I would be extremely grateful. Thank You!
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Greetings and welcome.

    First, let's make sure that you understand what it is you are trying to do. That is very often the place where most mistakes are mede (both in class and in the real world).

    At this point, let's not risk confusion resulting from using '0' and '1' to mean different things in different places. So let's call our colors 'B' and 'R' (like checker pieces).

    The "mastermind" will first select a sequence of colors that is unknown to the player. Let's call this sequenc 'K'. For example, we might have:

    K = BRRB

    The player then makes a string, G, that is their guess. Perhaps this was:

    G = BBBR

    Your job is to create circuits that will tell the positions they have guessed a correct color plus an additional output that will tell them if the entire code is correct.

    So, with this in mind, let 'F' be the feedback string and use the letter 'T' if the guess is correct and 'F' if it is not. Call another output 'D' (for Done) that is 'T' if the entire code matches the target code and 'F' otherwise.

    Q1) What should F and D be for the example given?

    Q2) Given F, is it possible to determine D without knowing anything about K or G? If so, how? If not, what other information is needed?

    Q3) What information is needed to determine, say, the third element of F?

    Answer these questions and then we can take it further from there.

    Note that, aside from the reduced number of colors, this 'game' differs from the real one in a fundamental way. In the real one, the feedback is the number of colors that are in the right position and the number of colors that are correct but in the wrong position. Knowledge about which positions fall into which category is not given. That important because, with the rules of this game, if you understand the logic then you are guaranteed to have the solution by the second guess. Now, that's perfectly fine since the goal here isn't to faithfully recreate the game, but rather to learn something about logic circuits. My point is just be careful to avoid letting any familiarity you have with the real game make you misinterpret the rules of this game, which is the game that counts.
     
    Last edited: Jun 11, 2012
  3. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Thank You for helping me out here.

    So for question 1, since F is the feedback for each color and position, would it give a true or false for each color and spot based on K? So if K is BRRB and I guess BBBR then it would give me back TFFF for position? Then D would only be a T if everything in the end is correct.

    For question 2, the player would be able to determine D without knowing K because of the outputted T or F from F. Or would we still need to know more?

    For question 3, i'm not sure what you mean by "the third element of F"

    Also, in your opinion, does this game require just a sequence of two guesses or the normal sequence of four guesses just with two colors?
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Yes. Sorry if I confused you with some 'W's instead of 'R's. I've fixed that. I wanted to use 'R' for 'Right' in the F string, so chaged 'R' to 'W', only, of course, to find out that I then wanted to use 'W' for 'Wrong'. So I changed back and used 'T' and 'F' instead but didn't get everything cleaned up. Fortunately it appears that you got the idea just fine.

    Correct. In fact, they not only don't need to know K, they don't need to know anything about G, either.

    You have four pins that make up K (and four more that make up each pattern, G). In

    K = BBRB

    the third pin is 'R'. This is what I meant by third element. The term 'element' is just a generic term for a member of a sequence. Here, each element is one of the pins but, importantly, a particular pin that takes into account its order in the pattern.

    I should have been more specific. Each instance of G is a single, separate "guess". That guess is composed of four, let's call them subguesses. We could also call G a "pattern" made of up four "guesses". I like that better (and have updated the above text in this post accordingly). So, in those terms, my claims is that you are guaranteed to be able to guess the correct pattern with, at most, two patterns.
     
  5. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Alright so thanks to your help I think I understand the overall concept behind this "game" but I'm not sure how to put it together. I would guess that this circuit would use mostly AND gates as a way to make sure the guess (G) is correct but how would it be compared to the sequence (K)?

    If B=0 and R=1 and K=BRRB and G=BBBR, how would they be fed together to get a true? If the first element of K and G are both 1(B) then an AND gate would seem to work but what if they are both 0(R)?

    Also, how would the Feedback be achieved for elements 2-4 if they are wrong?

    This is the main part that confuses me.
     
  6. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Q4) Let's pick the last (fourth) pin. I tell you that the fourth pin in K is 'R' and the fourth pin in G is 'R', do you have enough information to determine any of the pins (outputs) in F? If so, which one(s)? If not, what other information do you need to determine the output for at least one position in F?

    Q5) If you have enough information in Q4, then you are making that determination based on two inputs, the fourth position in K and the fourth position in G. How many possible combinations are there for these two inputs? Can you make a truth table showing what the output that you identified is discernable in Q3 for each of these combinations?

    Q6) What logic function does the truth table in the answer to Q5 match?
     
  7. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Q4: If both K and G show R then the output for the fourth element of F would be T.

    Q5: Possible combinations in a truth table for any of the pins would be:

    BB which would be T (since they match)
    BR which would be F (since they don't match)
    RB (F)
    RR (T)

    Q6: The logic gate seems to be some sort of XNOR gate. Or would it be possible with OR gates?
     
  8. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    You are correct in everything except that there is no way to make an XNOR gate out of just OR gates. It is ALWAYS possible to do it with just NOR gates or with just NAND gates.

    The XNOR gate is also known as the EQ gate (equality gate). Can you see why?

    Q7) Given what you have accomplished so far, can you see how to implement the complete logic for F?

    Q8) Given what you have accomplished so far, can you see how to implement the complete logic for D?

    Q9) Do you know how to replace the logic gates used in Q7 and Q9 with just NAND gates?
     
  9. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Q7: If K= BRRB and G= BBBR

    Then F would be TFFF (like mentioned earlier). I'm not sure where else to go from here. F would be a T or F based on the results of G compared to K but I don't know how to use any gates to accomplish a system that would not only give a T if everything matches but also checks itself and gives back Feedback.

    Q8: D seems like it would be completely determined on the final results of F and would simply be a T/F if G matches K.

    Q9: As stated above, I still am not sure how to construct this so I am not sure how to do it using NAND gates.
     
  10. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Look at your answers to Q4, Q5, and Q6. What you have basically said there is that, to get the value for the fourth position in F, all you need to do is pass the fourth value in K and the fourth value in G to an XNOR gate. Correct?

    Q10) So, if that is what you do for the fourth position in F, what would you do for the first position? For the second? For the third?

    Q11) Now, forgeting about K and G entirely, what must the four outputs that make up F be in order for D to be true. In other words, what is the one pattern for F that means K and G match entirely.

    Q12) Using only the four signals that make up F, what is the logic that yields D?
     
  11. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    "Look at your answers to Q4, Q5, and Q6. What you have basically said there is that, to get the value for the fourth position in F, all you need to do is pass the fourth value in K and the fourth value in G to an XNOR gate. Correct?"

    Is there a way to do this without using XNOR gates?

    Q10) So if that is what you do for the fourth position you would just repeat it for all the other three positions.

    Q11 and 12) The one pattern for F that would make D true is TTTT. That would be returned if K and G match. I'm guessing you could have all four values fed into an AND gate with the output D.
     
  12. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Good job.

    As for using something other than an XNOR, sure. Remember, you can implement ANY logic function using only NAND gates (or only NOR gates), so right there you know there are at least two other ways.

    Take a look at the truth table you are trying to implement:

    A B Y
    0 0 1
    0 1 0
    1 0 0
    1 1 1


    In words, saying that the output should be True if the two inputs are equal is actually a fairly abstract description of the table, albeit one that humans are well equipped to grasp with little thought or difficulty. But we can describe it in at a much lower, more literal level that, while not nearly as intuitive for a human, makes the low-level logic much more apparent.

    We want the output to be true if either A is not true and B is not true or if A is true and B is true .

    Now let's put some parenthesis in there and highlight the logical operators.

    We want the output to be true if either [(A is NOT true ) AND (B is NOT true )] OR if [A is true AND B is true ].

    Does that give you any ideas?
     
  13. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    So would the equation be something like this?

    F= (A'*B') + (A*B)

    Where *= an AND gate, += an OR gate

    On a side note, I talked to a teaching assistant about this for extra feedback and he mentioned that one of the ways to do it would be having X be Player 1 and Y be Player 2. Each would have 5 inputs (or guesses) which would give us K and G. All of those would be ANDed together to give us D. Most of that we've already determined thanks to your help.
     
  14. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    Yes. This is the defining Boolean expression for an XNOR gate. Similarly, the defining Boolean expression for a, XOR gate is

    Y = (A'*B)+(A*B')

    One thing that you should do, and keep it handy as a reference until you really understand the material and can easily generate what you need on the fly, is make a diagram showing all the one input and all of the symmetric (meaning you can swap the inputs and nothing has changed) two input gates:

    1 input:
    BUF (buffer)
    INV (inverter)

    2 input:
    AND
    OR
    NAND
    NOR
    XOR
    XNOR

    Besides having the Boolean expression, circuit symbol, and truth table for each gate, also put the NAND-only and NOR-only implementations. For some of them, you might have more than one such implementation and you might include an implementation using other gates is well.
     
  15. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    What is a Buffer and is an Inverter just another name for a NOT gate?

    Also, for the purpose of this "game" is it really as simple as using 5 constructed XNOR gates that are ANDed together at the end to give us D?
     
  16. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    It's a gate that simply echoes on its output whatever is on its input. From a logic standpoint it is essentially not there. For real circuits, buffers server real purposes. But even from a pure academic standpoint, it is important to understand the concept.

    Yes. In practice, the term "inverter" is probably a lot more common than "NOT gate".

    Pretty much, except there are only FOUR outputs that correspond to whether individual positions are correct. The FIFTH output IS the D output.
     
  17. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    Alright so I ANDed the multiple F= (A'*B') + (A*B) equations together and it seems to be working. That seems to satisfy the requirements of the project. I need to experiment with the NAND gates to see how I can recreate it with those.

    Again, I really appreciate all of your help!
     
  18. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    No problem. All I really did was explain a few concepts and ask a bunch of questions. You answered my questions and, in doing so, figured out the answer to your assignment yourself.
     
  19. Gourbot3000

    Thread Starter New Member

    Jun 10, 2012
    10
    0
    That was probably the best way to help. Thank You
     
  20. WBahn

    Moderator

    Mar 31, 2012
    17,750
    4,797
    In general I believe it is. It is known as the Socratic Method and has been around a few thousand years. If both parties are willing to struggle through it, it works wonders. But if one party isn't, either the teacher gets frustrated at perhaps having to revisit the same questions repeatedly or, more commonly, the student gets frustrated because they just want to be told the answer or the next step or whatever, then it breaks down pretty badly.
     
Loading...