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!
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.
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)
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.
I implemented an expectiminimax player without the neutral state optimization that you described 2 days ago: 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...
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
I played 20 games and only 1 was a draw. Interesting how this ends up being so rare compared to normal tic-tac-toe,
I must say I'm so proud of the HN community for all the passion and curiosity for a problem like this!
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?
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.