Hey I am obviously new here, but would love to get better at programming. I currently am using Michael Dawson's "Python Programming, Second Edition (for the absolute beginner)" to try and learn it. Anyway he gives code on how to make a very basic tic-tac-toe game inside the cmd prompt window. As a challenge at the end of the chapter he says try to make an unbeatable computer, the one given just goes with what the typically best move would be, starting with middle then going to corners etc. I have spent 3+ hours trying to figure out how to make the computer do something specific based on a human move and cant figure it out. Now I realize this is kinda useless, but I do want to learn programming and don't want to move on in the book if I can't do something I should be able to. Please help me out, here is my current code for computer move.

    def computer_move(board, computer, human):
    """Make computer move."""
    # make a copy to work with since function will be changing list
    board = board[:]
    # the best positions to have, in order

    BEST_MOVES = (4, 0, 2, 6, 8, 1, 3, 5, 7) # [COLOR="Red"]Only part determining computer moves[/COLOR]

    print "I shall take square number"
    # if computer can win, take that move
    for move in legal_moves(board):
        board[move] = computer
        if winner(board) == computer:
            print move
            return move
        # done checkin this move, undo it
        board[move] = EMPTY
    # if human can win, block that move
    for move in legal_moves(board):
        board[move] = human
        if winner(board) == human:
            print move
            return move
        #done checking this move, undo it
        board[move] = EMPTY
    # since no one can win on next move, pick best open square
    for move in BEST_MOVES:
        if move in legal_moves(board):
            print move
        return move

Kk now here is entire code for program

# Tic-Tac-Toe
# Play the game of ttt against a computer opponent

# global constants
X = "X"
O = "O"
EMPTY = " "
TIE = "TIE"
NUM_SQUARES = 9

def display_instructions():
    """Display Game Instructions."""
    print \
    """
    Welcome to Tic-Tac-Toe.
    You will make a move by entering a number 0-8.
    The number will correspond to the one on this board.

                    0 | 1 | 2 
                   -----------
                    3 | 4 | 5
                   -----------
                    6 | 7 | 8
    """

def ask_yes_no(question):
    """Ask a yes or no question."""
    response = None
    while response not in ("y", "n"):
        response = raw_input(question).lower()
    return response

def ask_number(question, low, high):
    """Ask for a number within a range."""
    response = None
    while response not in range(low, high):
        response = int(raw_input(question))
    return response

def pieces():
    """Determine if player or computer goes first."""
    go_first = ask_yes_no("Would you like to go first? (y/n): ")
    if go_first == "y":
        print "\nAlright human goes first."
        human = X
        computer = O
    else:
        print "Computer will go first then."
        computer = X
        human = O
    return computer, human

def new_board():
    """Create new game board."""
    board = []
    for square in range(NUM_SQUARES):
        board.append(EMPTY)
    return board

def display_board(board):
    """Display game board on screen."""
    print "\n\t", board[0], "|", board[1], "|", board[2]
    print "\t", "---------"
    print "\t", board[3], "|", board[4], "|", board[5]
    print "\t", "---------"
    print "\t", board[6], "|", board[7], "|", board[8], "\n"

def legal_moves(board):
    """Create list of legal moves."""
    moves = []
    for square in range(NUM_SQUARES):
        if board[square] == EMPTY:
            moves.append(square)
    return moves

def winner(board):
    """Determine the game winner."""
    WAYS_TO_WIN = ((0, 1, 2),
                  (3, 4, 5),
                  (6, 7, 8),
                  (0, 3, 6),
                  (1, 4, 7),
                  (2, 5, 8),
                  (0, 4, 8),
                  (2, 4, 6))
    for row in WAYS_TO_WIN:
        if board[row[0]] == board[row[1]] == board[row[2]] != EMPTY:
            winner = board[row[0]]
            return winner
    if EMPTY not in board:
            return TIE
    return None

def human_move(board, human):
    """Get human move."""
    humanmoves = []
    legal = legal_moves(board)
    move = None
    while move not in legal:
        move = ask_number("Where will you move? (0 - 8): ", 0, NUM_SQUARES)
        if move not in legal:
            print "\nInvalid Move, That square is already occupied, Choose another. \n"
            humanmoves.append(move)
    print "Fine..."
    return move


