Sunday, March 10, 2013

Programming Othello / Reversi - Part 1

I dug an old dusty box out of my closet about a week ago.  While sifting through it, I realized that I had stumbled upon several ancient treasures of the past.  One of these treasures was the Nintendo Entertainment System (NES) and the other was the game Othello.  After playing a couple games against Level 4 I had defeated it, but only to be presented with the sinister level 5.  Once you make it to level 5,  there is no time limit, which means the computer has all day to figure out how to beat you.  Conversely, you have all day to sit around and watch yourself lose.  Fun, fun, fun.

Bottom line: I do not like to lose.  So this morning I decided to embark on a journey to a strange new world, to seek out new moves and new predictions, to boldly create an Othello core, like i've never done before!  Did you catch that Star Trek reference?  Of course you did... Nerd.

I decided to rapidly prototype Othello using Python.  The first thing I needed to do was create a board.  A list of lists struck me as the most obvious way to do this:

_black = 0
_white = 1
_board_size = 8

def get_new_board():

    board = []
    for i in xrange(_board_size):
        board.append([None] * _board_size)

    board[3][3] = board[4][4] = _white
    board[3][4] = board[4][3] = _black

    return board

Alright, so I have a board.  I think?  It would be nice if I could see it.

def display_board(board):

    for line in board:
        output_line = ''
        for item in line:
            if item == None:
                output_line += ' '
            else:
                output_line += str(item)
        print output_line

My first attempt at display_board felt awkward and dirty.  Using None as the default cell value turned out to be a bad decision, that made the display function a bit more cumbersome than I had hoped for.  If I forced the default cell value to 0 and made the player values 1 and 2, I could then simplify 'for item in line' and the print statement to a simple print using ''.join.  This means our initial code block will look like this:

_black = 1
_white = 2

...

board.append([0] * _board_size)

Let's see how this feels in terms of display_board:

def display_board(board):

    for line in board:
        print ''.join([str(i) for i in line])

That's a bit cleaner.  So what does the output look like?

00000000
00000000
00000000
00021000
00012000
00000000
00000000
00000000

It's not exactly a hypertexture enhanced scene but I can live with that.  I now have a board that I can see, wouldn't it be nice if I could place a piece on it?  Before I can place a piece for a particular player I will need to check if a single move is valid or get a list of all valid moves.  Because I have a personal interest in being able to enumerate over all possible moves for a particular player / board state, I will enumerate a list of all possible moves for a player.  I am not sure how all the internals will work right now but that's ok, let's just write it out.  We will generate a list of all possible positions, iterate over it and if a move is valid, store the coordinates somewhere:

def get_valid_moves(player, board):

    valid_moves = []

    # enumerate all possible positions
    positions = []
    for i in xrange(0, _board_size):
        for j in xrange(0, _board_size):
            positions.append((i,j))

    # for each position, if the move is valid, store it
    for position in positions:
        if move_is_valid(player, position, board):
            valid_moves.append(position)


It is a brute force approach and all of it should work once move_is_valid is implemented.  Our valid move coordinates are stored in the valid_moves list.  At a glance we can observe that the positions list is really unnecessary overhead, so let's get rid of it.

def get_valid_moves(player, board):

    valid_moves = []

    for i in xrange(0, _board_size):
        for j in xrange(0, _board_size):
            position = (i,j)
            if move_is_valid(player, position, board):
                valid_moves.append(position)

    return valid_moves

