Both sides of the Kalah board are the same, with only the numbers of the

slots

changing. You can write a little code to make it so that your players

need not

be concerned with this minor difference. Here’s an example from Adam

Shelly:

```
#Adapter class - rotates the board so that player's Kalah is always 6
class KalahPlayer < Player
def choose_move
n = (@side==KalahGame::TOP) ? 7 : 0
@board = @game.board
@board = @board.rotate n
return get_move + n
end
#simulate a move
def simulate board,i
b = board.dup
stones,b[i]=b[i],0
while stones > 0
i = 0 if (i+=1) >12
b[i]+=1
stones-=1
end
if (0..5)===i and b[i]==1
b[6]+= (b[i]+b[opposite(i)])
b[i]=b[opposite(i)]=0
end
b
end
def opposite n
12-n
end
end
```

As the comment suggests, this is the Adapter Design Pattern at work.

Player’s

original interface is that choose_move() should return a correct move

regardless

of which side of the board it is playing from. KalahPlayer changes that

interface to having get_move() see the board as if it was playing from

the

bottom and return only moves in that range.

This change is accomplished by defining a choose_move() the rotates a

board and

adds an offset to the players selected move, if needed. When the player

is on

the bottom, the board is rotated 0 and the selected move is added to an

offset

of 0, resulting in no change either way. When the player is on the top

though,

the board the player sees is flipped 180 degrees (rotate(7)), and the

player’s

move is raised by 7 to place it on the proper side of the board.

This class also defines the helper method simulate(), which given a

board and a

move, will return the resulting board. This makes searching a lot

easier for

the subclasses.

The above code makes use of a rotate() method we haven’t seen. It comes

from a

few helpers added to Array:

```
#Some helpers in Array
class Array
def rotate n
a =dup
n.times do a << a.shift end
a
end
def sum
inject(0){|s,e|s+=e}
end
#choose randomly between all items with given value
def random_index value
n=rand(find_all{|e|e==value}.size)
each_with_index{|e,i| return i if e==value and (n-=1)<0 }
end
end
```

The first method is the rotate() call used earlier. It’s pretty simple,

just

returning a copy of the Array with the elements cycled in a circular

fashion the

requested number of times.

I really hope sum() needs no introduction by this point, as it’s

probably the

most popular helper method in Ruby Q. solutions. It just returns a

summation

of all elements in the Array.

Finally, random_index() selects a random element equal to the passed in

value.

In other words, if an Array contained [1, 2, 3, 2] and you call

random_index(2),

you have a 50/50 chance of getting 1 or 3 (the indices of the 2s)

returned.

Now we’re ready to actually build a player:

```
#Tries to find the biggest increase in score for a turn
class DeepScoreKalahPlayer < KalahPlayer
def get_move
best_move(@board)
end
def best_move board
possible_scores = (0..5).map{|i| score_for(board,i)}
possible_scores.index(possible_scores.max)
end
#find the increase in score if we make move m
def score_for board,m
return -100 if board[m]<1 #flag invalid move
b, taketurn = board,true
while taketurn
taketurn = ((b[m]+m)%14 == 6) #will we land in kalah?
b = simulate b,m
m = best_move(b) if taketurn
end
b[6]-board[6] #how many points did we gain?
end
end
```

This is a fairly uncomplicated player with the idea of find the most

points I

can get with my move. Remember, get_move() is the adapted interface, so

that’s

where we start. All it does is call best_move() passing in the current

board.

Now best_move() walks all possible moves calculating how many points we

would

earn by making the move. When it has that information, it selects the

highest

point move and returns to index for that slot.

The last piece of this puzzle is score_for(). Given a board and a move,

it

returns how many points you would gain by making the move. This is

slightly

complicated, because a move ending in the Kalah allows us to move again.

That

is handled with recursion by simply calling best_move() again on the new

board.

When that’s all done, subtracting the Kalah we started with from the

Kalah we

ended with gives us the points gained by the move or moves.

Adam doesn’t quit there though, there’s another player that inherits

from this

one. Let’s take a look:

```
#Tries to find the biggest increase in score for a turn
#subtracts opponent's possible score
class APessimisticKalahPlayer < DeepScoreKalahPlayer
MaxDepth = 3
def get_move
@level=0
best_move(@board)
end
def best_move board
return super(board) if (@level > MaxDepth)
@level+=1
possible_scores = (0..5).map{|i|
score_for(board,i) - worst_case(simulate(board,i))
}
@level-=1
possible_scores.random_index(possible_scores.max)
end
#biggest score the opponent can get on this board
def worst_case board
worst = 0
opp_board = board.rotate 7
6.times {|i|
s = score_for(opp_board, i)
worst = s if worst < s
}
worst
end
end
```

This is a famous gaming algorithm known as a Minimax Search. The idea

is that

everyone is always going to make their best move, both you and your

opponent.

Given that, we want to find your best (or maximum) choice, but we also

need to

consider the opponent’s best response. We want to chose the path that

minimizes

the opponent’s potential to get back at us. The father ahead we can

look in

this fashion, the more intelligent of a decision we can make.

The code above is very similar to the last player we examined. The main

new

element here is worst_case(), which is just a tool to find the

opponent’s best

move (worst for us). Beyond that, you can see that get_move() and

best_move()

have been reworked to search down to a constant depth. In this case, a

depth of

3 was chosen. Of course we want to look as deep as possible, but memory

and

execution time can make deeper searches unrealistic.

Note that best_move() now subtracts worst_case() from score_for(), so

the

opponent’s response move is weighted against our own. This may even

yield

negative values for moves, because the opponent has a response better

than the

move we made.

If you want to take Minimax deeper, you have to cut down the work it has

to do.

A common technique is Alpha-Beta Pruning, which allows you to skip large

portions of the move tree in your search. I’m not going to show the

code here,

but be sure to look at David B.'s code which walks father along

this path.

My thanks to all the players who always share such interesting solutions

with

us.

Tomorrow I have a real treat for all you Ruby Q. fans, our first prize

awarding competition…