Show HN: Probabilistic Tic-Tac-Toe • Hacker News Board

Re: Show HN: Probabilistic Tic-Tac-Toe

#101

Post by furyofantares » Tue, Jun 11, 2024, 3:22 PM UTC

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.

Re: Show HN: Probabilistic Tic-Tac-Toe

#102

Post by barfbagginus » Tue, Jun 11, 2024, 3:32 PM UTC

maweki wrote: post #90

barfbagginus wrote: post #61

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

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#103

Post by orlp » Tue, Jun 11, 2024, 3:55 PM UTC

Labo333 wrote: post #98

yshui wrote: post #87

Earlier quoted context omitted.

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: W(S, A) = P(good) * (1 - W(S_good)) + P(bad) * (1 - W(S_bad)) + (1 - P(good) - P(bad)) * (1 - W(S)) And obvisouly: W(S) = max(W(S, A), foreach A in Actions) max() is troublesome, but we can replace it with a >= sign: W…

There is an easier way to solve each recursion! I just wrote a blog post on it: https://louisabraham.github.io/articles/probabilistic-tic-ta...

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#104

Post by [deleted] » Tue, Jun 11, 2024, 5:13 PM UTC

Labo333 wrote: post #98

yshui wrote: post #87

Earlier quoted context omitted.

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: W(S, A) = P(good) * (1 - W(S_good)) + P(bad) * (1 - W(S_bad)) + (1 - P(good) - P(bad)) * (1 - W(S)) And obvisouly: W(S) = max(W(S, A), foreach A in Actions) max() is troublesome, but we can replace it with a >= sign: W…

There is an easier way to solve each recursion! I just wrote a blog post on it: https://louisabraham.github.io/articles/probabilistic-tic-ta...

[deleted]

Re: Show HN: Probabilistic Tic-Tac-Toe

#105

Post by Labo333 » Tue, Jun 11, 2024, 5:18 PM UTC

orlp wrote: post #103

Labo333 wrote: post #98

Earlier quoted context omitted.

There is an easier way to solve each recursion! I just wrote a blog post on it: https://louisabraham.github.io/articles/probabilistic-tic-ta...

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

oh RIGHT. Gotta fix it

Re: Show HN: Probabilistic Tic-Tac-Toe

#106

Post by eaplmx » Tue, Jun 11, 2024, 11:53 PM UTC

antognini wrote: post #46

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

I 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/

Re: Show HN: Probabilistic Tic-Tac-Toe

#107

Post by kevindamm » Wed, Jun 12, 2024, 12:59 AM UTC

jedberg wrote: post #100

kevindamm wrote: post #89

Earlier quoted context omitted.

Yes, I think we're saying the same thing. Your second sentence is exactly what I mean by lookup table.

But you don't need a lookup table. The square itself would literally have that printed on it. No percentages.

but that is what a lookup table is -- something to turn the number on the die into the happy/meh/sad outcome. There would be nine on each card.

Re: Show HN: Probabilistic Tic-Tac-Toe

#108

Post by primitivesuave » Wed, Jun 12, 2024, 2:00 AM UTC

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#109

Post by primitivesuave » Wed, Jun 12, 2024, 3:30 AM UTC

barfbagginus wrote: post #61

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

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.

Re: Show HN: Probabilistic Tic-Tac-Toe

#110

Post by primitivesuave » Wed, Jun 12, 2024, 3:35 AM UTC

janwillemb wrote: post #17

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

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