12 ms·

Solving Probabilistic Tic-Tac-Toe

138 points by Labo333 2y ago

H8crilA 2y ago
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.
phoronixrly 2y ago
I love how the other day when the Show HN[1] post was submitted there were a bunch of 'Oh what a great problem to solve with AI', when it was painfully obvious that it is not necessary... Is there astroturfing here or is AI the current hammer that everyone defaults to? [1] https://news.ycombinator.com/item?id=40635397 https://news.ycombinator.com/item?id=40635397
- Ukv 2y ago
  Unless there's a comment I'm missing, I don't see anyone recommending deep learning and neural networks. Comments such as "the AI is making really bad plays" mean in the videogame sense (the CPU player), as far as I can tell - which was just a simple heuristic in the original.
- renewiltord 2y ago
  [flagged]
- furyofantares 2y ago
  This is AI. At least in the classic sense of the word, which includes "search" as a broad category. I do see a lot of people using AI to mean specifically and only neural networks lately. I think this new use of the term is causing some confusion.
- orlp 2y ago
  When I said "Harder for humans, but easy to make a really strong AI for this." I was not referring to the modern meaning of the word 'AI' with GPTs, transformers, neural nets and whatnot, I was referring to the traditional meaning of the word, which is a machine observing its environment (the probabilistic tic-tac-toe board) and making decisions (which move should I make?) to achieve a goal within this environment (winning the game). Also note that in "make a really strong AI for this" AI is not a tool, it is the end-result. It is the agent that plays the game. I never said "solve with AI".
- krisoft 2y ago
  > Is there astroturfing here or is AI the current hammer that everyone defaults to? What is discussed in the article is AI. If you want to contrast it with the modern neural network / machine learning paradigms this flavour is often labeled GOFAI (good old fashioned artificial intelligence). https://en.wikipedia.org/wiki/GOFAI https://en.wikipedia.org/wiki/GOFAI
primitivesuave 2y ago
I implemented an expectiminimax player without the neutral state optimization that you described 2 days ago: https://keshav.is/coding/pt3 https://keshav.is/coding/pt3 It seems like even a naive search of the game tree in the browser produces a fairly strong computer opponent to a human player. It would be interesting to see if this optimization produces a better computer player to standard expectiminimax as I implemented here: https://github.com/keshavsaharia/pt3/blob/master/src/minimax.ts https://github.com/keshavsaharia/pt3/blob/master/src/minimax...
igpay 2y ago
Hey all, I'm the author of Probabilistic Tic-Tac-Toe. I'm currently working with Louis to integrate this solver into the game itself so that people can play against it. I'm hoping to have it released by EOD and will update this comment when it's ready.
- 317070 2y ago
  I'm actually interested in being coached by the solver, so it can tell me when I made a suboptimal move and what the optimal move would have been. Like in chess, playing against stockfish isn't very fun, but having it as a way to get better is fun.
  - igpay 2y ago
    Hey there, I thought this was a good idea so I added it to the game as "Tutor" mode. Thanks!
    - 317070 2y ago
      Thanks, this was very interesting. I was happy to see that my play was indeed near optimal.
- TarasBob 2y ago
  Have you considered making probabilistic Chess or Go? One way to do it is before each move a coin is flipped to decide who’s turn it is.
  - SamBam 2y ago
    Hmm, but party of the strategy of this one is that different cells have different odds, and you know those odds. It's not just a random 50% chance, that wouldn't be so interesting. I could see probabilistic cheese working as each grid square having an odds that the move will "work." Those odds stay the same the whole game. If you try to move from that square, the odds dictate whether you do your move or just lose it and skip your turn. This would mean that certain squares become very valuable. A queen on a 95% square is much more powerful than a queen on a 40% square. But those squares may not may not be in useful positions. And the battles may be over who gets to put good pieces on those squares.
