1 year ago
#385971
Display name
Finding all of the outcomes for a Tic-Tac-Toe game
I recently decided to type up some code in C sharp that determines the outcomes for a Tic-Tac-Toe game.
In my code, I received the results:
Total number of games:77088
214 tied
36533 x wins
40341 o wins
(following the rules of x goes first)
However, my results are vastly contradictory to the results on Google.
According to Wikipedia: Tic-tac-toe there are 138 different game outcomes with 91 won by x, 44 won by o and 3 tied
Most other websites say there are either 9!(352,880) or 3^9(19,683) ways to fill the board.
Through my personal experience and basic testing, I know there are many more than 3 ways to tie a game which invalidates the results presented by Wikipedia. Also, the pure math proposed by other websites witch use 9! and 3^9 fail to take into account games that are ended early.
So, am I mistaken, is everyone else mistaken?
My research: A game cannot be won in less than 5 turns. A game has finished once a victor has been found. A victor is determined by a match of 3 vertically, horizontally or diagonally across any 3 cells.
My testing code : c sharp - ran in Unity
void Start()
{
int x=0;
int o=0;
int t=0;
int victor;
for (int i = 0; i < 9; i++)
{//turn 1 - no win
for (int b = 0; b < 9; b++)
{//turn 2 - no win
if (b == i) continue;
for (int c = 0; c < 9; c++)
{//turn 3 - no win
if (c == i || c == b) continue;
for (int d = 0; d < 9; d++)
{//tunr 4 - no win
if (d == i || d == b || d == c) continue;
for (int e = 0; e < 9; e++)
{//turn 5 - possible winner
if (e == i || e == b || e == c || e == d) continue;
TicTacToeGame ticTacToeGame = new TicTacToeGame();
ticTacToeGame.SetMove(i);
ticTacToeGame.SetMove(b);
ticTacToeGame.SetMove(c);
ticTacToeGame.SetMove(d);
victor = ticTacToeGame.SetMove(e);
if (victor > 0)
{
Debug.Log(ticTacToeGame.GetGame());
Debug.Log("The victor is " + (victor == 1 ? 'X' : (victor == 2 ? 'O' : ' ')));
switch (victor)
{
case 0:
t++;
break;
case 1:
x++;
break;
case 2:
o++;
break;
}
continue;
}
for (int f = 0; f < 9; f++)
{
if (f == i || f == b || f == c || f == d || f == e) continue;
TicTacToeGame ticTacToeGame6 = new TicTacToeGame();
ticTacToeGame.SetMove(i);
ticTacToeGame.SetMove(b);
ticTacToeGame.SetMove(c);
ticTacToeGame.SetMove(d);
ticTacToeGame.SetMove(e);
victor = ticTacToeGame.SetMove(f);
if (victor > 0)
{
Debug.Log(ticTacToeGame.GetGame());
Debug.Log("The victor is " + (victor == 1 ? 'X' : (victor == 2 ? 'O' : ' ')));
switch (victor)
{
case 0:
t++;
break;
case 1:
x++;
break;
case 2:
o++;
break;
}
continue;
}
for (int g = 0; g < 9; g++)
{
if (g == i || g == b || g == c || g == d || g == e || g==f) continue;
TicTacToeGame ticTacToeGame7 = new TicTacToeGame();
ticTacToeGame.SetMove(i);
ticTacToeGame.SetMove(b);
ticTacToeGame.SetMove(c);
ticTacToeGame.SetMove(d);
ticTacToeGame.SetMove(e);
ticTacToeGame.SetMove(f);
victor = ticTacToeGame.SetMove(g);
if (victor > 0)
{
Debug.Log(ticTacToeGame.GetGame());
Debug.Log("The victor is " + (victor == 1 ? 'X' : (victor == 2 ? 'O' : ' ')));
switch (victor)
{
case 0:
t++;
break;
case 1:
x++;
break;
case 2:
o++;
break;
}
continue;
}
for (int h = 0; h < 9; h++)
{
if (h == i || h == b || h == c || h == d || h == e || h == f || h==g) continue;
TicTacToeGame ticTacToeGame8 = new TicTacToeGame();
ticTacToeGame.SetMove(i);
ticTacToeGame.SetMove(b);
ticTacToeGame.SetMove(c);
ticTacToeGame.SetMove(d);
ticTacToeGame.SetMove(e);
ticTacToeGame.SetMove(f);
ticTacToeGame.SetMove(g);
victor = ticTacToeGame.SetMove(h);
if (victor > 0)
{
Debug.Log(ticTacToeGame.GetGame());
Debug.Log("The victor is " + (victor == 1 ? 'X' : (victor == 2 ? 'O' : ' ')));
switch (victor)
{
case 0:
t++;
break;
case 1:
x++;
break;
case 2:
o++;
break;
}
continue;
}
for (int j = 0; j < 9; j++)
{
if (j == i || j == b || j == c || j == d || j == e || j == f || j == g || j==h) continue;
TicTacToeGame ticTacToeGame9 = new TicTacToeGame();
ticTacToeGame.SetMove(i);
ticTacToeGame.SetMove(b);
ticTacToeGame.SetMove(c);
ticTacToeGame.SetMove(d);
ticTacToeGame.SetMove(e);
ticTacToeGame.SetMove(f);
ticTacToeGame.SetMove(g);
ticTacToeGame.SetMove(h);
victor = ticTacToeGame.SetMove(j);
Debug.Log(ticTacToeGame.GetGame());
Debug.Log("The victor is " + (victor == 1 ? "X" : (victor == 2 ? "O" : "Tied")));
switch (victor)
{
case 0:
t++;
break;
case 1:
x++;
break;
case 2:
o++;
break;
}
continue;
}
}
}
}
}
}
}
}
}
Debug.Log(t + " tied\n" + x + " x\n" + o + " o");
Debug.Log("Total : " + (t + x + o));
}
private class TicTacToeGame
{
int[] gameBoard = new int[9];
bool turn = true;
int victor = 0;
bool isActive = false;
public TicTacToeGame()
{
isActive = true;
}
public int SetMove(int i)
{
if (!isActive) return victor;
if (i < 0 || i > 8) throw new Exception("Invalid move : " + i);
gameBoard[i] = turn ? 1 : 2;
turn = !turn;
victor = CheckVictory();
if (victor!=0)
{
isActive = false;
}
return victor;
}
private int CheckVictory()
{
if(IsEqual(gameBoard[0], gameBoard[1], gameBoard[2]))
{
return gameBoard[0];
}
if (IsEqual(gameBoard[3], gameBoard[4], gameBoard[5]))
{
return gameBoard[3];
}
if (IsEqual(gameBoard[6], gameBoard[7], gameBoard[8]))
{
return gameBoard[6];
}
if (IsEqual(gameBoard[0], gameBoard[3], gameBoard[6]))
{
return gameBoard[6];
}
if (IsEqual(gameBoard[1], gameBoard[4], gameBoard[7]))
{
return gameBoard[1];
}
if (IsEqual(gameBoard[2], gameBoard[5], gameBoard[8]))
{
return gameBoard[2];
}
if (IsEqual(gameBoard[0], gameBoard[4], gameBoard[8]))
{
return gameBoard[0];
}
if (IsEqual(gameBoard[6], gameBoard[4], gameBoard[2]))
{
return gameBoard[6];
}
return 0;
}
private bool IsEqual(int a, int b, int c)
{
if (a == 0 || b == 0 || c == 0) return false;
return a == b && a == c;
}
public string GetGame()
{
return string.Format("{0}|{1}|{2}\n" +
"-----\n" +
"{3}|{4}|{5}\n" +
"-----\n" +
"{6}|{7}|{8}",
IntToChar(gameBoard[0]),
IntToChar(gameBoard[1]),
IntToChar(gameBoard[2]),
IntToChar(gameBoard[3]),
IntToChar(gameBoard[4]),
IntToChar(gameBoard[5]),
IntToChar(gameBoard[6]),
IntToChar(gameBoard[7]),
IntToChar(gameBoard[8]));
}
private char IntToChar(int i)
{
return i == 1 ? 'X' : (i == 2 ? 'O' : ' ');
}
}
Update :: After reading some comments, I realized that there was a flaw in my code as it wasn't checking all outcomes but now that should be rectified. One issue that is not addressed would be rotations or reflections but if this data is to be used in practice then rotations and reflections should be included otherwise the computer will have to rotate and reflect every move before making a decision which may take as long or longer than running through an array of outcomes.
Either way, my data is still widely contradictory to results found online.
c#
tic-tac-toe
0 Answers
Your Answer