Calculate the probability of winning for a selected tic-tac-toe player

Question

I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.

I want to calculate the probability of winning for a selected tic-tac-toe player. I have a directed graph of the game, where the vertices of the graph are game positions, directed edges are a moves from one player to another. And I have information associated with each vertex of the graph, we could call it statistic. That is data about how many numbers of moves are required for players to win or draw.

By example, we have 'A' vertex and player '#1' decides what move is better for him/her - transition to 'B' vertex or to 'C' vertex. And 'B' vertex has next statistic:

In 3 moves: player '#2' has 51 winning positions.

In 4 moves (*condition): player '#1' has 538 winning positions.

In 5 moves (*condition): player '#2' has 443 winning positions.

In 6 moves (*condition): player '#1' has 584 winning positions and 453 draw positions.

*condition - if the game is not finished.

'C' vertex contains different data, but it is required to calculate the best variant for player '#1'.

I am not sure that it is the task of the theory of probability, perhaps it is the task of optimization. In any case, I will be glad to any advice or tips on how to solve this problem.

Answer 1

The formulation of the question is very unclear, so I'll make some guesses about what was meant. First, I assume that all vertices have the same sort of data available, namely how many winning positions (not how many sequences of moves leading to those positions) there are for one or the other player after any number of subsequent moves. (In particular, the statement "'C' vertex contains different data" means only that the numbers are different for C, not that a different sort of information is given there.) Second, I'll assume that the *condition "if the game is not finished" means merely that the indicated number of moves should make sense. (I'll comment below on the alternative interpretation that, at a vertex corresponding to a finished game, we are not told who won.) Third, I'll assume that the absence of that *condition in the "3 moves" line of the example is not significant, mainly because I can't think of anything general to infer from that absence.

With all these assumptions, I'd find optimal moves for Player 1 by the following standard method for analyzing game trees. First, discard the information at most of the vertices; keep only the information at the leaves of the tree, telling who won the finished plays. Second, work backward from the leaves toward the root, labeling each vertex with the following information: Who has a winning strategy from that vertex? How many moves will it take to win (against the opponent's best delaying strategy)? If the player who has the winning strategy from this vertex is the one who is to move, then what is the first move of that strategy? It is easy to assemble all this information for a vertex given the corresponding information for all its children, so we can work backward from the leaves and fill in the information throughout the game tree. (Note that there is nothing probabilistic about the solution, or, for that matter, about the problem.)

In the (intuitively very strange) case that the *condition was intended to say that we don't know who wins at which terminal position, then, in general, there is not enough information to design an optimal (or even a reasonable) strategy. Perhaps in this situation, probability can become relevant if we assume that the opponent also doesn't know the winning conditions of the game and therefore uses some mixed strategy. In that case, the theory of equilibrium mixed strategies might be relevant, but I think this interpretation of the question is too improbable to be worth any more comment.