by Labo333 on 6/11/24, 2:25 PM with 44 comments
by igpay on 6/13/24, 9:58 PM
by Labo333 on 6/14/24, 8:10 AM
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!
by harpiaharpyja on 6/14/24, 1:40 PM
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.
by malisper on 6/14/24, 1:34 AM
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)
by H8crilA on 6/13/24, 7:19 PM
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.
by primitivesuave on 6/13/24, 9:03 PM
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...
by spywaregorilla on 6/14/24, 12:17 AM
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
by fallingknife on 6/14/24, 9:05 AM
by wsycharles0o on 6/14/24, 2:54 AM
by phoronixrly on 6/13/24, 8:05 PM