spywaregorilla 2y ago
I said this on the original thread. You don't need to search the whole space. A greedy solution is fine. Considering a simple score that utilizes the odds of you getting it vs. your opponent, the paths to or immediate victories/losses opened up is nearly guaranteed to give you the optimal strategy every time. If a slot has negative odds, meaning it's more likely to help your opponent, you should NEVER play that slot unless you have no dissimilar options. Many slots, based on position, assume a value of 0 and should be avoided while there's positively valued options available. If a slot has a > 50% chance of handing you the win, you should always play it. (you could argue the model proves this rigidly at the 57% level) 9 calculations are all you need
- gus_massa 2y ago
  This is not a strategy, it's just an idea that can lead to an strategy. A strategy must give clear rules about which move to play. To make the question more clear, let's analyze the grid in the top of the blog post. I think it's clear for everyone [1] that the first player must play one of the cells on the top row. Which one is the best move left, middel or right? How is this explained by your strategy? [1] citation needed
  - spywaregorilla 2y ago
    Well let's start with the [1] 5 of the 9 squares have negative odds. If you play those your expected value is guaranteed to be negative. One of them has even odds, so barring any positional nuance to evaluating it sooner (of which there is none up front), there is an expected value of 0. So off the bat we have eliminated 66% of the search space by doing just 6 comparisons of odds. In fact, we haven't just solved the first turn. The optimal strategy is invariant to the outcome of the first draws. You will ALWAYS want to play the top row until it's complete, regardless of who gets which slot. Top left has an odds spread of +35 for the player. Top right has an odds spread of +40. So the right is guaranteed to be a superior choice. We haven't even begun to do any sort of nuanced analysis here and we're down to just two options. Top middle has a superior odds spread of +50. You would need to run some sort of model to derive the exact positional score of the corner vs. the upper middle for a first guess, but I'll tell you based on strong gut instinct, the middle slot with 10 points better odds is going to be the better choice. You can validate this on the new tutor mode if you want. Here's the algo I would use: * Calculate all net odds * If there's positive options, ignore all neutral and negative options. If there's no positives but there are neutrals, ignore all negatives * If there's any slot that offers you a > 50% chance of winning, play the one that does this with the best odds * Otherwise add one point per unlocked path, (e.g. 3 on a corner at games start, 2 at the side, or 4 for the center) or stopped path for your opponents * Pick the highest score (net odds + positional points). Break ties with higher probability or otherwise pick randomly. A few nuances here: * It'd probably be better to use odds ratio instead of net odds but that's trickier to spout off the top of my head * Probably underweighting the center by a bit for first choice but simplicity is good Feel free to this against tutor mode and find a counter example. The logic typically just gets easier and easier as the game goes on too.
