In this
post, I showcase a bare-bones point-and-click implementation of the classic
board Reversi (also called Othello*) in the R programming language. R is
typically used for more serious, statistical endeavors, but it works reasonably
well for more playful projects. Building a classic game like this is an
excellent high-school level introduction to programming, as well as a good basis
for building and testing game AI.
If you want
to skip ahead and just play Reversi in R right away, download this .R file:
open it either base R or Rstudio, set the working directory to the location where you
downloaded to, and run the file with source("Reversi Functions.r") . This will print some basic play instructions
for you.
The starting
configuration shown here is just one of many possible configurations that the
code can handle. This program can allow for many variants in play including board
dimensions, 'walls' that block capture, and three or more players. These will be
shown in a later post.
When
running, the active player can click on any of the legal spaces, marked with red
circles, to place a stone and capture any enemy pieces that are sandwiched
between the newly placed piece and already-placed pieces.
The board
after the first couple moves by "B"lack and "W"hite are shown
in the next two figures.
The game continues
until neither player has a legal move, which usually, but not always, occurs when
the board is filled or when there is only one player's pieces remaining.
Before we
look at the user-defined functions for this game, let's review a few important
functions in base R.
paste(x, collapse="") # Takes a vector of string variables and converts
it into a single string with nothing between each of the original strings.
strsplit(x,"")[[1]]
# Takes a single string and converts it into a vector of string variables of
one character each.
plot.new();
plot.window(xlim=.. ylim=) # Clears the existing plot, if any, and creates a
new one with the given x and y limits.
locator(1) # Takes
the first mouse click on a plot and extracts the x and y coordinates on the
plot.
The paste
and strsplit functions are useful for passing information about the stones to
each other in a convenient way. String manipulation is slow, so it's not the most
computationally efficient way to handle this, but it's also not the biggest
task. If I had to run thousands of games quickly, say, for machine learning purposes,
I would have used a more sophisticated method here.
The locator
function is what makes it possible to play this game with a mouse instead of a
keyboard, which makes the whole thing much more enjoyable to play and test.
The game instead
is broken down into as many user-defined functions as is convenient. In other
words, the programming is modular, it's broken down into many small
modules. Modularity makes it easier to modify the program and prevents errors
that may occur from having to change the same code in multiple locations. Furthermore,
with good function names, the whole process is easier to read by a human.
We start
with setup.board, which establishes the board dimensions, starting pieces,
number of players, and any walls or gaps. For this demo, let's stick with the classic
Othello setup.
setup.board =
function(style = "Basic Othello")
{
if(style == "Basic Othello")
{
board =
matrix(".",nrow=8,ncol=8)
board[4,4] = "W"
board[5,5] = "W"
board[4,5] = "B"
board[5,4] = "B"
}
}
A piece can be
placed anywhere that a 'sandwich' can be made. To determine this, we first need
a function to 'look' in a given direction from a given position on a board. For
example, looking from b1 in the southeast direction on this board…
…should
produce a 'look' of ''B,W,W,space,space,space". The look.to function takes in a board, position,
and direction, and returns the state of the board spaces from that location
outwards until it hits the edge of the board. The direction dictates the values
of xstep and ystep, which in turn dictate which spaces are the board are examined.
the order The look.around function calls look.to from a given position for all
eight directions, one at a time.
look.to = function(board, position, direction)
{
…
if(direction == "N"){
xstep = 0; ystep = -1}
if(direction == "NE"){ xstep = 1; ystep = -1}
…
if(direction == "W"){
xstep = -1; ystep = 0}
if(direction == "NW"){ xstep = -1; ystep = -1}
## Do this until we look to the edge of the board
while(this_x > 0
& this_x <= ncol(board) &
this_y >
0 & this_y <= nrow(board))
{
### Record the stone (or space) and xy coords at the observed
location
stones =
c(stones, board[this_y,this_x])
xlist =
c(xlist, this_x)
ylist =
c(ylist, this_y)
### Iterate the observed location based on the selected
direction
this_x = this_x
+ xstep
this_y = this_y
+ ystep
}
…
}
The
legal.look function takes a given sequence of stones from the look.to function,
and determines if a given player (a single character of a string) can make a sandwich
in that direction. It returns the number of sandwiched enemy stones.
Note that the code considers any character other a blank space ( . ) or a wall (
# ) to be an enemy stone, allowing this code to work with 3+ players.
The legal.directions
function calls legal.look for each direction and returns the list of directions
in which a capture can be made by the given player by placing at the given
position. The which.legal function calls legal.direction for each empty position
on the board to determine which, if any, spaces a given player may place on the
board.
legal.look = function(player, look)
{
…
Nenemies = 0
enemy_chain = TRUE
while( Nenemies < length(look) & enemy_chain)
{
### Examine a space, if it's anything except
### the current player's piece, a space, or a wall, it's an
enemy piece
examined_piece =
look[Nenemies + 1]
if(examined_piece
%in% c(player,"."," ","#"))
{ ## If it's not an
enemy, stop looking
enemy_chain =
FALSE
}
else
{ ## If it is an enemy, iterate and keep
looking
Nenemies =
Nenemies + 1
}
}
### If there are enemy pieces all the way to the end of the
board
### Return 'no capture'.
if(Nenemies == length(look)){return(0)}
## There must be an allied piece at immediately after the enemy
pieces
## If so, return the number of pieces that can be captured
examined_piece = look[Nenemies + 1]
if(examined_piece == player)
{
return(Nenemies)
}
### Otherwise return 'no capture'
return(0)
}
The
plot.game function takes a board state, active player, and possibly the matrix
of legal moves, and draws this information as a plot.
plot.game =
function(board,player,legal_board=NULL,showlegal=TRUE)
The
play.move function checks if a move at the position is legal by a given player
on the given board. If it is, it updates the board by placing a stone for player
at position and makes all the appropriate captures. It returns the new board
state. It uses look.to and legal.look to determine which stones on the board to
change.
play.move = function(board, this_player, position)
The play game
is the main function that that runs the whole game.
play.game = function(board=NA)
It takes in
mouse clicks with locator and converts them into positions on the board (note
the inversion of the y-axis).
mouseclick = locator(1)
input_x = round(mouseclick$x)
input_y = round(mouseclick$y)
input_y = nrow(board) - input_y + 1
Before using
that click, it first checks if that it maps to a space on the board, and that the
space is a legal move by the given player. (If there is no legal move, it will
accept any click as a 'pass', and move to the next player)
while(all(board == new_board) & any(legal_board == TRUE))
if(input_x > 0 & input_x <= Nx & input_y > 0
& input_y <= Ny)
legal_board = which.legal(board, current_player)
if(legal_board[input_y,input_x])
If the move
is legal, it calls play.move to update the board and cycles to the next player.
new_board =
play.move(board,this_player=current_player,position=c(input_y,input_x))
current_player = player_list[ 1 + (player_idx %% Nplayers)]
It continues
to do this until no player has a legal move, or there are no spaces left on the
board. After which it returns the board state as a matrix as well as the score
of each player.
while( any(board ==
".") & players_skipped < length(player_list))
print(table(board))
return(board)
Finally, you
can use setup.board to create a non-standard board and use it in play.game. For
example, a 4x10 board can be created and used with the "Othello Wide"
style.
board = setup.board("Othello Wide")
play.game(board)
* There
are slight differences between the commercial version Othello, and the public domain
game Reversi. Also, the name Othello is trademarked by Mattel.
In Part 2, found here, we make real graphics and improve support for custom and multiplayer boards.
No comments:
Post a Comment