Now we need to implement move_is_valid.  I will assume that the reader is familiar with the game and understands what a valid is (don't you?).  Ultimately, we will need to check in 8 different directions from the target position to see if a single move is valid.  For this function, we will need to know which player is playing, the position of interest and the current board.  Let's stub this out:

def move_is_valid(player_piece, position, board):

    if board[position[1]][position[0]] != 2:
        return False

    if has_vertical_up_play(player_piece, position, board):
        return True

    if has_vertical_down_play(player_piece, position, board):
        return True

    if has_horizontal_left_play(player_piece, position, board):
        return True

    if has_horizontal_right_play(player_piece, position, board):
        return True

    if has_diagonal_up_left_play(player_piece, position, board):
        return True

    if has_diagonal_up_right_play(player_piece, position, board):
        return True

    if has_diagonal_down_left_play(player_piece, position, board):
        return True

    if has_diagonal_down_right_play(player_piece, position, board):
        return True

    return False

The first test verifies that the requested position on the board is empty.  The next statements will perform the individual horizontal, vertical and diagonal play tests.  The parameters to each of the has_..._play functions are reasonably redundant and they don't look pretty at all.  However, in this case I prefer to be explicit.  I could have easily created a tuple and stored all the parameters in it, like this:

parameters = (player_piece, position, board)

if has_vertical_up_play(parameters):
        return True

But I feel that would make the has_..._play calls more cryptic, because now you have to look back into the caller to see what was being packed into the list:

# I decided against this
def has_vertical_up_play(parameters):

    player_piece = parameters[0]
    position = parameters[1]
    board = parameters[2]

Now what will our has_vertical_up_play function look like?  This specific function is interested in examining the upwards path from the target position to determine if the play is valid.  We are only interested in walking upwards as long as we encounter opposing pieces.  If we found opposing pieces and did not run off the end of the board and the final piece was our own, then we found a valid play.

def has_vertical_up_play(player_piece, position, board):

    opposing_piece = _opposing_pieces[player_piece] 

    # consume all immediate opposing pieces
    # in the vertical up direction
    found_opposing_piece = False
    for i in xrange(position[1]-1, -1, -1):
        if board[i][position[0]] == opposing_piece:
            found_opposing_piece = True
        else:
            break

    if found_opposing_piece and i >= 0:
        if board[i][position[0]] == player_piece:
            return True 

    return False

Each of the has_..._play functions works in a similar fashion.  I finished implementing all of the has_..._play functions above, so we are ready to start dumping some output.  Let's take our initial board and determine the possible valid moves for white and black:

print 'creating new board'
board = get_new_board()

print 'displaying board'
display_board(board)

print 'valid white moves'
for valid_move in get_valid_moves(_white, board):
    print valid_move
    
print 'valid black moves'
for valid_move in get_valid_moves(_black, board):
    print valid_move

That was pretty easy! But what does our output look like?

creating new board
displaying board
00000000
00000000
00000000
00021000
00012000
00000000
00000000
00000000
valid white moves
(2, 4)
(3, 5)
(4, 2)
(5, 3)
valid black moves
(2, 3)
(3, 2)
(4, 5)
(5, 4)

Hooray, we are beginning to see things come together!  Now, it's time to make some moves.  For each of our has_..._play functions, let's write some new make_..._play functions that will modify the board.  Each of these functions will be expected to return the board that results from the move.  Here is an example of make_vertical_up_play:

def make_vertical_up_play(player_piece, position, board):

    opposing_piece = _opposing_pieces[player_piece] 

    for i in xrange(position[1]-1, -1, -1):
        if board[i][position[0]] == opposing_piece:
            board[i][position[0]] = player_piece
        else:
            break

    return board

For each of these functions, I assumed the play was valid (since I plan to check in advance).  Now we need to glue all of these make_..._play functions together.  I decided to do this in a generic move function.  After all, there should be one (and preferably only one) way to do things, right?

def move(player_piece, position, board):
    ''' Makes the move for the provided player at the provided position on the board.'''

    if has_vertical_up_play(player_piece, position, board):
        board = make_vertical_up_play(player_piece, position, board)

    if has_vertical_down_play(player_piece, position, board):
        board = make_vertical_down_play(player_piece, position, board)

    if has_horizontal_left_play(player_piece, position, board):
        board = make_horizontal_left_play(player_piece, position, board)

    if has_horizontal_right_play(player_piece, position, board):
        board = make_horizontal_right_play(player_piece, position, board)

    if has_diagonal_up_left_play(player_piece, position, board):
        board = make_diagonal_up_left_play(player_piece, position, board)

    if has_diagonal_up_right_play(player_piece, position, board):
        board = make_diagonal_up_right_play(player_piece, position, board)

    if has_diagonal_down_left_play(player_piece, position, board):
        board = make_diagonal_down_left_play(player_piece, position, board)

    if has_diagonal_down_right_play(player_piece, position, board):
        board = make_diagonal_down_right_play(player_piece, position, board)

    board[position[1]][position[0]] = player_piece

    return board

After I implemented each of these functions, it was time to have some fun!  How about enumerating all of the opening moves for black?

print 'creating new board'
board = get_new_board()

print 'displaying board'
display_board(board)

print 'displaying valid black moves'
for valid_move in get_valid_moves(_black, board):
    temp_board = copy.deepcopy(board)
    print 'making move: ', valid_move
    temp_board = move(_black, valid_move, temp_board)
    display_board(temp_board)

A deep copy is required because I am re-using the board between iterations.  During each iteration, I display the move being made and the resulting board.  Let's see what it looks like:

creating new board
displaying board
00000000
00000000
00000000
00021000
00012000
00000000
00000000
00000000
displaying valid black moves
making move:  (2, 3)
00000000
00000000
00010000
00011000
00012000
00000000
00000000
00000000
making move:  (3, 2)
00000000
00000000
00000000
00111000
00012000
00000000
00000000
00000000
making move:  (4, 5)
00000000
00000000
00000000
00021000
00011100
00000000
00000000
00000000
making move:  (5, 4)
00000000
00000000
00000000
00021000
00011000
00001000
00000000
00000000

Now, let's take it to the next level.  Why don't we give our second player a chance?  We will make the first valid black move and then the first valid white move.  Between each move we will display our board.

print 'creating new board'
board = get_new_board()

print 'displaying board'
display_board(board)

# get the first valid black move
black_move = get_valid_moves(_black, board)[0]
temp_board = copy.deepcopy(board)
print 'making black move: ', black_move
temp_board = move(_black, black_move, temp_board)
display_board(temp_board)

# get the first valid white move
white_move = get_valid_moves(_white, temp_board)[0]
print 'making white move: ', white_move
temp_board = move(_white, white_move, temp_board)
display_board(temp_board)

Let's take a look at the results.

creating new board
displaying board
00000000
00000000
00000000
00021000
00012000
00000000
00000000
00000000
making black move:  (2, 3)
00000000
00000000
00010000
00011000
00012000
00000000
00000000
00000000
making white move:  (2, 2)
00000000
00000000
00210000
00021000
00012000
00000000
00000000
00000000

There is still some work left todo in terms of getting an actual game going, but not much.  In part 2, we'll take a look at our first end-to-end game.

2 comments:

Joss82 said...

Fun python fact:
You can initialise your empty board like this:

board = [[None] * _board_size] * _board_size]

Also, why precompute all the possible moves?

Why not compute on the spot, when a move is played, using function is_move_possible() ?

Joss82 said...

What a great, long post!
Thanks for taking the time to write it!