From: Adam Shelly <adam.shelly@...>
Date: 2005-12-13T05:26:15+09:00
Subject: Re: [QUIZ][SOLUTION] Kalah (#58)

------=_Part_1773_7619312.1134419167836
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here are my Kalah Players.
My first trick was to create subclass of Player so that my players are
always playing from bins 0..5.  This got rid of a lot of messy
conditions. It also contains a move simulator.

AdamsPlayers.rb contains some very simple test players, as well as 2
reasonably good players:
DeepScoreKalahPlayer tries to find the biggest gain in points for a
single move, and APessimisticKalahPlayer does the same, but subtracts
the opponent's best possible next move.

AHistoryPlayer.rb contains a player which ranks the results of each
move, and keeps a history.  The idea is that the more it plays, the
less likely it is to choose bad moves.
It stores the history in a Yaml file, which definitely causes a
slowdown as it gets bigger.
That's one thing I'd like to improve if I have time.  I also added a
line to the game engine to report the final score back to the players.
 AHistoryPlayer still works without it, but it's less accurate I
think, since it never records the final result.

None of these players pay much attention to the number of stones
remaining on the opponent's side, which is one factor in why they fail
miserably against Dave's player.  But they do tend to beat Rob's
players.  I'm hoping some more people submit solutions.

Add your players to TestMatch.rb to run them in a roundRobin

-Adam

------=_Part_1773_7619312.1134419167836
Content-Type: application/x-ruby; name=AdamsPlayers.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="AdamsPlayers.rb"


#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

#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

#### Some simple players for testing:
class RemoveRightKalahPlayer < KalahPlayer
	def get_move
			5.downto(0) {|i| return i if @board[i]>0 }
	end
end
class RemoveHighKalahPlayer < KalahPlayer
	def get_move
			myboard = @board[0,6]
			myboard.index(myboard.max)
	end
end
class RemoveRandomHighKalahPlayer < KalahPlayer
	def get_move
			myboard = @board[0,6]
			myboard.random_index(myboard.max)
	end
end
class RemoveLowKalahPlayer < KalahPlayer
	def get_move
			myboard = @board[0,6].select{|e| e>0}
			@board[0,6].index(myboard.min)
	end
end
class RemoveRandomLowKalahPlayer < KalahPlayer
	def get_move
			myboard = @board[0,6].select{|e| e>0}
			@board[0,6].random_index(myboard.min)
	end
end

class ScoreKalahPlayer < KalahPlayer
	def get_move
		possible_scores = (0..5).map{|i| score_for i}
		possible_scores.index(possible_scores.max)
	end
	def score_for i
	  return -1 if @board[i] == 0
		simulate(@board,i)[6]-@board[6]
	end
end


### Some better players

#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                               
			i = best_move(b) if taketurn             
		end
		b[6]-board[6]                                 #how many points did we gain?
	end
	
end


#Tries to find the biggest increase in score for a turn
#subtracts opponent's possible score
class APessimisticKalahPlayer < DeepScoreKalahPlayer
	MaxDepth = 4
	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




------=_Part_1773_7619312.1134419167836
Content-Type: application/x-ruby; name=AHistoryPlayer.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="AHistoryPlayer.rb"

require 'AdamsPlayers.rb'
require 'yaml'

HistoryFile = "ads_khist.yaml"

class WeightedAverage
	def initialize window
		@store = []
		@size = window
	end
	def add item, weight
		@store.shift if @store.size > @size
		@store << [item,weight]
		self
	end
	def ave
	  totweight = 0
		@store.inject(0){|sum,e| totweight+=e.last; sum+e.first*e.last}/(totweight.to_f)
	end
end

class AHistoryKalahPlayer <APessimisticKalahPlayer
	def initialize name
		super	
		@db = load
		@stack=[]
		@myside = nil
	end
	def reset
	  @stack=[]
		@myside = @side
		save HistoryFile
	end
	
	def get_move
		update_scores @board
	  @level=0
		scores = db_fetch(@board)
		if scores.sum !=0   																#there is data in the record
			scorez = scores.zip((0..5).to_a).sort.reverse 
			m = scorez.first.last
		end
		while m && @board[m]==0
			scorez.shift
			m = scorez.first.last if !scorez.empty?
		end
		m = best_move(@board) if !m                       
	  @stack << [@board,m,WeightedAverage.new(16).add(scores[m],2)]
		save HistoryFile if game_almost_over? simulate(@board,m)
		m
	end
	def scoreboard b
	  b[6]-b[13]
	end
	def update_scores board
		reset if @side!=@myside
		score = scoreboard board
		(1..16).each do |n|
			break if n > @stack.size
			oldboard,move,wave = @stack[-n]
			delta = score-scoreboard(oldboard)  		#did we improve or worsen our relative score?
			db_update(oldboard,move,wave.add(delta,1/Math::sqrt(n)).ave)   #record it, weighted by age
		end
	end
	def game_almost_over? board
		!board[0..5].find{|e| e>0} || board[7..12].find_all{|e| e>0}.size <1
	end
	def key board
		(board[0..5]+board[7..12]).join('-')
	end
	def db_fetch board
		@db[key(board)]||=Array.new(6){0}
	end
	def db_update board,move,score
		  a = db_fetch board
			a[move]=score
		end

	def load
		if File.exists? HistoryFile
			File.open(	HistoryFile,"rb+"){|f| YAML::load(f) } 	
		else
			{}
		end
	end
	def save name
		File.open( name, 'wb' ) {|f| f<< (@db.to_yaml)}
	end

	#I added the following lines to the bottom of KalahGame#play_game so that I could get better scoring. 
	  #>> 	top.notify_over [top_score,bottom_score] if top.respond_to? :notify_over
	  #>> 	bottom.notify_over [bottom_score, top_score] if bottom.respond_to? :notify_over
	#This player still works without these.
	def notify_over score
		final = Array.new(14){0}
		final[6]=score[0]
		final[13]=score[1]
		update_scores final
	end

end



------=_Part_1773_7619312.1134419167836
Content-Type: application/x-ruby; name=KalahMatch.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="KalahMatch.rb"

class Player
attr_accessor :name
attr_writer :game, :side

def initialize( name )
@name = name
end

def choose_move
if @side==KalahGame::TOP
(7..12).each { |i| return i if @game.stones_at?(i) > 0 }
else
(0..5).each { |i| return i if @game.stones_at?(i) > 0 }
end
end
end

class HumanPlayer < Player
def choose_move
print 'Enter your move choice: '
gets.chomp.to_i
end
end


class KalahMatch
	def start( p1, p2 )
		puts ''
		puts '========== GAME 1 =========='
		p1_score_1, p2_score_1 = KalahGame.new.play_game( p1, p2 )
				
		if p1_score_1 > p2_score_1
			puts p1.name+' won game #1: '+p1_score_1.to_s+'-'+p2_score_1.to_s
		elsif p2_score_1 > p1_score_1
			puts p2.name+' won game #1: '+p2_score_1.to_s+'-'+p1_score_1.to_s
		else
			puts 'game #1 was a tie: '+p1_score_1.to_s+'-'+p2_score_1.to_s
		end
		
		puts ''
		puts '========== GAME 2 =========='		
		p2_score_2, p1_score_2 = KalahGame.new.play_game( p2, p1 )
		
		if p1_score_2 > p2_score_2
			puts p1.name+' won game #2: '+p1_score_2.to_s+'-'+p2_score_2.to_s
		elsif p2_score_2 > p1_score_2
			puts p2.name+' won game #2: '+p2_score_2.to_s+'-'+p1_score_2.to_s
		else
			puts 'game #2 was a tie: '+p1_score_2.to_s+'-'+p2_score_2.to_s
		end
		
		puts ''
		puts '========== FINAL =========='
		
		p1_final = p1_score_1+p1_score_2
		p2_final = p2_score_1+p2_score_2
		
		if p1_final > p2_final
			puts p1.name+' won the match: '+p1_final.to_s+'-'+p2_final.to_s
		elsif p2_final > p1_final
			puts p2.name+' won the match: '+p2_final.to_s+'-'+p1_final.to_s
		else
			puts 'the match was tied overall : '+p1_final.to_s+'-'+p2_final.to_s
		end
	end	
end

class KalahGame
	NOBODY = 0
	TOP = 1
	BOTTOM = 2

  attr_reader :board, :player_to_move

  def initialize_copy(other_game)
      super
      @board = other_game.board.dup
  end
	
	def stones_at?( i )
		@board[i]
	end
	
	def legal_move?( move )
		( ( @player_to_move==TOP and move >= 7 and move <= 12 ) || 
			( @player_to_move==BOTTOM and move >= 0 and move <= 5 ) ) and @board[move] != 0
	end
	
	def game_over?
		top = bottom = true
		(7..12).each { |i| top = false if @board[i] > 0 }
		(0..5).each { |i| bottom = false if @board[i] > 0 }
		top or bottom
	end
	
	def winner
		top, bottom = top_score, bottom_score
		if top > bottom
			return TOP
		elsif bottom > top
			return BOTTOM
		else
			return NOBODY
		end
	end
	
	def top_score
		score = 0
		(7..13).each { |i| score += @board[i] }
		score
	end
	
	def bottom_score
		score = 0
		(0..6).each { |i| score += @board[i] }
		score
	end
	
	def make_move( move )
		( puts 'Illegal move...' ; return ) unless legal_move?( move )
		
		stones, @board[move] = @board[move], 0
		
		pos = move+1
		while stones > 0
			pos+=1 if( (@player_to_move==TOP and pos==6) || (@player_to_move==BOTTOM and pos==13) )
			pos = 0 if pos==14
			@board[pos]+=1
			stones-=1
			pos+=1 if stones > 0
		end
		
		if( @player_to_move==TOP and pos>6 and pos<13 and @board[pos]==1 )
			@board[13] += @board[12-pos]+1
			@board[12-pos] = @board[pos] = 0
		elsif( @player_to_move==BOTTOM and pos>=0 and pos<6 and @board[pos]==1 )
			@board[6] += @board[12-pos]+1
			@board[12-pos] = @board[pos] = 0
		end
		
		if @player_to_move==TOP
			@player_to_move = BOTTOM unless pos == 13
		else
			@player_to_move=TOP unless pos == 6
		end
		
	end
	
	def display
		puts ''
		top = '    '
		[12,11,10,9,8,7].each { |i| top += @board[i].to_s+'  ' }
		puts top
		puts @board[13].to_s + '                     ' + @board[6].to_s
		bottom = '    '
		(0..5).each { |i| bottom += @board[i].to_s+'  ' }
		puts bottom
		puts ''
	end
	
	def reset	
		@board = Array.new( 14, 4 )
		@board[6] = @board[13] = 0	
		@player_to_move = BOTTOM
	end
	
	def play_game( bottom, top )
		reset
		
		bottom.side = BOTTOM
		top.side = TOP
		top.game = bottom.game = self
		
		puts bottom.name+' starts...'
		display
		
		until game_over?
			puts ''
			if @player_to_move == TOP
				move = top.choose_move
				puts top.name+' choose move '+move.to_s
			else
				move = bottom.choose_move
				puts bottom.name+' choose move '+move.to_s
			end
			make_move( move )
			display		
		end
		
		[bottom_score, top_score]		
	end
end

p1 = Player.new( 'Player 1' )
p2 = Player.new( 'Player 2' )
KalahMatch.new.start( p1, p2 )
------=_Part_1773_7619312.1134419167836--