def computer_move(board, computer, human):
    """Make computer move."""
    # make a copy to work with since function will be changing list
    board = board[:]
    # the best positions to have, in order

    BEST_MOVES = (4, 0, 2, 6, 8, 1, 3, 5, 7)

    print "I shall take square number"
    # if computer can win, take that move
    for move in legal_moves(board):
        board[move] = computer
        if winner(board) == computer:
            print move
            return move
        # done checkin this move, undo it
        board[move] = EMPTY
    # if human can win, block that move
    for move in legal_moves(board):
        board[move] = human
        if winner(board) == human:
            print move
            return move
        #done checking this move, undo it
        board[move] = EMPTY
    # since no one can win on next move, pick best open square
    for move in BEST_MOVES:
        if move in legal_moves(board):
            print move
            return move





def next_turn(turn):
    """Switch turns."""
    if turn == X:
        return O
    else:
        return X

def congrat_winner(the_winner, computer, human):
    """Congratulate the winner."""
    if the_winner != TIE:
        print the_winner, "won!\n"
    else:
        print "It's a tie!"
    if the_winner == computer:
        print "Ha you really think you could beat a computer?"
    elif the_winner == human:
        print "Bet you couldn't do it again!"
    elif the_winner == TIE:
        print "You were lucky, somehow you managed to not lose..."


def main():
    display_instructions()
    computer, human = pieces()
    turn = X
    board = new_board()
    display_board(board)

    while not winner(board):
        if turn == human:
            move = human_move(board, human)
            board[move] = human
        else:
            move = computer_move(board, computer, human)
            board[move] = computer
        display_board(board)
        turn = next_turn(turn)
    the_winner = winner(board)
    congrat_winner(the_winner, computer, human)

# start the program
main()


raw_input("Press the Enter Key to Exit.")

Thanks in advance for any help

Edited 3 Years Ago by Dani: Formatting fixed

don't hijack eggowaffles thread ramakrishnakota, if you need help and it's not related to this guy start a new thread

I didn't spend a lot of time on the code, but best move should be similiar to legal move. IMHO this should be implemented as a class. That would avoid the gobal variables and make the code cleaner. But you may not have gotten into creating classes yet. Also, the function main() is unnecessary. It is common to use "if __name__ == '__main__':" so that you can both test and reuse functions in the code, but in this case main() serves no purpose.

def legal_moves(board):
    """Create list of legal moves."""
    moves = []
    for square in range(NUM_SQUARES):
        if board[square] == EMPTY:
            moves.append(square)
    return moves
#
#
def best_move(board):
    for square in BEST_MOVES:     ##   BEST_MOVES will have to be global
        if board[square] == EMPTY:
            return square
    return -1

Thanks for the reply, I will try doing something like this. However I don't see how I could use this in having the computer make a specific move. Like right now if the human were to go board[0], the computer would take board[4], (which is fine), however if human was to take board[8] now computer would take board[2] because right now it just goes from middle then off to corners, and since board[0] is taken it takes board[2] causing the board to look like this.

x |   | 0 
                   ----------
                      | 0 |  
                   ----------
                      |   | x

Which obviously is not good because now human takes board[6] and wins 2 different ways. I would like to have the computer take like board[3] rather than board[2] so the human would have to take board[5] causing the board to look like this and leading to a tie.

x |   |  
                   ----------
                   0 | 0 | x
                   ----------
                     |   | x

So I would like to do something like if human controls board[0], board[8] and computer controls board[4] then computer takes board[3]. I just don't know how to implement this into code. Thanks again in advance for any help.

I was assuming that no one had two in a row. You first want to check for two in a row and if your opponent has it then block, if you have it, win the game. Taking a closer look at your code, it appears that the function computer_move() does just that, but I didn't test it. So I would say, at this point I don't understand what the problem is. Second, if you want to make the computer unbeatable, then you will have to store all losing games: (who started and the number of each move), and not do the same thing again. While you are at it, you could do the same for winning games and try to repeat. On second thought, you only have to keep track of winning games and try to make the same moves for yourself, and different moves if your opponent is on the same track as one of the winning games, which of course would supercede the best_move() function.

