CareerCup

let's say you take a one or two dimensional array for the positions; wouldn't all the empty positions be valid moves after that? I think this is about a logical minimax implementation. (logical moves rather than valid?)

It looks to me that we can solve this question with a tree where every node can have up to 9 branches. Lets assume O starts first.

- The root node represents an empty board.
- The second level will have 9 edges and nodes since there are 9 places that we can use for O (or X, whichever starts first.) Each node will have (row,column) indices.
- X plays the next time. Since one of the board cells is occupied, we can now have 8 places to move.
...
This goes until we have only one node.

Once we created the tree, we list the paths by using DFS. There will be 9! different paths. Since 9 is a constant, The complexity is constant too. But if we have different version of the game with a bigger board than complexity will be O(N!) which is O(2^N)

Please correct me if I am wrong or suggest a better algorithm.

I created a programmatic solution for the case. It uses almost full tree of field combination and don't seem to sweet cause is't bruteforce.

package test;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class TicTacToe {
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		System.out.println("Game processing started.");

		Level init = Level.getInitialLevel(true);
		int c = init.getGamesCount();

		System.out.println("\n---------------------------------------");
		System.out.println("Games count for X-starter player = " + c);
		System.out.println("Games count for both players = " + c * 2);

		System.out.println("---------------------------------------");
		System.out.println("Total field object created: "
				+ Field.totalFieldsCount);
		System.out.println("Total level object created: "
				+ Level.totalLevelsCount);
		System.out.println("Note: 9! is " + fact(9));
		System.out.println("Total game processing time: "
				+ (System.currentTimeMillis() - start) / 1000.0 + " s.");

	}

	static class Field {
		static long totalFieldsCount = 0;

		static int MAX_FIELD_CELLS = 9;

		BitSet cells = new BitSet(MAX_FIELD_CELLS);
		// true means cell is empty
		BitSet emptyCells = new BitSet(MAX_FIELD_CELLS);

		public Field() {
			emptyCells.flip(0, MAX_FIELD_CELLS);
		}

		public Field(Field prevLevField) {
			totalFieldsCount++;
			cells = (BitSet) prevLevField.cells.clone();
			emptyCells = (BitSet) prevLevField.emptyCells.clone();
		}

		public String getCellContentsForToString(int idx) {
			if (emptyCells.get(idx)) {
				return "_ ";
			} else {
				return cells.get(idx) ? "X " : "O ";
			}
		}

		public String toString() {
			StringBuilder buff = new StringBuilder();
			buff.append(getCellContentsForToString(0));
			buff.append(getCellContentsForToString(1));
			buff.append(getCellContentsForToString(2));
			buff.append("\n");
			buff.append(getCellContentsForToString(3));
			buff.append(getCellContentsForToString(4));
			buff.append(getCellContentsForToString(5));
			buff.append("\n");
			buff.append(getCellContentsForToString(6));
			buff.append(getCellContentsForToString(7));
			buff.append(getCellContentsForToString(8));
			buff.append("\n");

			return buff.toString();

		}

		boolean putVal(int idx, boolean player) {
			if (!emptyCells.get(idx)) {
				throw new IllegalArgumentException(String.format(
						"Cell with idx %s is not empty.", idx));
			}
			emptyCells.set(idx, false);
			cells.set(idx, player);

			return checkIsGameOver();
		}

		boolean makeMove(BitSet foreignEmptySections, boolean player) {
			int clearIdx = foreignEmptySections.nextSetBit(0);
			foreignEmptySections.set(clearIdx, false);
			return putVal(clearIdx, player);
		}

		private boolean checkIsGameOver() {
			if (getEmptySectionsCount() == 0) {
				return true;
			}
			if (checkLineIsWinLine(0, 1, 2) || checkLineIsWinLine(3, 4, 5)
					|| checkLineIsWinLine(6, 7, 8)
					|| checkLineIsWinLine(0, 3, 6)
					|| checkLineIsWinLine(1, 4, 7)
					|| checkLineIsWinLine(2, 5, 8)
					|| checkLineIsWinLine(0, 4, 8)
					|| checkLineIsWinLine(2, 4, 6)) {
				System.out.println(toString());
				return true;
			}
			return false;
		}

		boolean checkLineIsWinLine(int i1, int i2, int i3) {
			if (!emptyCells.get(i1) && !emptyCells.get(i2)
					&& !emptyCells.get(i3)) {
				if (cells.get(i1) && cells.get(i2) && cells.get(i3)) {
					return true;
				}
				if (!cells.get(i1) && !cells.get(i2) && !cells.get(i3)) {
					return true;
				}
			}
			return false;
		}

		public int getEmptySectionsCount() {
			return emptyCells.cardinality();
		}

		public BitSet getEmptyCells() {
			return (BitSet) emptyCells.clone();
		}
	}

	static class Level {
		int levelDepth = 0;

		List<Field> fields = new ArrayList<Field>(9);
		boolean currentPlayer;

		Field prevLevField;

		public static Level getInitialLevel(boolean player) {
			Field prevLevField = new Field();
			return new Level(prevLevField, player, 0);
		}

		public int getGamesCount() {
			return makeMove();
		}

		public static int totalLevelsCount = 0;

		public Level(Field prevLevField, boolean currentPlayer, int levelDepth) {
			totalLevelsCount++;
			this.levelDepth = levelDepth;
			this.currentPlayer = currentPlayer;
			this.prevLevField = prevLevField;
			int emptyCells = prevLevField.getEmptySectionsCount();

			for (int i = 0; i < emptyCells; i++) {
				fields.add(new Field(prevLevField));
			}
		}

		int makeMove() {
			// System.out.println("level depth = " + levelDepth);
			BitSet prevLevFieldEmptyCells = prevLevField.getEmptyCells();
			int gamesCounter = 0;
			for (Field field : fields) {
				// System.out.println(field);
				boolean gameOver = field.makeMove(prevLevFieldEmptyCells,
						currentPlayer);
				// System.out.println(field);
				if (gameOver) {
					// System.out.print("0");
					gamesCounter++;
					continue;
				}
				Level nextLevel = new Level(field, !currentPlayer,
						levelDepth + 1);
				gamesCounter += nextLevel.makeMove();
			}
			return gamesCounter;
		}
	}

	private static int fact(int in) {
		if (in == 0) {
			return 1;
		}
		return in * fact(--in);
	}

}

