Make the computer never lose at Tic-Tac-Toe

Question

I am working on a simple game of Tic Tac Toe code for C. I have most of the code finished, but I want the AI to never lose.

I have read about the minimax algorithm, but I don't understand it. How do I use this algorithm to enable the computer to either Win or Draw but never lose?

Answer 1

The way to approach this sort of problem is one of exploring possible futures. Usually (for a chess or drafts AI) you'd consider futures a certain number of moves ahead but because tic tac toe games are so short, you can explore to the end of the game.

Conceptual implementation

So you create a branching structure:

• The AI imagines itself making every legal move
• The AI them imagines the user making each legal move they can make after each of its legal move
• Then the AI imagines each of its next legal moves
• etc.

Then, going from the most branched end (the furthest forward in time) the player whose turn it is (AI or user) chooses which future is best for it (win, lose or draw) at each branching point. Then it hands over to the player higher up the tree (closer to the present); each time choosing the best future for the player whose imaginary turn it is until finally you're at the first branching point where the AI can see futures which play out towards it losing, drawing and winning. It chooses a future where it wins (or if unavailable draws).

Actual implementation

Note that conceptually this is what is happening but it's not necessary to create the whole tree, then judge it like this. You can just as easily work though the tree getting to the furthest points in time and choosing then.

Here, this approach works nicely with a recursive function. Each level of the function polls all its branches; passing the possible future to them and returns -1,0,+1; choosing the best score for the current player at each point. The top level chooses the move without actually knowing how each future pans out, just how well they pan out.

Pseudo code

I assume in this pseudo code that +1 is AI winning, 0 is drawing, -1 is user losing

determineNextMove(currentStateOfBoard)
    currentBestMove= null
    currentBestScore= - veryLargeNumber

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI’sMove)
        if score>currentBestScore
            currentBestMove=legalMove
            currentBestScore=score
        end
    end

    make currentBestMove

end

getFutureScoreOfMove(stateOfBoard, playersTurn)

    if no LegalMoves
       return 1 if AI wins, 0 if draw, -1 if user wins
    end


    if playersTurn=AI’sTurn
        currentBestScore= - veryLargeNumber //this is the worst case for AI
    else
        currentBestScore= + veryLargeNumber //this is the worst case for Player
    end

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn)
        if playersTurn ==AI’sTurn AND score>currentBestScore //AI wants positive score
           currentBestScore=score
        end
        if playersTurn ==Users’sTurn AND score<currentBestScore //user wants negative score
           currentBestScore=score
        end

     end

     return currentBestScore
end

This pseudo code doesn't care what the starting board is (you call this function every AI move with the current board) and doesn't return what path the future will take (we can't know if the user will play optimally so this information is useless), but it will always choose the move that goes towards the optimum future for the AI.

Considerations for larger problems

In this case where you explore to the end of the game, it is obvious which the best possible future is (win, lose or draw), but if you're only going (for example) five moves into the future, you'd have to find some way of determining that; in chess or drafts piece score is the easiest way to do this with piece position being a useful enhancement.

Answer 2

I have been doing such a thing about 5 years ago. I've made a research. In tic tac toe it doesn't take long, you just need to prepare patterns for first two or three moves.

You need to check how to play:

1. Computer starts first.
2. Player starts first.

There are 9 different start positions:

But actually just 3 of them are different (others are rotated). So after that you will see what should be done after some specific moves, I think you don't need any algorithms in this case because tic tac toe ending is determining by first moves. So in this case you will need a few if-else or switch statements and random generator.

Answer 3

tic tac toe belong to group of games, which won't be lost if you know how to play, so for such a games you do not need to use trees and modified sorting algorithms. To write such algorithm you need just a few functions:

1. CanIWin() to check if computer has 2 in a row and possible to win.
2. ShouldIBlock() to check if player do not have 2 in a row and need to block it.

Those two functions must be called in this order, if it returns true you need either to win or not to let player win.

After that you need to do other calculations for move.

One exclusive situation is when computer starts the game. You need to chose cell which belongs to the biggest amount of different directions (there are 8 of them - 3 horizontal, vertical and 2 diagonal). In such a algorithm computer will always choose center because it has 4 directions, you should add small possibility to choose second best option to make game a bit more attractive.

So when you reach situation where are some chosen parts of the board and computer have to move you need to rate every free cell. (If first or second function returned true you have to take an action before reaching this place!!!). So to rate cell you need to count how many open directions left on every cell, also you need to block at least one opponent direction.

After that you will have a few possible cells to put your mark. So you need to check for necessary moves sequence, because you will have a few options and it may be that one of them lead you into loosing. So after that you will have set and you can randomly choose move, or to choose the one with biggest score.

I have to say similar thing, as said at the beginning of post. Bigger games do not have perfect strategy and, lets say chess are much based on patterns, but also on forward thinking strategy (for such a thing is using patricia trie). So to sum up you do not need difficult algorithms, just a few functions to count how much you gain and opponent loses with move.

Answer 4

Make a subsidiary program to predict the cases with which the user can win. Then you can say your ai to do the things that the user has to do to win.