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?

Sismondi

did you try any code? just make sure that in minimax algorithm computer always choose best strategy. – Byword

Please show the code you have tried. We are not here to do your homework! – Canter

If you would rather write the algorithm yourself, you may find xkcd.com/832 to be of use. Used a variation of that chart for a Reversi game. – Kyne

@Doc Wow, that is nice, I'll try making it into code – Sismondi

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.

Delldella

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.

Sheath

While a "script" is certainly possible its a little ugly and will actually be huge to cope with the player doing demostrably stupid moves. The optimum game is entirely determined by starting position. But the user isnt obliged to play optimumly – Delldella

@RichardTingle I've been doing that and remember that user stupid moves was handling with default in switch. – Sheath

@user2623967 So the minimax algorithm can be prevented? If so, that is great because I'm having a hard time understanding it – Sismondi

@RichardTingle What do you mean by a 'script' – Sismondi

@C_Beginner_Learner Probably in all cases difficult algorithms can be prevented, but in some other situations it is better to use algorithm. If you need just tic tac toe so you can do without any detecting algorithm, if it is just a first step to something bigger you will need that anyway, so you better try to understand that. – Sheath

@C_Beginner_Learner By script I mean the programmer in advance saying "if the user does this do this" approach. This could work for a tic tac toe game but would never work for a drafts or chess AI. Is this a school assignment? If so a script based approach will probably be the "lowest passing grade" – Delldella

@C_Beginner_Learner If you learning C++ it is nothing bad to use my option, but if you trying to learn some algorithms it is better not to use patterns. – Sheath

Answer 3

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.

Pinnule

Answer 4

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.

Sheath

I know this sounds simpler than a minimax solution but it probably isnt, you end up with loads of rules for particular situations (you teach the computer how to play). A rule you haven't considered is what to do when theres no blocking needed and you dont have 2 in a row. Choosing ramdomly will not be anywhere near optimum. A computer can blast through the few thousand futures in no time and is guaranteed to play optimumlly. With minimax you dont need to teach the computer strategy; only what a legal move is and what a "good" final state is – Delldella