output:

---------------------------------------
Games count for X-starter player = 255168
Games count for both players = 510336
---------------------------------------
Total field object created: 549945
Total level object created: 294778
Note: 9! is 362880
Total game processing time: 7.512 s.

I designed recursive algo up to either win case or board is full. Plus I counted the interesting for me statistics. It turned out that starter has 2 times more winning situations to choose from. Processing time: 0.3 sec.

unsigned int g_ValidMoves;
unsigned int g_FirstWon;
unsigned int g_SecondWon;

enum ETicTacCellValue
{
eEmpty = 0,
eTic,
eTac
};

class CTicTacBoard
{
public:
CTicTacBoard()
{
m_bGameIsOver = false;
m_winner = eEmpty;

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
m_Board[i][j] = eEmpty;
}

CTicTacBoard(CTicTacBoard& board)
{
m_bGameIsOver = board.m_bGameIsOver;
m_winner = board.m_winner;

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
m_Board[i][j] = board.m_Board[i][j];
}

bool IsValidMove(unsigned int row, unsigned int col)
{
return (!m_bGameIsOver && row < 3 && col < 3 && m_Board[row][col] == eEmpty);
}

bool SetMove(unsigned int row, unsigned int col, ETicTacCellValue value)
{
bool bResult = false;

if (IsValidMove(row, col) && value != eEmpty && m_Board[row][col] == eEmpty)
{
m_Board[row][col] = value;
CheckIfGameIsOver();
bResult = true;
}

return bResult;
}

bool IsGameOver(ETicTacCellValue& winner)
{
winner = m_winner;
return m_bGameIsOver;
}

private:
void CheckIfGameIsOver()
{
if ((m_Board[0][0] == eTic && m_Board[0][1] == eTic && m_Board[0][2] == eTic) ||
(m_Board[1][0] == eTic && m_Board[1][1] == eTic && m_Board[1][2] == eTic) ||
(m_Board[2][0] == eTic && m_Board[2][1] == eTic && m_Board[2][2] == eTic) ||
(m_Board[0][0] == eTic && m_Board[1][0] == eTic && m_Board[2][0] == eTic) ||
(m_Board[0][1] == eTic && m_Board[1][1] == eTic && m_Board[2][1] == eTic) ||
(m_Board[0][2] == eTic && m_Board[1][2] == eTic && m_Board[2][2] == eTic) ||
(m_Board[0][0] == eTic && m_Board[1][1] == eTic && m_Board[2][2] == eTic) ||
(m_Board[2][0] == eTic && m_Board[1][1] == eTic && m_Board[0][2] == eTic))
{
m_winner = eTic;
m_bGameIsOver = true;
}
else if ((m_Board[0][0] == eTac && m_Board[0][1] == eTac && m_Board[0][2] == eTac) ||
(m_Board[1][0] == eTac && m_Board[1][1] == eTac && m_Board[1][2] == eTac) ||
(m_Board[2][0] == eTac && m_Board[2][1] == eTac && m_Board[2][2] == eTac) ||
(m_Board[0][0] == eTac && m_Board[1][0] == eTac && m_Board[2][0] == eTac) ||
(m_Board[0][1] == eTac && m_Board[1][1] == eTac && m_Board[2][1] == eTac) ||
(m_Board[0][2] == eTac && m_Board[1][2] == eTac && m_Board[2][2] == eTac) ||
(m_Board[0][0] == eTac && m_Board[1][1] == eTac && m_Board[2][2] == eTac) ||
(m_Board[2][0] == eTac && m_Board[1][1] == eTac && m_Board[0][2] == eTac))
{
m_winner = eTac;
m_bGameIsOver = true;
}
}

private:
ETicTacCellValue m_Board[3][3];
bool m_bGameIsOver;
ETicTacCellValue m_winner;
};

