# Kalah (#58)

**URL:** <https://www.ruby-forum.com/t/kalah-58/66069>\
**Category:** Ruby\
**Created:** [December 15, 2005, 2:42pm UTC](https://www.ruby-forum.com/t/kalah-58/66069 "2005-12-15T14:42:26Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 15, 2005, 2:42pm UTC](https://www.ruby-forum.com/t/kalah-58/66069/1 "2005-12-15T14:42:26Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 15, 2005, 6:55pm UTC](https://www.ruby-forum.com/t/kalah-58/66069/2 "2005-12-15T18:55:09Z")

</div>

There’s nothing like a code review to make you see ways to improve your  
code…  
Based on James description of what #worst\_case is doing I realized I  
could rewrite it in 2 lines:

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

So this function should simply be:  
def worst\_case board  
opp\_board = board.rotate 7  
score\_for(opp\_board,best\_move(opp\_board))  
end

Thanks for runing these always entertaining and educational quizes,  
James.  
-Adam

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 15, 2005, 7:01pm UTC](https://www.ruby-forum.com/t/kalah-58/66069/3 "2005-12-15T19:01:10Z")

</div>

On Dec 15, 2005, at 11:53 AM, Adam S. wrote:

> > ```
> > worst = s if worst < s
> > 
> > ```
> > 
> > move (worst for us).
> 
> So this function should simply be:  
> def worst\_case board  
> opp\_board = board.rotate 7  
> score\_for(opp\_board,best\_move(opp\_board))  
> end

Hey, I like that.

> Thanks for runing these always entertaining and educational quizes,  
> James.

Thanks for giving me something to talk about, Adam. 😉

James Edward G. II