Yeah right now it will do that, the 2 in a row block or take the win thing. But see the problem is that right now a human can guarantee them selves a win by setting them selves up for a 2 way win as demonstrated above. See if they end up with board[0] and board[8] it is not 2 in a row however, they automatically win now by taking a corner because then they are set up to win 2 different ways. However if the computer were to go to board[3] during the time the human would have to take board[6] for the block and there by couldnt set them self up for the 2-way-win.

I see what you mean. You could of course test for that, but then there would be another set of moves that would always beat the computer. There is probably even a "101 ways to win at tic-tac-toe" book, and you would have to test for all 101 ways. I would guess that this is the point to start keeping track of winning games and losing games so eventually the computer would not make any mistakes. The tic-tac-toe entry on Wikipedia has a slightly different best move strategy. They call your current problem a "fork".

A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[4].

1. Win: complete three in a row.
2. Block: block their opponent from completing three in a row
3. Fork: threaten a win with two possible completions in two ways
4. Block Fork:

Option 1: create two in a row to force a block (Note: Sometimes, if one forces a block in this manner, the other player's block will result in a fork and a winning position, so care must be taken when there is more than one way to create two in a row. For example, if X has played the center and a corner, and o is in the opposite corner, o must play a corner and not an edge or else x will win).
Option 2: if there is a configuration where the opponent can fork, block that fork

5. Centre: play the centre
6. Opposite Corner: if the opponent is in the corner, play the opposite corner
7. Empty Corner: play an empty corner
8. Empty Side: play on an empty side

The first player, whom we shall designate "X," has 3 possible positions to mark during the first turn. Superficially, it might seem that there are 9 possible positions, corresponding to the 9 squares in the grid. However, by rotating the board, we will find that in the first turn, every corner mark is strategically equivalent to every other corner mark. The same is true of every edge mark. For strategy purposes, there are therefore only three possible first marks: corner, edge, or center. Player X can win or force a draw from any of these starting marks, however playing the corner gives the opponent the smallest choice of squares which must be played to avoid losing[5].

The second player, whom we shall designate "O," must respond to X's opening mark in such a way as to avoid the forced win. Player O must always respond to a corner opening with a center mark, and to a center opening with a corner mark. An edge opening must be answered either with a center mark, a corner mark next to the X, or an edge mark opposite the X. Any other responses will allow X to force the win. Once the opening is completed, O's task is to follow the above list of priorities in order to force the draw, or else to gain a win if X makes a weak play.

Hi,

It's not quite clear from the above whether you managed to implement the code that would make the computer unbeatable in this game. I am using the same book to learn programming and have just attempted this same challenge. I did the following...

In the line directly underneath BEST_MOVES (line 114 in the games code as displayed above), I created a new tuple that reads as follows: COUNTER_PUNCH = (3, 5).

I then entered the following code, sandwiched between the "if human can win..." block and the "since no-one can win" block:

# blocking winning tactic
if human == board[8] and human == board[0] or human == board[2] and human == board[6]:
for move in COUNTER_PUNCH:
if move in legal_moves(board):
print move
return move

This bit of code is designed to prevent the use of the tactic that you refer to above, that allows the human to win every time. So far I have not been able to win since adding this code, so I think I've completed this challenge, but if anyone can see a loophole (or a sleeker way of doing it) I'd be interested to hear about it.

Thanks,
Paul

I think one should always try to look at the date of the last post before replying to a thread no one is interested to read.
It is more than an year old.

Thanks for your kind response to my post.
I was aware that the email was over a year old, the reason I posted
was because it was unresolved - a question had been asked but no real solution had been put forward. It's quite possible that other people would be struggling with the same question (the book it comes from is pretty popular) so although none of the original contributors to this thread might find the answer useful, other people who are only just coming across this particular challenge may be pleased to find a complete thread which resolves the question.

The AI should do something like this :

1) Check if you can move if the middle
2) Check if you can win in 1 move
3) Check if player can win in 1 move
4) Check if opposite corners from user is available
5) Check if any move is available.

This article has been dead for over six months. Start a new discussion instead.