7 ms·
Show HN: Probabilistic Tic-Tac-Toe
- janwillemb 2y agoNice! And irritating! I would make it a lot faster though. It takes so much time waiting for the animations to finish.
- JKCalhoun 2y agoToo 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 2y agoAgreed 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 2y agoI 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?
- Laremere 2y agoCan 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?
- its_ethan 2y agoWhy 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?
- Laremere 2y agoYes, 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.
- its_ethan 2y agoVery cool! Best of luck working on it!
- igpay 2y agoThe current code for board generation is as follows: var neutralChances = Random.Range(1, MaxNeutralChances + 1); square.GoodChances = Random.Range(MinGoodChances, 20 - neutralChances); square.BadChances = 20 - (square.GoodChances + neutralChances); 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.
- JKCalhoun 2y agoThat'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 https://github.com/EngineersNeedArt/Phosphor3D
- SamBam 2y agoAgreed. 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 2y agoAn 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 2y agoThat's good feedback, thanks. I've added a fast forward button to the top left.
- SV_BubbleTime 2y agoYou overdid it. 1x is right at first, but 2x is really fast.
- airstrike 2y ago3x is great
- primitivesuave 2y agoI 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 https://keshav.is/coding/pt3
- henry_pulver 2y agoThis is fantastic! The dice roll animation is :chefkiss:
- netcraft 2y agoall I see is a dark grey square? using Firefox on mac Got the same in chrome but it eventually loaded
- rendall 2y agoMe too. Android Chrome and Firefox.
- rendall 2y agoI tried it again and after the loading bar it just went black again. I waited a bit but nothing happened. Android Chrome.
- Twirrim 2y agoWorked for me eventually on Firefox / Linux. Definitely has a slow start on first load.
- igpay 2y agoThanks for that, I added a loading bar. It should be visible now if you refresh the page.
- legohead 2y agoNeat 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 2y agoTotally 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.
- jkaptur 2y agoI 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 2y agoThanks! I've added a fast forward button to the top left so that you can play faster.
- mbroshi 2y agoBrilliant! 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 https://en.wikipedia.org/wiki/Action_bias
- deleted 2y ago[deleted]
- dylanhouli 2y agoReally cool, lost two games in a row, finally won my third one after the computer got extremely unlucky.
- eevilspock 2y ago> 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 https://en.wikipedia.org/wiki/Matthew_effect
- abecedarius 2y agoNice! 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 2y agoOr a pie chart.
- abecedarius 2y agoDoesn't have stable positions.
- wongarsu 2y agoGreat 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.
- aishaish 2y ago[flagged]
- aishaish 2y ago[flagged]
- rmetzler 2y agoI was wondering if I maybe experienced a bug. Do you shortcut drawn games when neither player can win?)
- btbuildem 2y agoTook 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 2y agoThat's how the AI seems to play it. :)
- igpay 2y agoYes, 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"
- SV_BubbleTime 2y agoI don’t think this is right though. I watched it pick a 70 it didn’t need over a 60 I used to win.
- orlp 2y agoHarder 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 2y agoWRT to computing an exact solution, something something markov chains, transition matrices, eigenvalues. I think it is tractable
- orlp 2y agoUsually 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 2y agoYou'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
- CSMastermind 2y agoThis is a small thing but I really wish it would draw a line through the three in a row when you get one.
- wilgertvelinga 2y agoOffline multiplayer over bluetooth would be a great addition!
- deleted 2y ago[deleted]
- nico 2y agoWhat 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 https://trinket.io/glowscript/a90cba5f40
- airstrike 2y agoUnity per the logo on the loading screen
- antognini 2y agoThis 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 https://www.smbc-comics.com/comic/incomplete
- eaplmx 2y agoI 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/ https://eapl.me/incomplete/
- spywaregorilla 2y agoare 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 2y agoOkay. This has a lot more depth than it initially appeared. What a great twist on a simple game!
- bagels 2y agoIt's an interesting game, but the AI is making really bad plays.
- varelaz 2y agoIt doesn't require AI to solve the game. It's possible to do with probabilistic theory, dynamic programming and game theory (minimax)
- aidenn0 2y agoNumber 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 2y agoFascinating. 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 2y agoit's a bit slow with all the animation... but nice idea
- livrem 2y agoAs 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 2y agoyou 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!
- jedberg 2y agoA D20 would be more than enough, you just put the probabilities of the tiles in terms of 20 digits.
- kevindamm 2y agoI'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.
- RheingoldRiver 2y agoThe 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
- kevindamm 2y agoYes, I think we're saying the same thing. Your second sentence is exactly what I mean by lookup table.
- barfbagginus 2y agoMontecarlo 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
- maweki 2y ago> 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?
- JohannesH 2y agoI was thinking the same ø, but does it work with the neutral field and changing players in the mix?
- JohannesH 2y agoI mean there will be non-zero chance that the game could go on forever.
- barfbagginus 2y agoRead 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.
- jzw8833 2y agoI 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.
- pvillano 2y agoYou 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 _
- kristopolous 2y agoI 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
- magicalhippo 2y agoInteresting 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/ https://quantumtictactoe.com/play/
- lupire 2y agoReminds me of Quantum Chess
- eastoeast 2y agoThis 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
- zeroonetwothree 2y agoThis just reminded me why I hate output randomness in games. Lost 3 75% in a row
- Marciakhan 2y ago[dead]
- ismailmaj 2y agoA 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).
- napsternxg 2y agoNice 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/ 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 https://news.ycombinator.com/item?id=12932183
- cainxinth 2y agoAs a longtime XCOM veteran, I am constitutionally opposed to making any game move with less than an 85% chance of success.
- furyofantares 2y agoSweet! 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 2y agoI 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/ https://keshav.is/coding/pt3/ Link to HN submission: https://news.ycombinator.com/item?id=40653736 https://news.ycombinator.com/item?id=40653736