tic tac toe | Newbie | | Join Date: Mar 2007
Posts: 29
| | |
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
|  | Moderator | | Join Date: Aug 2008 Location: Leipzig, Germany
Posts: 3,657
| | | re: tic tac toe
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).
|  | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by 1051109210  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 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,
Jos
|  | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
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.
HTH
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by kadghar 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.
HTH There are also winning games while there are still empty cells; you can't represent those games as a binary number by forgetting about those empty cells. Your reasoning is not correct.
kind regards,
Jos
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by JosAH There are also winning games while there are still empty cells; you can't represent those games as a binary number by forgetting about those empty cells... 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. Quote:
Originally Posted by JosAH ... Your reasoning is not correct.
kind regards,
Jos That was rude.
=(
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by kadghar 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.
=( 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,
Jos
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by JosAH Again: you can't represent a (partly completed) game by a binary number; read this link for an explanation.
.... 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: - 001110011 010011101 010101101 010110101
-
011100011 011100101 011110001 100011110
-
101001110 101011010 101100011 101101010
-
101110010 110001101 110001110 110011100
Any idea for a 17th?
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!
Kad
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by kadghar 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:
- 001110011 010011101 010101101 010110101
-
011100011 011100101 011110001 100011110
-
101001110 101011010 101100011 101101010
-
101110010 110001101 110001110 110011100
Any idea for a 17th?
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!
Kad Yep there are 16 possible draws and that page also mentions that number (actuallly another page linked from that page mentions them but that page agrees). Of course 9! is totally wrong and that page also mentions that fact. That page is simply correct.
kind regards,
Jos
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
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. ='(
| | Moderator | | Join Date: Aug 2008 Location: Leipzig, Germany
Posts: 3,657
| | | re: tic tac toe
Quote:
Originally Posted by kadghar that give us:
9 different games in the first move,
... actually, if you consider symmetry, there are only 3.
and for the real game play: Quote:
you win only if your opponent loses.
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by kadghar 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.
Then again, i don't want to trust that page. It has an ugly and grey design. ='( 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,
Jos
| | Moderator | | Join Date: Aug 2008 Location: Leipzig, Germany
Posts: 3,657
| | | re: tic tac toe
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. - | |3| | // most opponents would choose move 2
-
|1|2| | // now you have a 50% chance of winning based on probability
-
| | | |
... provided you play sensibly.
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by JosAH You get those numbers because you keep on playing after one of the players has won... 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. Quote:
Originally Posted by JosAH ...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
... 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.
Kad
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by Dormilich 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)
That's true, If the first player starts in a corner, the second player must play in the center, otherwise, the first player has a 100% of the times winning strategy.
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Here's the quick and dirty Java class I used: -
import java.util.HashSet;
-
import java.util.Set;
-
-
public class TTT {
-
-
private static final String[][] wins= {
-
// row diag1 diag2 column
-
{ "xxx", "x...x...x", "..x.x.x..", "x..x..x"},
-
{ "ooo", "o...o...o", "..o.o.o..", "o..o..o" }
-
};
-
-
private static Set<String>[] games= new Set[9];
-
-
private static char[] board= ".........".toCharArray();
-
-
private static void initialize() {
-
-
for (int i= 0; i < games.length; i++) games[i]= new HashSet<String>();
-
}
-
-
private static boolean win(String s, int level) {
-
-
for (int i= 0; i < wins[level&1].length; i++)
-
if (s.replaceAll(wins[level&1][i], "").length() < 9)
-
return true;
-
-
return false;
-
}
-
-
private static boolean register(int level) {
-
-
String s= new String(board);
-
-
if (games[level].contains(s))
-
return true;
-
-
games[level].add(s);
-
-
return win(s, level);
-
}
-
-
private static void play(char p, int level) {
-
-
if (level == board.length) return;
-
-
for (int i= 0; i < board.length; i++)
-
if (board[i] == '.') {
-
board[i]= p;
-
if (!register(level))
-
play((char)('x'+'o'-p), level+1);
-
board[i]= '.';
-
}
-
}
-
-
private static int wins(int level) {
-
-
int total= 0;
-
for (String s : games[level])
-
if (win(s, level)) total++;
-
-
return total;
-
}
-
-
private static void report() {
-
-
for (int i= 0; i < games.length; i++)
-
System.out.println(i+": "+games[i].size()+"/"+wins(i));
-
}
-
-
public static void main(String[] args) {
-
-
initialize();
-
play('x', 0);
-
report();
-
}
-
}
kind regards,
Jos
ps. if you change line #39 to 'return false;' you get the numbers you posted, i.e. it keeps on generating further board configurations even after a win situation.
| | Moderator | | Join Date: Mar 2006
Posts: 1,103
| | | re: tic tac toe
Original Question comment:
For each move pick a random number (1-9)
If square is filled, keep on picking a random number until you get a square that isn't filled.
Move there.
kadghar:
I assume you were talking 126 configuration for a finished game? Quote:
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.
No. What about this game?
XOO
XOO
XXX
or this game:
XOX
XXO
XOO
Of those 16 draws you can play them in 5!*4! = 120 * 24 = 2880 ways each
16 * 2880 = 46080 different draw games.
On another note, for games that end in n moves there are m ways to play them ->
5 = 3! * 2! = 12
6 = 3! * 3! = 36
7 = 4! * 3! = 144
8 = 4! * 4! = 576
9 = 5! * 4! = 2880
Calculating number of games that end in 5 moves.
There are 8 possible lines. There are 6C2 = 15 possibilities for the opponennts moves. 12 ways to play this game
8 * 15 * 12 = 1440
You forgot the 3 ways to place the first mark.
I wonder how to calculate how many different configurations/games there are, ignoring symmetries.
1st move 9 - 3
2nd move 72 - 12
3rd move 504 - 66
4th move 3024 - ???
...
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by jkmyoung kadghar:
I assume you were talking 126 configuration for a finished game?
...
Of those 16 draws you can play them in 5!*4! = 120 * 24 = 2880 ways each
16 * 2880 = 46080 different draw games. No, the 126 are all the possible combinations in the 9th move, 52 was the number with only one three-in-a-row. Yes, you're right, it shouldn't be 52, but a greater number, because of the cases that have 2 'three-in-a-row' in the last move (i think they're 22, one in each intersection, but 6 in the center, and 3 in each corner).
But as Jos said, that's not a sufficient argument to get the probabilities. because one three-in-a-row doesnt mean it was won exactly this turn. It could have been won the turn before and this turn's move didnt completed another three-in-a-row. Quote:
Originally Posted by jkmyoung ...
On another note, for games that end in n moves there are m ways to play them ->
5 = 3! * 2! = 12
6 = 3! * 3! = 36
7 = 4! * 3! = 144
8 = 4! * 4! = 576
9 = 5! * 4! = 2880
... Yes, that's true, but we weren't counting the ways the games can be played, but the different boards you can have, which is not necessarily right. Counting ways to play the games is always a good alternative.
When you see a finished board there is no difference if you played in the upper-right corner the first X and in the lower down corner the second X, or vice versa. Then, those are two different 'ways to play the game' but they lead you to the very same board. The right way to calculate that number is using combinations:
nCr: 9C5 (5 Xs in 9 spaces) or 9C4 (4 O's in 9 spaces). Both numbers are 126.
Another problem comes with the cases where you have a trinary system, with O's, X's and blank spaces. Those possible boards are the one i showed in my first table. And it's quite right. The problem is that many of those boards will never be reached, since the game could be finished in some turn before.
That's why Jos' code tries to simulate every possible game, and end it when you have the first 'three-in-a-row'. That's why it seems logical for me.
| | Moderator | | Join Date: Mar 2006
Posts: 1,103
| | | re: tic tac toe
Quote:
Yes, that's true, but we weren't counting the ways the games can be played
?? I thought we were discussing both. Counting only finished configurations is like saying thousands of chess games are the same because then end with the same end configuration, eg a Rook and King checkmating a king.
# of winning configurations/games in 5 moves: 120/1440
I concur with 120; Jos' other calculation appears to be a mistake.
Storing all the possible configurations seems to be overwork to me. Ensuring that each game is connected to other games through possible moves seems overly complicated.
Looking back, this is wrong for 7, 8 and 9: Quote:
5 = 3! * 2! = 12
6 = 3! * 3! = 36
7 = 4! * 3! = 144
8 = 4! * 4! = 576
9 = 5! * 4! = 2880
why? because I forget to take into account that the game may have ended on one of these moves, so the last move must make a line. This is however correct to get to configurations where there is no winner at that point.
Correction to # of ways to win a game with particular configuration:
7 = 3*3! * 3! = 108
8 = 4! * 3 * 3! = 432
9 - 1 line: 3 * 4! * 4! = 1728
9 - 2 lines: 1 * 4! * 4! = 576
I get 22 double line configurations as well.
Counting the # of winning games for 6-8 moves seems to be much harder.
| | Expert | | Join Date: Apr 2007 Location: Mexico City
Posts: 1,155
| | | re: tic tac toe
Quote:
Originally Posted by jkmyoung Counting the # of winning games for 6-8 moves seems to be much harder. the ones with 9 moves are quite hard too, since you dont know exactly if they were won in some turn before... i'd say those are the hardest.
As i said before. counting boards is not necessary right. Counting ways of playing the game sounds easier to find out when a game was finished... but then again, you cannot find that number using combinations or permutations. You'll have to simulate all possible games, because of the already-won cases.
About Jos' numbers, i havn't checked them, it's a lot of work (, i'm lazy) and i haven't make myself time to do it (but i will). Anyway, the main idea of his code seems fine, doesn't it?
| | Expert | | Join Date: Mar 2007
Posts: 10,611
| | | re: tic tac toe
Quote:
Originally Posted by kadghar About Jos' numbers, i havn't checked them, it's a lot of work (, i'm lazy) and i haven't make myself time to do it (but i will). Anyway, the main idea of his code seems fine, doesn't it? Look at the 'register' and 'win' methods: if a current board configuration is a winning configuration the 'play' method stops, otherwise it keeps playing.
kind regards,
Jos
|  |
Similar Algorithms / Advanced Math bytes | | |  /bytes/about
We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights.
Get the best answers to your questions from over 226,471 network members.
|
