from Hacker News

Show HN: Probabilistic Tic-Tac-Toe

by igpay on 6/10/24, 4:40 PM with 106 comments

• by janwillemb on 6/10/24, 6:22 PM

  Nice! And irritating! I would make it a lot faster though. It takes so much time waiting for the animations to finish.

• by orlp on 6/10/24, 7:19 PM

  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.

• by mbroshi on 6/10/24, 5:44 PM

  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

• by livrem on 6/10/24, 10:17 PM

  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?

• by legohead on 6/10/24, 5:28 PM

  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!

• by wongarsu on 6/10/24, 6:23 PM

  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.

• by eevilspock on 6/10/24, 6:07 PM

  > 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

• by cainxinth on 6/11/24, 1:04 PM

  As a longtime XCOM veteran, I am constitutionally opposed to making any game move with less than an 85% chance of success.

• by napsternxg on 6/11/24, 10:19 AM

  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

• by btbuildem on 6/10/24, 7:05 PM

  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.

• by jkaptur on 6/10/24, 5:42 PM

  I love this!

  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?

• by abecedarius on 6/10/24, 6:13 PM

  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.

• by kristopolous on 6/11/24, 12:27 AM

  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

• by furyofantares on 6/11/24, 3:22 PM

  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.

• by primitivesuave on 6/12/24, 2:00 AM

  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

• by varelaz on 6/10/24, 9:39 PM

  It doesn't require AI to solve the game. It's possible to do with probabilistic theory, dynamic programming and game theory (minimax)

• by nico on 6/10/24, 8:04 PM

  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

• by gwbas1c on 6/10/24, 5:30 PM

  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.

• by dylanhouli on 6/10/24, 5:59 PM

  Really cool, lost two games in a row, finally won my third one after the computer got extremely unlucky.

• by rmetzler on 6/10/24, 6:48 PM

  I was wondering if I maybe experienced a bug. Do you shortcut drawn games when neither player can win?)

• by jzw8833 on 6/10/24, 10:44 PM

  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.

• by eastoeast on 6/11/24, 2:35 AM

  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

• by zeroonetwothree on 6/11/24, 2:37 AM

  This just reminded me why I hate output randomness in games. Lost 3 75% in a row

• by pncnmnp on 6/10/24, 9:50 PM

  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.

• by magicalhippo on 6/11/24, 1:11 AM

  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/

• by pvillano on 6/10/24, 11:10 PM

  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 _

• by ismailmaj on 6/11/24, 6:27 AM

  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).

• by CSMastermind on 6/10/24, 7:39 PM

  This is a small thing but I really wish it would draw a line through the three in a row when you get one.

• by henry_pulver on 6/10/24, 6:01 PM

  This is fantastic!

  The dice roll animation is :chefkiss:

• by educasean on 6/10/24, 9:31 PM

  Okay. This has a lot more depth than it initially appeared. What a great twist on a simple game!

• by bagels on 6/10/24, 9:34 PM

  It's an interesting game, but the AI is making really bad plays.

• by spywaregorilla on 6/10/24, 9:20 PM

  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?

• by wilgertvelinga on 6/10/24, 7:57 PM

  Offline multiplayer over bluetooth would be a great addition!

• by netcraft on 6/10/24, 5:17 PM

  all I see is a dark grey square? using Firefox on mac

  Got the same in chrome but it eventually loaded

• by aidenn0 on 6/10/24, 9:40 PM

  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).

• by lupire on 6/11/24, 2:15 AM

  Reminds me of Quantum Chess

• by ziofill on 6/10/24, 10:00 PM

  it's a bit slow with all the animation... but nice idea

• by antognini on 6/10/24, 9:05 PM

  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

• by barfbagginus on 6/10/24, 10:43 PM

  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