Tic-tac-toe game has one simple rule:
the player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row, in a 3x3 grid, wins the game.
So what's the best move to start? Well, I don't know.
But I can use a computer to get an answer.
(I lied. I do know)
The tools I've used:
The computer played 10000 "random" games and saved them in a database.
Actually the games are not plain random games. I've embedded the tic-tac-toe rule in the program. The program chooses a random move only if the player can't win or can't block the opponent. The players are considered to be intermediate level tic-tac-toe players.
Even though we've played random games, the best moves dominate over the good and bad ones, and just by counting the results we get our answer:
0 | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8
As we can observe,
corners lead to more victories. Yeah baby!
And what's the more
defensive opening for tic-tac-toe?
(by
defensing I mean a move that leads to more ties)
Hmm, it's the center (cell 4). Interesting.
Here's something way cooler: since we have a knowledge base for tic-tac-toe games, we can query the database for a specific game state and find out
the next best move for any player!
An example: let's say that
X (player 1) chose the upper-left corner (cell 0).
X | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8
Now what
O (player 2) should choose? A move that gives the fewer wins for player
X has good odds to be the next best move, right? OK, lets run a query and see...
Hey, statistically,
the center (cell 4) causes fewer wins for player 1, thus it's the next best move for player 2. Neat!
Play on-line
Tic-Tac-Toe
You prefer to play with code? Here's what I've crafted:
import random
import sqlite3
def CanTicTacToe(player, cells):
return cells.count(player) == 2 and cells.count(0) == 1
def SelectWinningMove(player, board):
# Horizontal
if CanTicTacToe(player, board[0:3]): return board[0:3].index(0) + 0
if CanTicTacToe(player, board[3:6]): return board[3:6].index(0) + 3
if CanTicTacToe(player, board[6:9]): return board[6:9].index(0) + 6
# Vertical
if CanTicTacToe(player, board[0::3]): return board[0::3].index(0) * 3 + 0
if CanTicTacToe(player, board[1::3]): return board[1::3].index(0) * 3 + 1
if CanTicTacToe(player, board[2::3]): return board[2::3].index(0) * 3 + 2
# Diagonal
if CanTicTacToe(player, board[0::4]): return board[0::4].index(0) * 4
if CanTicTacToe(player, board[2::2][:3]):
return board[2::2][:3].index(0) * 2 + 2
return -1
def SelectRandomMove(player, board):
moves = [i for i in range(0, len(board)) if board[i] == 0]
if len(moves) == 0: return -1
return moves[random.randint(0, len(moves) - 1)]
# ([0,1,2,3,4,5,6,7,8], result)
def PlayRandomGame():
result = 0 # tie
board = [0] * 9
moves = []
player = 0
while True:
player = player % 2 + 1 # X: 1, O: 2:
move = SelectWinningMove(player, board)
if move >= 0: # victory
moves.append(move)
result = player
break
# Opponent can win?
opponent = player % 2 + 1
move = SelectWinningMove(opponent, board)
if move < 0: # nope, so ...
move = SelectRandomMove(player, board)
if move >= 0:
moves.append(move)
board[move] = player
else: # no more moves; tie
break
return (moves, result)
def SaveRandomGames(fileName, n=10000):
conn = sqlite3.connect(fileName)
c = conn.cursor()
c.execute('DROP TABLE IF EXISTS games')
c.execute('CREATE TABLE IF NOT EXISTS games ('
'move1 INTEGER, move2 INTEGER, move3 INTEGER,'
'move4 INTEGER, move5 INTEGER, move6 INTEGER,'
'move7 INTEGER, move8 INTEGER, move9 INTEGER,'
'winner INTEGER)')
for _ in xrange(n):
game = PlayRandomGame()
moves = game[0] + [None] * (9 - len(game[0]))
result = game[1]
c.execute('INSERT INTO games VALUES (?,?,?,?,?,?,?,?,?,?)',
moves + [result])
conn.commit()
c.close()
