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

91–100 of 113 posts

Re: Show HN: Probabilistic Tic-Tac-Toe

#91

Post by JohannesH »

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?

I was thinking the same ø, but does it work with the neutral field and changing players in the mix?

Re: Show HN: Probabilistic Tic-Tac-Toe

#92

Post by JohannesH »

JohannesH wrote: post #91
maweki wrote: post #90

Earlier quoted context omitted.

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

I was thinking the same ø, but does it work with the neutral field and changing players in the mix?

I mean there will be non-zero chance that the game could go on forever.

Re: Show HN: Probabilistic Tic-Tac-Toe

#93

Post by orlp »

pvillano wrote: post #84
orlp wrote: post #47

Earlier quoted context omitted.

If it were just solely :) / :( then it is a freshman's exercise in expectiminimax.

it turns out you don't need anything more than minimax for the general case Here's my solution https://github.com/pvillano/probabalistic-tic-tac-toe

I think this fails to take into account that your opponent can also roll 'meh', making it your turn again.

Re: Show HN: Probabilistic Tic-Tac-Toe

#94

Post by napsternxg »

Nice 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/ ), 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

Re: Show HN: Probabilistic Tic-Tac-Toe

#96

Post by gwbas1c »

BWStearns wrote: post #7
gwbas1c wrote: post #6

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.

Middle square is actually pretty good. Solid odds of the opponent giving you a layup with a bad break.

The odds on each square change every game. I didn't realize that at first.

Re: Show HN: Probabilistic Tic-Tac-Toe

#97

Post by yshui »

yshui wrote: post #87
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…

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…

Turns out linear programming is not fast... Takes about 90 minutes to find the optimal solution for any board configuration.

Re: Show HN: Probabilistic Tic-Tac-Toe

#98

Post by Labo333 »

yshui wrote: post #87
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…

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#99

Post by Labo333 »

pvillano wrote: post #34
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…

WRT to computing an exact solution, something something markov chains, transition matrices, eigenvalues. I think it is tractable

I just did: https://louisabraham.github.io/articles/probabilistic-tic-ta...

Re: Show HN: Probabilistic Tic-Tac-Toe

#100

Post by jedberg »

kevindamm wrote: post #89
RheingoldRiver wrote: post #83

Earlier quoted context omitted.

The 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

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.
Post reply on HN