Pages

Saturday, September 18, 2010

Tic-tac-toe, best move to start?

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()

No comments:

Post a Comment