4 ms·

Are you sure there is only one solution to the set of max/min equations? I've been trying to solve the probabilistic tic-tac-toe since it was published, and I b

Are you sure there is only one solution to the set of max/min equations? I've been trying to solve the probabilistic tic-tac-toe since it was published, and I believe there are actually multiple solutions here. In fact I'm not sure that given a board there exists a best solution. I.e. I suspect that for most boards and for most fixed strategies you can create a counter-strategy that outperforms the given strategy (but perhaps then loses to some other strategy). My code looks completely different, but I suspect you can uncover alternate solutions if you mess with the binary search. For example replace `x = (a + b) / 2` with `x = (a + b) / 3`, or even better pick a random point between a and b.

GistNoesis 2y ago
The article give the bellman equation that you need to solve. V(s)=max c sc×V′(s+c) + fc×V′(s−c) + nc×V′(s) V′(s)=min c sc×V(s−c) + fc×V(s+c) + nc×V(s) You have to solve for all states simultaneously. One way to solve them is by using fixed point iteration. aka successive approximation. Pick some small alpha and update the value function in a gradient ascent kind of way. Vi+1(s) = (1-alpha)Vi(s)+alpha ( max c sc×V′i(s+c)+ fc×V′i(s−c) + nc×V′i(s) ) V′i+1(s) = (1-alpha)V'i(s)+ alpha ( min c sc×Vi(s−c) + fc×Vi(s+c) + nc×Vi(s) ) https://en.wikipedia.org/wiki/Fixed-point_iteration https://en.wikipedia.org/wiki/Fixed-point_iteration
salamo 2y ago
I think there is. In this case we have to clarify that an optimal strategy can still lose due to random chance, so the optimal strategy will only be clear after some large number of games.
Ruphin 2y ago
There is no hidden information and turns are sequentially. This means both players have full access to all information, and that implies there must be a single "best" move. If the board is at a certain state and one player is to play next, the strategy of the opponent is irrelevant for determining the optimal move. Proof: Suppose that it is possible that different strategies exist that outperform each other. Lets consider the case that there are three "optimal" strategies that counter each other, call them Rock Paper and Scissors. Since these are the three "optimal" strategies, both players know the exact move produced by these strategies. The first important part to note is that there is no cost to changing strategy during the game. If an opponent has one fixed strategy, say Rock, the "optimal" strategy is to change your strategy to Paper. Since you have full information on the state of the board, you do not have to guess the strategy of the opponent, because there is no hidden information. Now you could consider the opponent strategy to be hidden information, but this doesn't hold for the following reason: If knowing the opponent strategy would alter your choice of move (by for example changing to Rock that specifically counters his hidden Scissors), the opponent can freely change to Paper after you made your move, because he can see that you changed to Rock before making his next move. If it was impossible for the opponent to tell that you changed your strategy, that implies that each strategy produces the same board state, and that implies the strategies are identical.
- blharr 2y ago
  Aren't the same conditions true for chess, though there is no proof that a best strategy exists? What if it's not just rock/paper/scissors, and there are more than 3 strategies?
  - sobellian 2y ago
    At least one of the players has a strategy that cannot be countered though. That is, either white can force a win, black can force a win, or both players can force a draw. There is no situation where every strategy can be countered.
  - Ruphin 2y ago
    There is no fundamental difference between Chess and Tic-Tac-Toe other than the computational complexity. It is not feasible to compute all of the game states in Chess, and so we cannot determine (at this time) a single optimal strategy the same way we can for Tic-Tac-Toe. But that does not imply that it doesn't exist. From a pure game theoretical perspective, they are the same category of game. If there are more than 3 strategies, the same argument stands. IF there are multiple "optimal" strategies, AND these strategies create different "optimal" moves on the same board state, the opponent can just play the optimal counter-strategy after you make your move, because your move is enough information to give away your strategy. If your opponent cannot determine your strategy after you make your move, that implies the different strategies have the same "optimal" move.