void MakeNextMove(CTicTacBoard* pBoard, ETicTacCellValue currPlayer)
{
ETicTacCellValue winner;
ETicTacCellValue nextPlayer;

if (pBoard->IsGameOver(winner))
{
if (winner == eTic)
g_FirstWon++;
else
g_SecondWon++;
}
else
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
if (pBoard->IsValidMove(i, j))
{
g_ValidMoves++;
CTicTacBoard newBoard(*pBoard);
if (currPlayer == eTic)
nextPlayer = eTac;
else if (currPlayer == eTac)
nextPlayer = eTic;
else
{
printf("\nUnexpected error! Empty player passed in MakeNextMove.\n");
return;
}

newBoard.SetMove(i, j, currPlayer);
MakeNextMove(&newBoard, nextPlayer);
}
}
}
}

void TicTacGame()
{
CTicTacBoard Boards[3][3];

g_ValidMoves = 0;
g_FirstWon = 0;
g_SecondWon = 0;

// Lets start allways from eTic
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
Boards[i][j].SetMove(i, j, eTic);
MakeNextMove(&(Boards[i][j]), eTac);
}

printf("\nNumber of all Valid moves = %d\t(100%%)\n", g_ValidMoves);
printf("\nNumber of Non win cases = %d\t(%d%%) \n", g_ValidMoves - g_FirstWon - g_SecondWon,
100 * (g_ValidMoves - g_FirstWon - g_SecondWon) / g_ValidMoves);
printf("\nNumber of First player won = %d\t(%d%%)\n", g_FirstWon, 100 * g_FirstWon / g_ValidMoves);
printf("\nNumber of Second player won = %d\t(%d%%)\n", g_SecondWon, 100 * g_SecondWon / g_ValidMoves);
}

Number of all Valid moves = 549936 (100%)

Number of Non win cases = 340848 (61%)

Number of First player won = 131184 (23%)

Number of Second player won = 77904 (14%)

I think a way to make the algorithm faster but still using DFS is to limit the first move to just one out three: (0,0), (1,0), (1,1). Analogously, the second move can be limited to the above (or below) diagonal positions. All the other possible initial moves are generated from these by simple rotation/mirror. This would save in both space and time complexity since we are cutting the graph at the root. The total cost would be then 3*5*(7!)=75600, with the caveat to add rotated/mirrored moves when printing the total set of available moves.