[HN Gopher] Show HN: Probabilistic Tic-Tac-Toe
___________________________________________________________________
Show HN: Probabilistic Tic-Tac-Toe
Author : igpay
Score : 152 points
Date : 2024-06-10 16:40 UTC (6 hours ago)
(HTM) web link (www.csun.io)
(TXT) w3m dump (www.csun.io)
| netcraft wrote:
| all I see is a dark grey square? using Firefox on mac
|
| Got the same in chrome but it eventually loaded
| rendall wrote:
| Me too. Android Chrome and Firefox.
| rendall wrote:
| I tried it again and after the loading bar it just went black
| again. I waited a bit but nothing happened. Android Chrome.
| Twirrim wrote:
| Worked for me eventually on Firefox / Linux. Definitely has a
| slow start on first load.
| igpay wrote:
| Thanks for that, I added a loading bar. It should be visible
| now if you refresh the page.
| legohead wrote:
| 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!
| gwbas1c wrote:
| 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.
| BWStearns wrote:
| Middle square is actually pretty good. Solid odds of the
| opponent giving you a layup with a bad break.
| jkaptur wrote:
| 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?
| igpay wrote:
| Thanks! I've added a fast forward button to the top left so
| that you can play faster.
| mbroshi wrote:
| 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
| dylanhouli wrote:
| Really cool, lost two games in a row, finally won my third one
| after the computer got extremely unlucky.
| henry_pulver wrote:
| This is fantastic!
|
| The dice roll animation is :chefkiss:
| eevilspock wrote:
| _> 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
| abecedarius wrote:
| 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.
| TheDudeMan wrote:
| Or a pie chart.
| abecedarius wrote:
| Doesn't have stable positions.
| janwillemb wrote:
| Nice! And irritating! I would make it a lot faster though. It
| takes so much time waiting for the animations to finish.
| JKCalhoun wrote:
| 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?
| igpay wrote:
| 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.
| zachmu wrote:
| 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?
| SamBam wrote:
| 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.
| omoikane wrote:
| 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.
| igpay wrote:
| That's good feedback, thanks. I've added a fast forward button
| to the top left.
| wongarsu wrote:
| 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.
| rmetzler wrote:
| I was wondering if I maybe experienced a bug. Do you shortcut
| drawn games when neither player can win?)
| igpay wrote:
| Yes, those should go straight to a "Tie" result.
| rmetzler wrote:
| 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.
| btbuildem wrote:
| 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.
| prerok wrote:
| That's how the AI seems to play it. :)
| igpay wrote:
| 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"
| orlp wrote:
| 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.
| pvillano wrote:
| WRT to computing an exact solution, something something markov
| chains, transition matrices, eigenvalues. I think it is
| tractable
| orlp wrote:
| 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.
| pvillano wrote:
| 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
| orlp wrote:
| If it were just solely :) / :( then it is a freshman's
| exercise in expectiminimax.
| hammock wrote:
| >Harder for humans
|
| IDK if it's just me, but I went 6-0. Is something wrong with
| the computer player logic?
| orlp wrote:
| The OP mentioned that the AI they programmed is using a
| simple heuristic.
| spywaregorilla wrote:
| 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.
| spacemanspiff01 wrote:
| Wouldn't you also have to take into account the probability
| of the following moves also being successful and giving you a
| win?
| orlp wrote:
| > 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.
| CSMastermind wrote:
| This is a small thing but I really wish it would draw a line
| through the three in a row when you get one.
| wilgertvelinga wrote:
| Offline multiplayer over bluetooth would be a great addition!
| nico wrote:
| 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
| airstrike wrote:
| Unity per the logo on the loading screen
| antognini wrote:
| 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
| spywaregorilla wrote:
| 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?
| educasean wrote:
| Okay. This has a lot more depth than it initially appeared. What
| a great twist on a simple game!
| bagels wrote:
| It's an interesting game, but the AI is making really bad plays.
| varelaz wrote:
| It doesn't require AI to solve the game. It's possible to do with
| probabilistic theory, dynamic programming and game theory
| (minimax)
| aidenn0 wrote:
| 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).
| pncnmnp wrote:
| 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.
| ziofill wrote:
| it's a bit slow with all the animation... but nice idea
| livrem wrote:
| 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?
| kevindamm wrote:
| 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!
| barfbagginus wrote:
| 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
| jzw8833 wrote:
| 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.
___________________________________________________________________
(page generated 2024-06-10 23:00 UTC)