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.
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?
MaxNeutralChances and MinGoodChances are both set to 6 in the release build. Note that one chance is equal to one face of the die, so 5%. Also, this overload of Random.Range() has an inclusive min value but an exclusive max value.
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?
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.
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:
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?
I think you have an error in the equation defining V(s).
You have component n_c * V(s) for the 'nothing happened' case, but I don't think that's correct. If you rolled that nothing happens the turn still passes to your opponent, so I think it should be n_c * V'(s).
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.
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.
> 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.
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.
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.
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!
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.
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.
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"
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.
I'm not 100% sure, but I think it didn't display the outcome of the dice in this case. And it would be nice to have some hint that shows that this game ends in a Tie.
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
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.
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
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?
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).
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:
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.
> 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?
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.