Show HN: Probabilistic Tic-Tac-Toe(csun.io)
csun.io
Show HN: Probabilistic Tic-Tac-Toe
https://www.csun.io/2024/06/08/probabilistic-tic-tac-toe.html
112 comments
Nice! And irritating!
I would make it a lot faster though. It takes so much time waiting for the animations to finish.
Too much time to load too (ditch the overkill 3D engine, there are lighter frameworks out there).
Cool game though. I am still puzzled by how the probabilities are arrived at. Random?
Cool game though. I am still puzzled by how the probabilities are arrived at. Random?
Agreed that 3D is overkill. I'm fastest at prototyping in Unity though and this was only a couple day project, so I'm unlikely to port it to anything else.
Probabilities are mostly randomized during board generation but skewed in a way to make gameplay feel a bit better. There's a cap on the likelihood of the neutral event, and a bias towards the good event rather than a bad one.
Probabilities are mostly randomized during board generation but skewed in a way to make gameplay feel a bit better. There's a cap on the likelihood of the neutral event, and a bias towards the good event rather than a bad one.
I got the die to settle on an edge in the corner of the playfield, which triggered a re-roll.
Is this actually simulating a d20 with physics?
Is this actually simulating a d20 with physics?
Can you please share the specifics? I'm trying to make my own AI for this game, and would like to compare mine against random play to estimate its strength.
Also, in your listing of your ai beating the random, how are you counting drawn games?
Also, in your listing of your ai beating the random, how are you counting drawn games?
The current code for board generation is as follows:
I guess I didn't include ties in that little blurb I wrote up, but the real results of my 10k trials were around 5:1:11.5 (lose:tie:win) for the AI vs random actor.
Would love to see your AI when it's done! Please shoot me an email if you want. My email is in my profile / in the site footer.
var neutralChances = Random.Range(1, MaxNeutralChances + 1);
square.GoodChances = Random.Range(MinGoodChances, 20 - neutralChances);
square.BadChances = 20 - (square.GoodChances + neutralChances);
I guess I didn't include ties in that little blurb I wrote up, but the real results of my 10k trials were around 5:1:11.5 (lose:tie:win) for the AI vs random actor.
Would love to see your AI when it's done! Please shoot me an email if you want. My email is in my profile / in the site footer.
Why an AI? Just for the fun of implementing it (totally valid, just curious)? Given the probabilities of the outcomes couldn't you just "solve" for the best way to play it based on expected value?
If there are 65% and 50% to complete a row in one direction, and a 35% and 20% in another direction, you don't really need AI to tell you which one would be more advantageous to go after?
If there are 65% and 50% to complete a row in one direction, and a 35% and 20% in another direction, you don't really need AI to tell you which one would be more advantageous to go after?
Yes, I've made what is intended to be a perfect solver (Although it in some testing it's clearly making mistakes, so I have some debugging to do yet). I'm making it because I was nerd sniped into thinking through how to handle some of the trickiness with the solving. It's not an AI in the LLM or machine learning sense, but in the previously common use of the term (eg, deep blue), or in the video game sense.
Very cool! Best of luck working on it!
That's cool — use what you're comfortable with.
Myself, I am trying to create lightweight 3D code to sit on top of Canvas and HTML5. That may be why I was sensitive to the "overkill", ha ha.
https://github.com/EngineersNeedArt/Phosphor3D
Myself, I am trying to create lightweight 3D code to sit on top of Canvas and HTML5. That may be why I was sensitive to the "overkill", ha ha.
https://github.com/EngineersNeedArt/Phosphor3D
Agreed. Taking the time to roll the dice is important the first few times, to fully cement the idea of the game. After that it gets annoying.
To be specific, you could probably even leave the roll time as-is, to give you that suspense, but the time it takes to move the die to the center, flash it, and flash the result, is too long and gets irritating.
To be specific, you could probably even leave the roll time as-is, to give you that suspense, but the time it takes to move the die to the center, flash it, and flash the result, is too long and gets irritating.
That's good feedback, thanks. I've added a fast forward button to the top left.
An extra click that would stop the animation immediately might be helpful.
Or to turn this into a different game: the d20 stops fast by default, but extra click to cheat and keep it rolling if you feel that it's about to stop on an unfavorable face.
Or to turn this into a different game: the d20 stops fast by default, but extra click to cheat and keep it rolling if you feel that it's about to stop on an unfavorable face.
I made some updates to speed up the UI, and improved the computer player, as I was interested in finding the optimal strategy: https://keshav.is/coding/pt3
Harder for humans, but easy to make a really strong AI for this. Even overcounting because of illegal board states (multiple winners) and not even bothering to eliminate symmetries, there are at most 2 * 3^9 = 39366 board states.
There are cycles in the board state graph, although they are of a very specific form (the only kind of cycle that exists is for board B with O and X alternating turns). So it is probably possible to make a completely deterministic and optimal algorithm for this probabilistic game, but it does sound complicated. You can't naively apply expectiminimax.
However after marking the winning board states as 0 or 1 respectively if O or X wins I would expect value iteration to very quickly converge to an optimal strategy here.
There are cycles in the board state graph, although they are of a very specific form (the only kind of cycle that exists is for board B with O and X alternating turns). So it is probably possible to make a completely deterministic and optimal algorithm for this probabilistic game, but it does sound complicated. You can't naively apply expectiminimax.
However after marking the winning board states as 0 or 1 respectively if O or X wins I would expect value iteration to very quickly converge to an optimal strategy here.
>Harder for humans
IDK if it's just me, but I went 6-0. Is something wrong with the computer player logic?
IDK if it's just me, but I went 6-0. Is something wrong with the computer player logic?
The OP mentioned that the AI they programmed is using a simple heuristic.
i went up 8-1 and 6 games later it was 8-7
1/64 chance.
What happens if you play 6 more?
What happens if you play 6 more?
I think this is doable. Say we assign a win rate W(S) to each board state S, and let W(S, A) denote the win rate after taking action A from state S. Since the transition is probabilistic, we can write:
W(S, A) = P(good) * (1 - W(S_good)) + P(bad) * (1 - W(S_bad)) + (1 - P(good) - P(bad)) * (1 - W(S))
And obvisouly:
W(S) = max(W(S, A), foreach A in Actions)
max() is troublesome, but we can replace it with a >= sign:
W(S) >= (W(S, A), forall A in Actions)
And then we can expand W(S, A) and move W(S) in each of the inequalities to the left hand side. After all that we will have a bunch of linear inequalities which can be optimized with linear programming. I think the objective would just be:
<del>maximize</del> minimize W(empty_board)
W(S, A) = P(good) * (1 - W(S_good)) + P(bad) * (1 - W(S_bad)) + (1 - P(good) - P(bad)) * (1 - W(S))
And obvisouly:
W(S) = max(W(S, A), foreach A in Actions)
max() is troublesome, but we can replace it with a >= sign:
W(S) >= (W(S, A), forall A in Actions)
And then we can expand W(S, A) and move W(S) in each of the inequalities to the left hand side. After all that we will have a bunch of linear inequalities which can be optimized with linear programming. I think the objective would just be:
<del>maximize</del> minimize W(empty_board)
There is an easier way to solve each recursion! I just wrote a blog post on it: https://louisabraham.github.io/articles/probabilistic-tic-ta...
Yep, this is what I ended up doing as well! With how the game generate boards, the player that goes first always have a ~5% advantage. Since players switch hands each around they should have 50% win rate if both play optimally.
In practice, playing against author's AI I barely get ~60% win rate (small caveat, I count ties as 0.5 to both players). What about yours?
Edit: nvm I saw you did the same with ties.
In practice, playing against author's AI I barely get ~60% win rate (small caveat, I count ties as 0.5 to both players). What about yours?
Edit: nvm I saw you did the same with ties.
[deleted]
Turns out linear programming is not fast... Takes about 90 minutes to find the optimal solution for any board configuration.
I think you will find it extremely difficult to do better than simply checking the probability that each square gives you a spot times the number of victory paths it opens up minus the probability that it gives your opponent a spot times the number of victory paths it opens up for them. Add another clause for paths closed if you want.
Since chance is involved, you will basically never want to do anything but the greediest highest value next action. Sometimes more than half the board has net value of 0 or less which makes them very easy to ignore.
Since chance is involved, you will basically never want to do anything but the greediest highest value next action. Sometimes more than half the board has net value of 0 or less which makes them very easy to ignore.
Wouldn't you also have to take into account the probability of the following moves also being successful and giving you a win?
No because the odds are symmetric for every slot. If you have two in a row; and the third slot has higher odds that it goes to the non-roller, you should just... not roll in it.
The timing of when it gets rolled won't matter. The need to urgently consider blocking off other routes to victory will be embedded in the scoring described above.
The timing of when it gets rolled won't matter. The need to urgently consider blocking off other routes to victory will be embedded in the scoring described above.
> Since chance is involved, you will basically never want to do anything but the greediest highest value next action. Sometimes more than half the board has net value of 0 or less which makes them very easy to ignore.
Since passing is not an option, you can't ignore a net value of 0 or less, because all options might have a net value of 0 or less.
Since passing is not an option, you can't ignore a net value of 0 or less, because all options might have a net value of 0 or less.
Sure. But there's still no conceivable situation where it is advantageous to pursue such an option while a net positive option exists. Ergo, it is easy to ignore.
WRT to computing an exact solution, something something markov chains, transition matrices, eigenvalues. I think it is tractable
Usually those are for additive/linear systems, the problem with game theoretic graphs like these is that you alternate between max and min nodes, so the system is highly nonlinear.
You're right.
I'll work on the simpler problem of :) / :( first. I think that can be done with just minimax
And then maybe win chance for each possible state of a purely random game
I'll work on the simpler problem of :) / :( first. I think that can be done with just minimax
And then maybe win chance for each possible state of a purely random game
If it were just solely :) / :( then it is a freshman's exercise in expectiminimax.
it turns out you don't need anything more than minimax for the general case Here's my solution https://github.com/pvillano/probabalistic-tic-tac-toe
I think this fails to take into account that your opponent can also roll 'meh', making it your turn again.
Brilliant! Makes a simple children's game very interesting. One aspect I really enjoy is that it makes clear the knee-jerk response towards action bias[0]. There are times when your opponent has two-in-a-row, but the probability of a frown on the third is > 50%, in which case it's in my interest to have my opponent click on the third square instead of me (but even knowing that cognitively, it's still hard to not action).
[0]: https://en.wikipedia.org/wiki/Action_bias
[0]: https://en.wikipedia.org/wiki/Action_bias
As someone who often prints boardgames, this strikes me as a game that would be very easy to build a physical version of, just printing some tiles with random distributions printed on, and finding some tokens and a die to use. It would make a compact travel game. I do not think there would have to be a huge number of tiles. A few more than nine ought to be enough?
you would need different dice for each distribution but you could use a normal d20 and a lookup table for less needed equipment.. I think it could work!
A D20 would be more than enough, you just put the probabilities of the tiles in terms of 20 digits.
I'm saying if you wanted to mimic the happy/meh/sad faces on the die in this game you would need multiple dice. But since all of the percentages are in 5% increments yes a D20 is all you would need. I suggest a lookup table for the players who are uncomfortable or uninterested in doing the percentage division in their head, and the sum of the two lower partitions. But you've got me thinking you could probably also have a run of custom-labeled D20s with increments of 5 instead of 1 to eliminate the LUT.
The square would look like:
1-5 sad face 6-9 neutral face 10-20 happy face
more or less like an ability check in DnD
1-5 sad face 6-9 neutral face 10-20 happy face
more or less like an ability check in DnD
Yes, I think we're saying the same thing. Your second sentence is exactly what I mean by lookup table.
Neat idea! The computer keeps beating me with its basic strategy.
I also managed to get the die stuck on a side with an edge pointing up, to where the game couldn't choose a face. I thought it was going to brick the game, but it detected this and re-rolled the die. Nice!
I also managed to get the die stuck on a side with an edge pointing up, to where the game couldn't choose a face. I thought it was going to brick the game, but it detected this and re-rolled the die. Nice!
Great game. I find it interesting how impactful neutral rolls are. Whoever is last to place a mark can be forced to act against their own interest, making a roll that is likely to result in the win for the opponent. But rolling the neutral face skips the turn, changing who places the last mark.
> So what gives us the right to claim responsibility for our victories? Do we ever truly win? Or do we just get lucky sometimes?
> Well, in any given game of Probabilistic Tic-Tac-Toe you can do everything right and still lose (or do everything wrong and win.) However, the better player always rises to the top over time.
> Bad breaks are inevitable, but good judgment is always rewarded (eventually, and given enough chances.)
This assumes that everyone is on a level playing field with only non-compounding randomness preventing the better player from winning. But as you point out, luck does compound over time:
>The parents we’re born to, societal power structures... so many past events have an invisible impact on each new action we take
This is commonly known as the rich get richer and the poor get poorer, and to economists as the Matthew Effect[1].
You could try to model this in the game by having wins skew the odds of the next game in your favor. It's harder to model in a simple two person game like this... You have to persist state for a population of players over time.
I've wanted to publish alternate rules for Monopoly, where at the start of the game players don't get the same amount of cash. Cash is instead distributed according to real statistics for "birth wealth". Alternatively, your cash at the end of a game roles over into the next game.
I'd love to discuss this with you if you are interested. We might even collaborate on a future project.
---
[1]: https://en.wikipedia.org/wiki/Matthew_effect
> Well, in any given game of Probabilistic Tic-Tac-Toe you can do everything right and still lose (or do everything wrong and win.) However, the better player always rises to the top over time.
> Bad breaks are inevitable, but good judgment is always rewarded (eventually, and given enough chances.)
This assumes that everyone is on a level playing field with only non-compounding randomness preventing the better player from winning. But as you point out, luck does compound over time:
>The parents we’re born to, societal power structures... so many past events have an invisible impact on each new action we take
This is commonly known as the rich get richer and the poor get poorer, and to economists as the Matthew Effect[1].
You could try to model this in the game by having wins skew the odds of the next game in your favor. It's harder to model in a simple two person game like this... You have to persist state for a population of players over time.
I've wanted to publish alternate rules for Monopoly, where at the start of the game players don't get the same amount of cash. Cash is instead distributed according to real statistics for "birth wealth". Alternatively, your cash at the end of a game roles over into the next game.
I'd love to discuss this with you if you are interested. We might even collaborate on a future project.
---
[1]: https://en.wikipedia.org/wiki/Matthew_effect
As a longtime XCOM veteran, I am constitutionally opposed to making any game move with less than an 85% chance of success.
Nice game, I like the idea of your, opponent and no turn. I made a similar game long time back (around 2014) also called Probabilistic Tic Tac Toe ( https://shubhanshu.com/PT3/ ), but my randomization rules were different. I used coin toss to decide on the move vetween two choices.
Old HN thread: https://news.ycombinator.com/item?id=12932183
Old HN thread: https://news.ycombinator.com/item?id=12932183
Took me a minute to catch on - just play the odds! At first I was trying to play tic tac toe, but the winning strategy seems to be to go for the square likeliest to land your own mark.
That's how the AI seems to play it. :)
Yes, the AI mostly just looks for plays that have high certainty and are connected to other potential winning squares (for either team). Then it weights plays positively or negatively based on whether or not the "bad" chance outweighs "good"
I don’t think this is right though. I watched it pick a 70 it didn’t need over a 60 I used to win.
Nice!
UI suggestion: show the probabilities for a move as a point in a triangle, with your outcome labels on the vertices. (Or maybe as red/green/neutral colors in the triangle's interior.) This representation is called the "probability simplex". It would look less busy, quicker to scan, I think.
UI suggestion: show the probabilities for a move as a point in a triangle, with your outcome labels on the vertices. (Or maybe as red/green/neutral colors in the triangle's interior.) This representation is called the "probability simplex". It would look less busy, quicker to scan, I think.
I was able to consistently get about 2:1 lead over the ai by balancing the center and corners as valuable and trying to force it to play bad squares. It's a good amount of randomness tossed in.
The do nothing move is a nice touch
The do nothing move is a nice touch
Sweet!
I think the AI should be optimized to not make plays that look obviously bad. It doesn't really need to be any harder, but it kinda ruins it when it makes a play that seems really obviously bad to me.
Also does it simply never play the center? It seems center is never an outlier probability but also feels like the AI should play it sometime. (edit: After 20 or so games it finally did. Maybe I was just overvaluing it? Although I'm winning about 80%.)
These suggestions are all about the feel of playing the AI rather than difficulty.
I think the AI should be optimized to not make plays that look obviously bad. It doesn't really need to be any harder, but it kinda ruins it when it makes a play that seems really obviously bad to me.
Also does it simply never play the center? It seems center is never an outlier probability but also feels like the AI should play it sometime. (edit: After 20 or so games it finally did. Maybe I was just overvaluing it? Although I'm winning about 80%.)
These suggestions are all about the feel of playing the AI rather than difficulty.
I created an open-source web version of this game with a better computer player, which uses expectiminimax to pick the optimal move - https://keshav.is/coding/pt3/
Link to HN submission: https://news.ycombinator.com/item?id=40653736
Link to HN submission: https://news.ycombinator.com/item?id=40653736
It doesn't require AI to solve the game. It's possible to do with probabilistic theory, dynamic programming and game theory (minimax)
What engine is this using?
Any recommendations for creating simple 3d visualizations of orbiting spheres? Something like the one from the link, but more web-native (instead of python)?: https://trinket.io/glowscript/a90cba5f40
Any recommendations for creating simple 3d visualizations of orbiting spheres? Something like the one from the link, but more web-native (instead of python)?: https://trinket.io/glowscript/a90cba5f40
Unity per the logo on the loading screen
Totally changes the game for me. Makes it so that you (almost) never want to play the middle square unless your hand is forced.
Also reminds me of how I was playing Senet last night. I controlled the game until the very end, where by chance, I kept rolling "bad" numbers and my opponent kept rolling "good" numbers.
Also reminds me of how I was playing Senet last night. I controlled the game until the very end, where by chance, I kept rolling "bad" numbers and my opponent kept rolling "good" numbers.
Really cool, lost two games in a row, finally won my third one after the computer got extremely unlucky.
I was wondering if I maybe experienced a bug. Do you shortcut drawn games when neither player can win?)
I just played 100 rounds of this game, winning 47 times, tying 6, and losing 47. Very fun. I think it would be cool if I could look back at my previous games and figure out more optimal strategies so I could possibly get the slightest edge on the CPU.
This is just awesome, great idea. The computer doesn’t seem to defend against obvious, probabilistic winning moves (doesn’t block a final square). But funnily this works to its advantage sometimes if you end up rolling frowny
This just reminded me why I hate output randomness in games. Lost 3 75% in a row
Fascinating. I am curious, what other games do you all think this could be extended to and still remains fun? Connect Four seems like a natural extension to me. I'd love to see some of these dynamics in Battleship.
Interesting twist.
Reminded me a bit of the Quantum Tic Tac Toe[1] game that I stumbled over some time ago.
[1]: https://quantumtictactoe.com/play/
Reminded me a bit of the Quantum Tic Tac Toe[1] game that I stumbled over some time ago.
[1]: https://quantumtictactoe.com/play/
You can still strategize when the probability of failure and success are equal.
For example, O should choose the lower right because it gives them a greater than 50% chance of winning, whereas choosing another spot gives them a greater than 50% chance of loosing
X X O
X _ O
_ X _
For example, O should choose the lower right because it gives them a greater than 50% chance of winning, whereas choosing another spot gives them a greater than 50% chance of loosing
X X O
X _ O
_ X _
A new rule could be to make a neutral roll prevent the enemy to play that square for one turn (unless it's the last square).
This is a small thing but I really wish it would draw a line through the three in a row when you get one.
This is fantastic!
The dice roll animation is :chefkiss:
The dice roll animation is :chefkiss:
Okay. This has a lot more depth than it initially appeared. What a great twist on a simple game!
It's an interesting game, but the AI is making really bad plays.
are you, by chance, giving the computer artificially poor luck? My opponent has been rolling so amusingly poorly that I have to wonder if he's handicapped somehow?
Offline multiplayer over bluetooth would be a great addition!
[deleted]
all I see is a dark grey square? using Firefox on mac
Got the same in chrome but it eventually loaded
Got the same in chrome but it eventually loaded
Worked for me eventually on Firefox / Linux. Definitely has a slow start on first load.
Thanks for that, I added a loading bar. It should be visible now if you refresh the page.
Number of times I selected a square with 5% "meh" chance: 10. Number of times I got "meh" and the computer then selected that square: 8. I know probability is weird but this happens to me when rolling dice as well (I had a D&D 5E character who nearly always rolled attacks with advantage. I had a streak of 20 attacks in a row (i.e. 40 rolls of a 20 sided die) without getting a double-digit number, and even got a critical failure (which required two 1s).
Reminds me of Quantum Chess
it's a bit slow with all the animation... but nice idea
This is very cool and fun to play.
Another interesting variant is incomplete information Tic Tac Toe which was posted by SMBC: https://www.smbc-comics.com/comic/incomplete
Another interesting variant is incomplete information Tic Tac Toe which was posted by SMBC: https://www.smbc-comics.com/comic/incomplete
I enjoyed playing a few rounds of Probabilistic TTT, and 'Incomplete Information Tic-Tac-Toe' sounded interesting too.
After thinking about it last night, I made a quick version this morning, and I think it's fun to play as well: https://eapl.me/incomplete/
After thinking about it last night, I made a quick version this morning, and I think it's fun to play as well: https://eapl.me/incomplete/
Montecarlo Tree Search (MCTS) would be very ideal for this situation. Since the tree depth is really low, you would not need a neural network estimator. You would just load the entire game tree, and walk randomly through it, updating visit counts. The walk would be biased by the visit counts, and the biases would then converge to scores for each position.
See the following for a really nice tutorial for a slightly more advanced but more technically correct algorithm, Monte Carlo graph search (MCGS). This exploits the fact that some nodes in the game tree might are identical positions on the board and can be merged.
For your setup he could easily do either one, but the graph search might give you more mileage in the future:
github.com/lightvector/KataGo/blob/master/docs/GraphSearch.md
Once your scores have converged on the entire game tree, you can print out a crib sheet visually showing each position and the correct move. That might be the closest we can get to a human executable strategy. But the crib sheet might have strategic principles or hard rules that humans can identify
See the following for a really nice tutorial for a slightly more advanced but more technically correct algorithm, Monte Carlo graph search (MCGS). This exploits the fact that some nodes in the game tree might are identical positions on the board and can be merged.
For your setup he could easily do either one, but the graph search might give you more mileage in the future:
github.com/lightvector/KataGo/blob/master/docs/GraphSearch.md
Once your scores have converged on the entire game tree, you can print out a crib sheet visually showing each position and the correct move. That might be the closest we can get to a human executable strategy. But the crib sheet might have strategic principles or hard rules that humans can identify
I implemented expectiminimax in the browser which allows for a fairly strong AI player: https://keshav.is/coding/pt3/
I found that once you naively search the game tree beyond a depth of 8, it more or less converges on a particular choice. The presence of a neutral outcome (i.e. neither player claims the selected square) means the tree depth is technically infinite, but feasible to search thoroughly once the first few moves have been played.
I found that once you naively search the game tree beyond a depth of 8, it more or less converges on a particular choice. The presence of a neutral outcome (i.e. neither player claims the selected square) means the tree depth is technically infinite, but feasible to search thoroughly once the first few moves have been played.
> load the entire game tree, and walk randomly through it
Can't you just multiply all the percentages and just get an expected value for each field? Why the random walk? Can't you just calculate this exhaustively?
Can't you just multiply all the percentages and just get an expected value for each field? Why the random walk? Can't you just calculate this exhaustively?
Read the article, my friend. Then you'll see what is so magical about the random walk algorithm - namely, it is easier to implement then other tree evaluation algorithms!
Of course, you can use a number of algorithms to calculate the value, and if you beat me to the punch and it's correct, how about this I'll buy you a burger. But which specific algorithm are you proposing, and where is its pseudocode and correctness proof?
And is it simpler? If so I'll implement that instead of the random walk!
I picked the random walk algorithm because it is much easier to implement than any other game tree evaluation algorithm I know.
Of course, you can use a number of algorithms to calculate the value, and if you beat me to the punch and it's correct, how about this I'll buy you a burger. But which specific algorithm are you proposing, and where is its pseudocode and correctness proof?
And is it simpler? If so I'll implement that instead of the random walk!
I picked the random walk algorithm because it is much easier to implement than any other game tree evaluation algorithm I know.
[deleted]