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

Re: Show HN: Probabilistic Tic-Tac-Toe

#111

Post by yshui » Wed, Jun 12, 2024, 1:53 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...

Yep, this is what I ended up doing as well! With how the game generate boards, the player that goes first always have a ~5% advantage. Since players switch hands each around they should have 50% win rate if both play optimally.

In practice, playing against author's AI I barely get ~60% win rate (small caveat, I count ties as 0.5 to both players). What about yours?

Edit: nvm I saw you did the same with ties.

Re: Show HN: Probabilistic Tic-Tac-Toe

#112

Post by JKCalhoun » Wed, Jun 12, 2024, 8:32 PM UTC

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.

That'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

Re: Show HN: Probabilistic Tic-Tac-Toe

#113

Post by fsckboy » Sun, Jun 16, 2024, 4:11 PM UTC

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?

i went up 8-1 and 6 games later it was 8-7