How does "solving" a game like connect four or tic-tac-toe work?
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.