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

41–50 of 113 posts

Re: Show HN: Probabilistic Tic-Tac-Toe

#41

Post by orlp »

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

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#42

Post by hammock »

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?

Re: Show HN: Probabilistic Tic-Tac-Toe

#43

Post by abecedarius »

TheDudeMan wrote: post #25
abecedarius wrote: post #16

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

Or a pie chart.

Doesn't have stable positions.

Re: Show HN: Probabilistic Tic-Tac-Toe

#44

Post by orlp »

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?

The OP mentioned that the AI they programmed is using a simple heuristic.

Re: Show HN: Probabilistic Tic-Tac-Toe

#45

Post by pvillano »

orlp wrote: post #41
pvillano wrote: post #34

Earlier quoted context omitted.

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

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

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#47

Post by orlp »

pvillano wrote: post #45
orlp wrote: post #41

Earlier quoted context omitted.

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

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

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#48

Post by spywaregorilla »

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

Re: Show HN: Probabilistic Tic-Tac-Toe

#50

Post by rmetzler »

igpay wrote: post #36
rmetzler wrote: post #24

I was wondering if I maybe experienced a bug. Do you shortcut drawn games when neither player can win?)

Yes, those should go straight to a "Tie" result.

I'm not 100% sure, but I think it didn't display the outcome of the dice in this case. And it would be nice to have some hint that shows that this game ends in a Tie.
Post reply on HN