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.
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.
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.
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:
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:
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.
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).
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!
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!
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.
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.
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.
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.
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/
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
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.
[+] [-] janwillemb|1 year ago|reply
[+] [-] JKCalhoun|1 year ago|reply
Cool game though. I am still puzzled by how the probabilities are arrived at. Random?
[+] [-] SamBam|1 year ago|reply
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.
[+] [-] igpay|1 year ago|reply
[+] [-] omoikane|1 year ago|reply
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.
[+] [-] primitivesuave|1 year ago|reply
[+] [-] orlp|1 year ago|reply
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.
[+] [-] hammock|1 year ago|reply
IDK if it's just me, but I went 6-0. Is something wrong with the computer player logic?
[+] [-] yshui|1 year ago|reply
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)
[+] [-] spywaregorilla|1 year ago|reply
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.
[+] [-] pvillano|1 year ago|reply
[+] [-] mbroshi|1 year ago|reply
[0]: https://en.wikipedia.org/wiki/Action_bias
[+] [-] livrem|1 year ago|reply
[+] [-] kevindamm|1 year ago|reply
[+] [-] legohead|1 year ago|reply
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!
[+] [-] wongarsu|1 year ago|reply
[+] [-] eevilspock|1 year ago|reply
> 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
[+] [-] cainxinth|1 year ago|reply
[+] [-] napsternxg|1 year ago|reply
Old HN thread: https://news.ycombinator.com/item?id=12932183
[+] [-] btbuildem|1 year ago|reply
[+] [-] prerok|1 year ago|reply
[+] [-] jkaptur|1 year ago|reply
Quick feature request: the die-roll is really cool, but can you make a lower-latency version so I can play more games in less time?
[+] [-] igpay|1 year ago|reply
[+] [-] abecedarius|1 year ago|reply
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.
[+] [-] TheDudeMan|1 year ago|reply
[+] [-] kristopolous|1 year ago|reply
The do nothing move is a nice touch
[+] [-] furyofantares|1 year ago|reply
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.
[+] [-] primitivesuave|1 year ago|reply
Link to HN submission: https://news.ycombinator.com/item?id=40653736
[+] [-] varelaz|1 year ago|reply
[+] [-] nico|1 year ago|reply
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
[+] [-] airstrike|1 year ago|reply
[+] [-] gwbas1c|1 year ago|reply
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.
[+] [-] BWStearns|1 year ago|reply
[+] [-] dylanhouli|1 year ago|reply
[+] [-] rmetzler|1 year ago|reply
[+] [-] igpay|1 year ago|reply