malisper 2y ago
There is a simpler way to handle loops. If you end up repeating a position, you know the turn player will repeat the same move as before. By iterating over every possible move and every possible response, you can calculate the expected value of a position. Writing out the equations where V(s, i, j) is the expected value of the position when turn player will attempt move i and the opposing player will attempt move j: V(s) = max i (min j V(s, i, j)) V(s, i, j) = (probability move i or move j changes the state) * V(new state) + (probability state doesn't change) * V(s, i, j) You can solve the second equation for all i and j and then use that to solve the first equation.
- Labo333 2y ago
  Author here! I'm not sure about the first part V(s) = max i (min j V(s, i, j)) It looks like you suppose that j "precommits" to some move. But I'm not fully awake yet so you could be right.
- orlp 2y ago
  Your equation fails to take into account what the original article (before I notified the author, who kindly responded and shouted out my blog without even asking for it) also failed to take into account. When the dice rolls ":|" and you pass your turn, the state does change. Namely, whose turn it is changes. V(s, i, j) fails to capture this crucial detail.
  - malisper 2y ago
    This is accounted for because the second equation looks at sequences of two moves and not just one. After a sequence of two moves there are two possibilities. Either the state has changed or it has not. This is reflected in the left and right side of the second equation.
wsycharles0o 2y ago
I must say I'm so proud of the HN community for all the passion and curiosity for a problem like this!
Labo333 2y ago
Author here! It was such a power trip and blissful experience to discover the game on HN, think about a strategy, implement a solution, write a blog post (thanks again to orlp for his comment here that pointed out a mistake), email igpay (the author of the game), fork the repo, implement the algorithm in C# for Unity (it was my first time using those technologies but ChatGPT was quite helpful), get it merged and finally make it to the front page of HN where all of this started. Thank you guys, this is why the Internet exists!
- jb1991 2y ago
  The dynamic programming approach to solving tic-tac-toe is an implementation of reinforcement learning, is it not? I was surprised to see your post not mention reinforcement learning anywhere, despite that this solution appears in textbooks on reinforcement learning that use dynamic programming to solve tic-tac-toe.
  - sdwr 2y ago
    I don't think so. Reinforcement learning is about teaching by pairing correct actions with rewards, like giving a dog a treat for doing a trick. Dynamic programming is a recursive algorithm that caches partial results (from the bottom up). Apples and oranges
    - lrschaeffer 2y ago
      I'm no expert, but there are approaches to reinforcement learning where you build a table of the expected payoff for each scenario, and these can recursively reference other entries in the table. Take a look at Q-learning, for example.
    - jb1991 2y ago
      Dynamic programming is one of the most widely-used algorithms in reinforcement learning and in fact the tic-tac-toe example using dynamic programming is a classic demo in reinforcement learning classes or textbooks.
  - deleted 2y ago
fallingknife 2y ago
I played 20 games and only 1 was a draw. Interesting how this ends up being so rare compared to normal tic-tac-toe,
harpiaharpyja 2y ago
I don't think the description on the page really captures how much of an improvement this is over traditional tic-tac-toe. It's not at all about the outcome being contrary to how perfect or poorly someone played, though I'm sure that adds some excitement too. Deterministic tic-tac-toe is a very "degenerate" game, for lack of a better word, where the game readily falls into a state where one player is guaranteed to win absent a major blunder. There just isn't much space for actual decision making because most choices are just either obviously necessary or futile. By making every square have different probabilities like you have, you've created a kind of "terrain" to the board that needs to be considered when making moves, which adds a whole new dimension. Because the layout is randomized, the utility of each square might get re-evaluated from game to game, which adds a whole new dimension to gameplay.

138 points by Labo333 2y ago

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.

phoronixrly 2y ago

I love how the other day when the Show HN[1] post was submitted there were a bunch of 'Oh what a great problem to solve with AI', when it was painfully obvious that it is not necessary... Is there astroturfing here or is AI the current hammer that everyone defaults to? [1] https://news.ycombinator.com/item?id=40635397 https://news.ycombinator.com/item?id=40635397

Ukv 2y ago
Unless there's a comment I'm missing, I don't see anyone recommending deep learning and neural networks. Comments such as "the AI is making really bad plays" mean in the videogame sense (the CPU player), as far as I can tell - which was just a simple heuristic in the original.
renewiltord 2y ago
[flagged]
furyofantares 2y ago
This is AI. At least in the classic sense of the word, which includes "search" as a broad category. I do see a lot of people using AI to mean specifically and only neural networks lately. I think this new use of the term is causing some confusion.
orlp 2y ago
When I said "Harder for humans, but easy to make a really strong AI for this." I was not referring to the modern meaning of the word 'AI' with GPTs, transformers, neural nets and whatnot, I was referring to the traditional meaning of the word, which is a machine observing its environment (the probabilistic tic-tac-toe board) and making decisions (which move should I make?) to achieve a goal within this environment (winning the game). Also note that in "make a really strong AI for this" AI is not a tool, it is the end-result. It is the agent that plays the game. I never said "solve with AI".
krisoft 2y ago
> Is there astroturfing here or is AI the current hammer that everyone defaults to? What is discussed in the article is AI. If you want to contrast it with the modern neural network / machine learning paradigms this flavour is often labeled GOFAI (good old fashioned artificial intelligence). https://en.wikipedia.org/wiki/GOFAI https://en.wikipedia.org/wiki/GOFAI

primitivesuave 2y ago

I implemented an expectiminimax player without the neutral state optimization that you described 2 days ago: https://keshav.is/coding/pt3 https://keshav.is/coding/pt3 It seems like even a naive search of the game tree in the browser produces a fairly strong computer opponent to a human player. It would be interesting to see if this optimization produces a better computer player to standard expectiminimax as I implemented here: https://github.com/keshavsaharia/pt3/blob/master/src/minimax.ts https://github.com/keshavsaharia/pt3/blob/master/src/minimax...

igpay 2y ago

Hey all, I'm the author of Probabilistic Tic-Tac-Toe. I'm currently working with Louis to integrate this solver into the game itself so that people can play against it. I'm hoping to have it released by EOD and will update this comment when it's ready.

317070 2y ago
I'm actually interested in being coached by the solver, so it can tell me when I made a suboptimal move and what the optimal move would have been. Like in chess, playing against stockfish isn't very fun, but having it as a way to get better is fun.
- igpay 2y ago
  Hey there, I thought this was a good idea so I added it to the game as "Tutor" mode. Thanks!
  - 317070 2y ago
    Thanks, this was very interesting. I was happy to see that my play was indeed near optimal.
TarasBob 2y ago
Have you considered making probabilistic Chess or Go? One way to do it is before each move a coin is flipped to decide who’s turn it is.
- SamBam 2y ago
  Hmm, but party of the strategy of this one is that different cells have different odds, and you know those odds. It's not just a random 50% chance, that wouldn't be so interesting. I could see probabilistic cheese working as each grid square having an odds that the move will "work." Those odds stay the same the whole game. If you try to move from that square, the odds dictate whether you do your move or just lose it and skip your turn. This would mean that certain squares become very valuable. A queen on a 95% square is much more powerful than a queen on a 40% square. But those squares may not may not be in useful positions. And the battles may be over who gets to put good pieces on those squares.

spywaregorilla 2y ago

I said this on the original thread. You don't need to search the whole space. A greedy solution is fine. Considering a simple score that utilizes the odds of you getting it vs. your opponent, the paths to or immediate victories/losses opened up is nearly guaranteed to give you the optimal strategy every time. If a slot has negative odds, meaning it's more likely to help your opponent, you should NEVER play that slot unless you have no dissimilar options. Many slots, based on position, assume a value of 0 and should be avoided while there's positively valued options available. If a slot has a > 50% chance of handing you the win, you should always play it. (you could argue the model proves this rigidly at the 57% level) 9 calculations are all you need

gus_massa 2y ago
This is not a strategy, it's just an idea that can lead to an strategy. A strategy must give clear rules about which move to play. To make the question more clear, let's analyze the grid in the top of the blog post. I think it's clear for everyone [1] that the first player must play one of the cells on the top row. Which one is the best move left, middel or right? How is this explained by your strategy? [1] citation needed
- spywaregorilla 2y ago
  Well let's start with the [1] 5 of the 9 squares have negative odds. If you play those your expected value is guaranteed to be negative. One of them has even odds, so barring any positional nuance to evaluating it sooner (of which there is none up front), there is an expected value of 0. So off the bat we have eliminated 66% of the search space by doing just 6 comparisons of odds. In fact, we haven't just solved the first turn. The optimal strategy is invariant to the outcome of the first draws. You will ALWAYS want to play the top row until it's complete, regardless of who gets which slot. Top left has an odds spread of +35 for the player. Top right has an odds spread of +40. So the right is guaranteed to be a superior choice. We haven't even begun to do any sort of nuanced analysis here and we're down to just two options. Top middle has a superior odds spread of +50. You would need to run some sort of model to derive the exact positional score of the corner vs. the upper middle for a first guess, but I'll tell you based on strong gut instinct, the middle slot with 10 points better odds is going to be the better choice. You can validate this on the new tutor mode if you want. Here's the algo I would use: * Calculate all net odds * If there's positive options, ignore all neutral and negative options. If there's no positives but there are neutrals, ignore all negatives * If there's any slot that offers you a > 50% chance of winning, play the one that does this with the best odds * Otherwise add one point per unlocked path, (e.g. 3 on a corner at games start, 2 at the side, or 4 for the center) or stopped path for your opponents * Pick the highest score (net odds + positional points). Break ties with higher probability or otherwise pick randomly. A few nuances here: * It'd probably be better to use odds ratio instead of net odds but that's trickier to spout off the top of my head * Probably underweighting the center by a bit for first choice but simplicity is good Feel free to this against tutor mode and find a counter example. The logic typically just gets easier and easier as the game goes on too.

malisper 2y ago

There is a simpler way to handle loops. If you end up repeating a position, you know the turn player will repeat the same move as before. By iterating over every possible move and every possible response, you can calculate the expected value of a position. Writing out the equations where V(s, i, j) is the expected value of the position when turn player will attempt move i and the opposing player will attempt move j: V(s) = max i (min j V(s, i, j)) V(s, i, j) = (probability move i or move j changes the state) * V(new state) + (probability state doesn't change) * V(s, i, j) You can solve the second equation for all i and j and then use that to solve the first equation.

Labo333 2y ago
Author here! I'm not sure about the first part V(s) = max i (min j V(s, i, j)) It looks like you suppose that j "precommits" to some move. But I'm not fully awake yet so you could be right.
orlp 2y ago
Your equation fails to take into account what the original article (before I notified the author, who kindly responded and shouted out my blog without even asking for it) also failed to take into account. When the dice rolls ":|" and you pass your turn, the state does change. Namely, whose turn it is changes. V(s, i, j) fails to capture this crucial detail.
- malisper 2y ago
  This is accounted for because the second equation looks at sequences of two moves and not just one. After a sequence of two moves there are two possibilities. Either the state has changed or it has not. This is reflected in the left and right side of the second equation.

wsycharles0o 2y ago

I must say I'm so proud of the HN community for all the passion and curiosity for a problem like this!

Labo333 2y ago

Author here! It was such a power trip and blissful experience to discover the game on HN, think about a strategy, implement a solution, write a blog post (thanks again to orlp for his comment here that pointed out a mistake), email igpay (the author of the game), fork the repo, implement the algorithm in C# for Unity (it was my first time using those technologies but ChatGPT was quite helpful), get it merged and finally make it to the front page of HN where all of this started. Thank you guys, this is why the Internet exists!

jb1991 2y ago
The dynamic programming approach to solving tic-tac-toe is an implementation of reinforcement learning, is it not? I was surprised to see your post not mention reinforcement learning anywhere, despite that this solution appears in textbooks on reinforcement learning that use dynamic programming to solve tic-tac-toe.
- sdwr 2y ago
  I don't think so. Reinforcement learning is about teaching by pairing correct actions with rewards, like giving a dog a treat for doing a trick. Dynamic programming is a recursive algorithm that caches partial results (from the bottom up). Apples and oranges
  - lrschaeffer 2y ago
    I'm no expert, but there are approaches to reinforcement learning where you build a table of the expected payoff for each scenario, and these can recursively reference other entries in the table. Take a look at Q-learning, for example.
  - jb1991 2y ago
    Dynamic programming is one of the most widely-used algorithms in reinforcement learning and in fact the tic-tac-toe example using dynamic programming is a classic demo in reinforcement learning classes or textbooks.
- deleted 2y ago

fallingknife 2y ago

I played 20 games and only 1 was a draw. Interesting how this ends up being so rare compared to normal tic-tac-toe,

harpiaharpyja 2y ago

I don't think the description on the page really captures how much of an improvement this is over traditional tic-tac-toe. It's not at all about the outcome being contrary to how perfect or poorly someone played, though I'm sure that adds some excitement too. Deterministic tic-tac-toe is a very "degenerate" game, for lack of a better word, where the game readily falls into a state where one player is guaranteed to win absent a major blunder. There just isn't much space for actual decision making because most choices are just either obviously necessary or futile. By making every square have different probabilities like you have, you've created a kind of "terrain" to the board that needs to be considered when making moves, which adds a whole new dimension. Because the layout is randomized, the utility of each square might get re-evaluated from game to game, which adds a whole new dimension to gameplay.