Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Probabilistic Tic-Tac-Toe

csun.io

Post reply on HN
Print view View original

61–70 of 113 posts

Re: Show HN: Probabilistic Tic-Tac-Toe

#61

Post by barfbagginus »

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#62

Post by jzw8833 »

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.

Re: Show HN: Probabilistic Tic-Tac-Toe

#63

Post by pvillano »

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 _

Re: Show HN: Probabilistic Tic-Tac-Toe

#64

Post by spywaregorilla »

orlp wrote: post #58
spywaregorilla wrote: post #48

Earlier quoted context omitted.

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 gree…

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#65

Post by spywaregorilla »

spacemanspiff01 wrote: post #51
spywaregorilla wrote: post #48

Earlier quoted context omitted.

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 gree…

Wouldn't you also have to take into account the probability of the following moves also being successful and giving you a win?

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.

Re: Show HN: Probabilistic Tic-Tac-Toe

#66

Post by jedberg »

hammock wrote: post #42
orlp wrote: post #27

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 pos…

>Harder for humans IDK if it's just me, but I went 6-0. Is something wrong with the computer player logic?

What happens when you play against yourself?

Re: Show HN: Probabilistic Tic-Tac-Toe

#67

Post by jedberg »

kevindamm wrote: post #60
livrem wrote: post #59

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!

A D20 would be more than enough, you just put the probabilities of the tiles in terms of 20 digits.

Re: Show HN: Probabilistic Tic-Tac-Toe

#68

Post by Laremere »

igpay wrote: post #32
JKCalhoun wrote: post #19

Earlier quoted context omitted.

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?

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?

Post reply on HN