Making the Computer Play Strategically

PG: Long and hard.

MF: Project still needs to be wrapped up and updated online

On this page, you'll implement the Tic-Tac-Toe strategy rules to make the computer play strategically.

You'll set up a next move for computer block so you can broadcast to all the clones the position where the computer will move. As before, only the clone with the matching position number will make the move.

The code for next move for computer will implement the three strategy rules:

You will build the next move for computer block using two new blocks: can win now? and winning square, which aren't written yet. To start building next move for computer, you'll make the other two blocks, but they won't really do anything. They'll just be for setting up the code for next move for computer, and you'll make them do what they're meant to later.
  1. If it isn't open already, open your U5-TicTacToe project.
  2. Create these two new blocks for implementing the strategy rules. For now, make can win now? report false no matter what. Don't put code inside winning square yet.
    can player () win now? winning square for player
    Why make can win now? report false? That way, the computer will skip rules 1 and 2 and just default to the final rule, and so you can continue using your program as you build and test these two new blocks.
  3. Now, create the next move for computer block that implements the strategy rules using these two new blocks, and use it as the input to broadcast instead of best empty square.
    4. Click for a hint about implementing the strategy rules.
  4. Play a game against the computer, and make sure that your game still works.

You can check status of all winning triples for a triple that will allow the computer player to win on the next turn, but you will not be able to tell the position of the square where that player will move. To make that possible, you will need to initialize the spaces in the board variable with the numbers 1 to 9 instead of nine copies of the word "Empty." Then winning square for player can select the position number out of the winning triple.

  1. Change the initialization instruction for the board variable to a list of the numbers from 1 to 9.
    You can type the numbers out by hand or just use numbers from () to ().
  2. Debugging. Play a game. Identify the parts of your code that cause the problems, and come up with a solution.

    Click for a hint about how to fix the errors.

    is () a number?

Now you'll begin working on the winning square for player and can player () win now? blocks. The can win now? block can just check if there is a winning square by checking the results of winning square, so you'll code winning square first.

You'll begin by building a winning triple for player block to identify the contents of the three squares on the board where the player could win on their next turn. Then, winning square will select the correct position out of that triple.
winning triple for player reporting {3, O, O} winning square for player O reporting 3

  1. Talk with Your Partner How could you use one or more of the blocks that you have to determine if a player can win on their next turn?
    board possible winning triples status of all winning triples won? (X)
    You don't have to program it yet. Just talk about what you could do.
  2. Create a winning triple for player () block. It should report the first triple it finds that contains a place where the player could win.
    You may find it helpful to invent these blocks:
    opponent to (O) reporting X number of (X) in (list{X,5,X}) reporting 2

    Click here for a hint about winning triple.

    item (1) of (keep items such that ('The code is missing. Plain text says: You build the predicate.') from (status of all winning triples))

    You learned about using keep with predicates in Unit 2 Lab 3 Page 5: Keeping Items from a List.

    Click here for another hint about winning triple.

    The player must appear twice in the triple, but the opponent must not appear at all.
  3. Play part of a game, and then test winning triple for both inputs (X and O). Play a little more, and then test them both again. Fix any bugs.
  4. What does winning triple report if there is no winning triple?
  5. Now write the code inside the winning square for player () block. Make sure it works even if there is no winning square.
    6. Click for a hint about winning square.
    is () a number? is () a list?
  6. Play part of a game, test winning square for both players, and fix any bugs.
  7. Implement can player () win now? using your winning square block.
  8. Play several games against the program. Fix any bugs. Make sure computer is using three rules.
  1. Modify the program so that the computer can play either X or O. When the game starts, ask the human player to choose X or O.
  2. Create a way for the player to decide whether they want to play against another human or against the computer.
  1. Play against the computer, and find a strategy that lets you win the game. (This isn't trivial; just the computer rules you already have are pretty good.)
  2. Program more rules to make the computer a better player. This will involve looking more than one move ahead. There are various ways to do it, and what follows is just one suggestion.
    1. It's not good enough just to look for a winning move for yourself two moves from now. If you can see such a move, so can your opponent, who'll move to block you. So what you have to find is a fork: two triples in which you have one appearance and your opponent has none, and which have a free square in common. This is much easier to see with a picture:
      board with fork
      Player X opened the game with the standard opening move, in the center. Player O responded poorly, on the top edge, and is therefore about to lose the game. Player X played in the top left corner. Player O had to respond in the bottom right corner in order to block an immediate win for player X. It's player X's turn. There is no winning combination with two Xs, nor with two Os. But player X can find two winning combinations, the ones marked with the red lines, both of which have one X and two free squares, with one of the free squares in common. In the picture, the common square is 4, the left edge square, and so that's where Player X should move.
    2. Find all the triples (that is, report a list of triples) in which the computer has one square and the other two are empty, and store then in a variable called singles.
    3. Make one big list of all the letters and numbers from the triples:
      script variable(atoms); set (atoms) to (combine with(append()()) items of (singles))
      You don't have the append block in your palette, but it's in one of the Snap! libraries. Click on the file menu icon, and choose "Libraries...", then choose "List utilities" from the menu that appears.
      4. "Atom" is a technical term for a value that isn't a list. A list contains a bunch of items, just as a molecule contains a bunch of atoms.
    4. Now find a number that appears more than once in atoms.
      5. Need to update page number. --MF, 3/29/19
      You wrote a duplicates in block in Unit 5 Lab 1 Page 7: List Processing Algorithms.