How can i program this game based on probability? like for first move 1/9 chances second would be1/8 chances and so forth? or where can i look into. ive googled around and i dont think i can find wht im lookin for
-
-
for a 3x3 square there are only very few losing moves, otherwise the game will always end with a draw (unless you make non-forcing move or ignore a thread). -
Probabilities don't buy you much; for every move collect the empty cells and uniformly randomly select one of them. Chances are high that the player that uses that 'strategy' (mind the quotes) loses (almost) every game.
Another approach is: consider the board as a trinary nine digit number (e.g. 0 == empty, 1 == player A, 2 == player B). A valid move maps a number to another number, e.g. a first move could be described as M(0) = 10000, i.e. a peg is put in the cell in the middle.
If you jot down all pairs (x, M(x)) that lead to a winning, or best game, you can form a polynomial P(x) that plays a perfect game of tic-tac-toe. A simple Lagrange process will give you that (huge) polynomial ;-)
kind regards,
JosComment
-
There are, 126 possible games, obtained with COMB(9,4) or COMB(9,5).
At the end of the game, you'll have a binary nine digit number (0 for player A; 1 for player B), e.g. 111010001 will be a winning case for A.
Writing down this 126 possible games can be done easily in Excel. Just write the binaries from 0 to 511 (you can start in 31, the first case with 5 ones), and keep the numbers with 5 ones in them, those are your 126 possible games.
Now you have to check which ones are 'winning' numbers.
In those cases where both win... well lets say 1/2 of the times Player A wins first and 1/2 Player B wins first.... but that's just an 'i have no idea' assumption.
HTHComment
-
those games with 'empty cells' are represented by all the games that share the 'allready filled' ones. e.g.
if you have a winning game 111212020
it means its going to 'finish' like one of the following:
111212221
111212122
This means, the probability of 111212020 <-- this game, is 2/126
This is why im assuming the games that end with 2 winners are won 1/2 of the times by each player.
That was rude.
=(Comment
-
Again: you can't represent a (partly completed) game by a binary number; read this link for an explanation.
I don't understand why you perceive my previous remark as being rude: your reasoning was wrong and I noticed it; no more, no less; no hard feelings from my side about it; tic-tac-toe is just a game.
kind regards,
JosComment
-
No, you can't.
But you can represent a partly completed game, by all its possible completed games, after it's already won. Check my previous post. There's an example of a uncomplete-already won game. Which can be taken to any of the two 'complete-games' after it.
Anyway, to obtain the right probability, yes, its necessary to use a trinary sistem, but not as the page you suggested uses it.
About that page:
46080 possible draw games?!?!?!?!
i found 16:
Any idea for a 17th?Code:001110011 010011101 010101101 010110101 011100011 011100101 011110001 100011110 101001110 101011010 101100011 101101010 101110010 110001101 110001110 110011100
362880 possible games?? thats ridiculous, it'll assume that each one of the 9 marks are different, but each nought is the same as anyother, thats why, there are comb(9,5) = comb(9,4) = 126 possible games! Only 126, which can be easy obtained in Excel, not 9!
KadComment
-
Comment
-
Ok,
This is what i'll do then,
I'll check one by one all then numbers from 0 to 19682 in trinary, since we can always make a fast-simple code.
i'll only consider those that have less than 6 ones and less than 5 twos, and the difference between the number of ones and twos is less than two.
that give us:
9 different games in the first move,
72 in the second move,
252 in the third,
756 in the fourth,
1260 in the fifth,
1680 in the sixth,
1260 in the seventh,
630 in the eighth and
126 in the ninth.
Of those possible games, there's no 3-in-a-row before the 5th move, and:
120 have only one 3-in-a-row in the 5th move,
296 have only one 3-in-a-row in the 6th move,
528 have only one 3-in-a-row in the 7th move,
336 have only one 3-in-a-row in the 8th move,
52 have only one 3-in-a-row in the 9th move and
16 have zero 3-in-a-row in the 9th move.
I didnt consider the ones that have more than one 3-in-a-row, because that means they have been already won in some move before.
This sum give us 1348 possible games. So the probabilities are like this:
win in the 5th turn: 8.9%
win in the 6th turn: 21.96%
win in the 7th turn: 39.17%
win in the 8th turn: 24.93%
win in the 9th turn: 3.86%
Draw: 1.19%
And i have the list of all those numbers to prove it!!!
About the page:
8*3!*6*5 = 1440 <--- for ending in the fifth move?
even while thinking that all marks are different, the first player would have to chose between 8 lines, then he'll have 2 ways to place the 2nd mark, and then 1way to place the last one., the second player, well yes, he'll have 6 and 5;
that'll be 8*2!*6*5 = 480...
Then again, i don't want to trust that page. It has an ugly and grey design. ='(Comment
-
You get those numbers because you keep on playing after one of the players has won; if you don't do that you get:
move#: games/wins
0: 9/0
1: 72/0
2: 252/0
3: 756/0
4: 1260/180
5: 1440/210
6: 1080/562
7: 310/182
8: 54/50
In that page they count the game, say, 1, 2, 3 different from 3, 2, 1 (same board outcome but difference sequence).
kind regards,
JosComment
-
to put the discussion back to the original intention.... all those statistics will not win you a game (i.e. tictactoe based on probability will in most real scenarios lead you to a loss)
to not lose a game, you have to play (doesn't matter who is first)
the centre-of-edge opening doesn't contain a no-loss-on-second-move move, but you can force a draw.Code:|x| | | | |o| | | | | |
... provided you play sensibly.Code:| |3| | // most opponents would choose move 2 |1|[B]2[/B]| | // now you have a 50% chance of winning based on probability | | | |
Comment
-
May be the correct syntax for that table would be 'boards' instead of 'games'. I did tried to remove the already won games in the second table, by using the 'only one 3-in-a-row' filter, but i see that's not enough to guarantee you're removing all the already won games. I'll think of a way.
What comes to my mind now is that the ones in the 5th move are right.
In the 6th move i should only keep the ones won by player B... and i have no idea what to do for the 7th, 8th or 9th move. I'll make me some time latter to think about it.
Seems reasonable, but that 180 in the 5th move gave me some doubts, since i only found 120 trinary numbers with 4 zeros, 3 ones and 2 twos that have a 'valid' 3-in-a-row. I'll check that out latter.
Thanks Jos.
KadComment
Comment