This just reminded me why I hate output randomness in games. Lost 3 75% in a row
Show HN: Probabilistic Tic-Tac-Toe
81–90 of 113 posts
Re: Show HN: Probabilistic Tic-Tac-Toe
#82Re: Show HN: Probabilistic Tic-Tac-Toe
#83Earlier quoted context omitted.
A D20 would be more than enough, you just put the probabilities of the tiles in terms of 20 digits.
I'm saying if you wanted to mimic the happy/meh/sad faces on the die in this game you would need multiple dice. But since all of the percentages are in 5% increments yes a D20 is all you would need. I suggest a lookup table for the players who are uncomfortable or uninterested in doing the percentage division in their head, and the sum of the two lower partitions. But you've got me thinking you could probably also ha…
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
Re: Show HN: Probabilistic Tic-Tac-Toe
#84Earlier quoted context omitted.
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.
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
Re: Show HN: Probabilistic Tic-Tac-Toe
#85Earlier quoted context omitted.
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?
The current code for board generation is as follows:
var neutralChances = Random.Range(1, MaxNeutralChances + 1);
square.GoodChances = Random.Range(MinGoodChances, 20 - neutralChances);
square.BadChances = 20 - (square.GoodChances + neutralChances);
I guess I didn't include ties in that little blurb I wrote up, but the real results of my 10k trials were around 5:1:11.5 (lose:tie:win) for the AI vs random actor.
Would love to see your AI when it's done! Please shoot me an email if you want. My email is in my profile / in the site footer.
Re: Show HN: Probabilistic Tic-Tac-Toe
#86[dead]
Re: Show HN: Probabilistic Tic-Tac-Toe
#87Harder 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(S) >= (W(S, A), forall A in Actions)
And then we can expand W(S, A) and move W(S) in each of the inequalities to the left hand side. After all that we will have a bunch of linear inequalities which can be optimized with linear programming. I think the objective would just be:
maximize minimize W(empty_board)
Re: Show HN: Probabilistic Tic-Tac-Toe
#88A new rule could be to make a neutral roll prevent the enemy to play that square for one turn (unless it's the last square).
Re: Show HN: Probabilistic Tic-Tac-Toe
#89Earlier quoted context omitted.
I'm saying if you wanted to mimic the happy/meh/sad faces on the die in this game you would need multiple dice. But since all of the percentages are in 5% increments yes a D20 is all you would need. I suggest a lookup table for the players who are uncomfortable or uninterested in doing the percentage division in their head, and the sum of the two lower partitions. But you've got me thinking you could probably also ha…
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.
Re: Show HN: Probabilistic Tic-Tac-Toe
#90Montecarlo 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?