How does "solving" a game like connect four or tic-tac-toe work?

Question

To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all the possible combinations).

If I were to try every possible move for some game I would get a tree of all the moves and each branch of that tree would represent a single game and each node on a branch would represent a move.

The last node of each branch is the finished game. Some will be ties, some will be won and some lost. Now the question is how am I supposed to create a winning strategy from that tree? It basically boils down to: if you know every possible position for a game, how would you go about winning?

It sounds like a trivial question when you say it out loud (and maybe it is), but it just doesn't click for me. Any insights are appreciated.

Answer 1

In short, minimax is what you're looking for.

We say that a game is valued $1$ if player 1 wins, $-1$ if player 2 wins and $0$ if it's a tie.

You have your brute-forced game tree. At each level you check who's turn it is. If it's player 1's turn, he/she will try to maximize the outcome. If it's player 2's turn he/she will try to minimize the outcome.

So you apply that. Literally. At each node you take the maximum or minimum of the child nodes and assign it to that node, depending on the depth at which you're looking (AKA who's turn it is). Then the value of the root node is the outcome of the game with perfect play.

Answer 2

For simple games, you use the following strategy:

You check whether a game position is won, lost, drawn, or not decided yet. In the first three cases, the position has a value of +1, -1, or 0. In the latter case, you try out all your possible moves, calculate the value of every move recursively, and the value of the position is the value created by your best move, and the move that you make is one that created the highest value.

Obviously when you try a move and do the recursion, you have to do the calculation for the other player, who will judge a position exactly in the opposite way that you do.

That's the easy part. There are optimisations (like if your first move is a winner, you don't have to check the other moves. If your first move is a draw, then you don't need to completely evaluate the other moves, just far enough to prove or disprove that they are winning moves. If you can encounter the same position in different ways, then you store the value of a position instead of computing it again. ).

Most games are too complex for this, so you assign real values between +1 and -1, where positive values are positions that are more likely to win, and negative values are positions that are more likely to lose, and optimise the value, calculating not to the end of the game but only as far as you can.

Answer 3

Someone should mention the term "backward induction" here. The idea of backward induction is to start at the leaves of the game tree (when an end condition is reached) and label each Win, Lose, Draw for player 1 according to the rules of the game. Now work backward, looking at nodes whose children have all been labeled. The player who moves at that node will pick an optimal decision, i.e. a move leading to a child labeled a win for them, or draw if none are available. So label this node with the appropriate outcome. Repeat until reaching the root, which will be labeled as a draw or a win for one of the players. We will have also computed, for each node in the tree, an optimal move for the corresponding player.