HWR_14 2y ago
I believe there is either only one solution or multiple equivalent solutions (e.g. in board where all squares are an equal probability, it doesn't matter which corner you start with.) You should assume an optimal counter-strategy when figuring out your move. I don't have the time to rigorously prove there's always an optimal solution, but it seems to be the case.

GistNoesis 2y ago

The article give the bellman equation that you need to solve. V(s)=max c sc×V′(s+c) + fc×V′(s−c) + nc×V′(s) V′(s)=min c sc×V(s−c) + fc×V(s+c) + nc×V(s) You have to solve for all states simultaneously. One way to solve them is by using fixed point iteration. aka successive approximation. Pick some small alpha and update the value function in a gradient ascent kind of way. Vi+1(s) = (1-alpha)Vi(s)+alpha ( max c sc×V′i(s+c)+ fc×V′i(s−c) + nc×V′i(s) ) V′i+1(s) = (1-alpha)V'i(s)+ alpha ( min c sc×Vi(s−c) + fc×Vi(s+c) + nc×Vi(s) ) https://en.wikipedia.org/wiki/Fixed-point_iteration https://en.wikipedia.org/wiki/Fixed-point_iteration

salamo 2y ago

I think there is. In this case we have to clarify that an optimal strategy can still lose due to random chance, so the optimal strategy will only be clear after some large number of games.

Ruphin 2y ago

There is no hidden information and turns are sequentially. This means both players have full access to all information, and that implies there must be a single "best" move. If the board is at a certain state and one player is to play next, the strategy of the opponent is irrelevant for determining the optimal move. Proof: Suppose that it is possible that different strategies exist that outperform each other. Lets consider the case that there are three "optimal" strategies that counter each other, call them Rock Paper and Scissors. Since these are the three "optimal" strategies, both players know the exact move produced by these strategies. The first important part to note is that there is no cost to changing strategy during the game. If an opponent has one fixed strategy, say Rock, the "optimal" strategy is to change your strategy to Paper. Since you have full information on the state of the board, you do not have to guess the strategy of the opponent, because there is no hidden information. Now you could consider the opponent strategy to be hidden information, but this doesn't hold for the following reason: If knowing the opponent strategy would alter your choice of move (by for example changing to Rock that specifically counters his hidden Scissors), the opponent can freely change to Paper after you made your move, because he can see that you changed to Rock before making his next move. If it was impossible for the opponent to tell that you changed your strategy, that implies that each strategy produces the same board state, and that implies the strategies are identical.

blharr 2y ago
Aren't the same conditions true for chess, though there is no proof that a best strategy exists? What if it's not just rock/paper/scissors, and there are more than 3 strategies?
- sobellian 2y ago
  At least one of the players has a strategy that cannot be countered though. That is, either white can force a win, black can force a win, or both players can force a draw. There is no situation where every strategy can be countered.
- Ruphin 2y ago
  There is no fundamental difference between Chess and Tic-Tac-Toe other than the computational complexity. It is not feasible to compute all of the game states in Chess, and so we cannot determine (at this time) a single optimal strategy the same way we can for Tic-Tac-Toe. But that does not imply that it doesn't exist. From a pure game theoretical perspective, they are the same category of game. If there are more than 3 strategies, the same argument stands. IF there are multiple "optimal" strategies, AND these strategies create different "optimal" moves on the same board state, the opponent can just play the optimal counter-strategy after you make your move, because your move is enough information to give away your strategy. If your opponent cannot determine your strategy after you make your move, that implies the different strategies have the same "optimal" move.

HWR_14 2y ago

I believe there is either only one solution or multiple equivalent solutions (e.g. in board where all squares are an equal probability, it doesn't matter which corner you start with.) You should assume an optimal counter-strategy when figuring out your move. I don't have the time to rigorously prove there's always an optimal solution, but it seems to be the case.