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

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.

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.

StackExchange Computer Science Q#93421, answer score: 5