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.