From ruby-talk-admin@ruby-lang.org Thu Dec 15 22:40:45 2005 Received: from kankan.nagaokaut.ac.jp (kankan.nagaokaut.ac.jp [133.44.2.24]) by blade.nagaokaut.ac.jp (8.12.3/8.12.3/Debian-6.6) with ESMTP id jBFDejZk019735; Thu, 15 Dec 2005 22:40:45 +0900 Received: from funfun.nagaokaut.ac.jp (funfun.nagaokaut.ac.jp [133.44.2.201]) by kankan.nagaokaut.ac.jp (Postfix) with ESMTP id 115645B83; Thu, 15 Dec 2005 22:40:46 +0900 (JST) Received: from localhost (localhost.nagaokaut.ac.jp [127.0.0.1]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 89F24F04842; Thu, 15 Dec 2005 22:40:49 +0900 (JST) Received: from voscc.nagaokaut.ac.jp (voscc.nagaokaut.ac.jp [133.44.1.100]) by funfun.nagaokaut.ac.jp (Postfix) with ESMTP id 39E6DF04846; Thu, 15 Dec 2005 22:40:48 +0900 (JST) Received: from beryllium.ruby-lang.org (beryllium.ruby-lang.org [210.163.138.100]) by voscc.nagaokaut.ac.jp (Postfix) with ESMTP id 880FE630024; Thu, 15 Dec 2005 22:40:50 +0900 (JST) Received: from beryllium.ruby-lang.org (beryllium.ruby-lang.org [127.0.0.1]) by beryllium.ruby-lang.org (Postfix) with ESMTP id 038D833D16; Thu, 15 Dec 2005 22:40:47 +0900 (JST) Received: from localhost (beryllium.ruby-lang.org [127.0.0.1]) by beryllium.ruby-lang.org (Postfix) with ESMTP id 9968033D30 for ; Thu, 15 Dec 2005 22:40:37 +0900 (JST) Received: from beryllium.ruby-lang.org ([127.0.0.1]) by localhost (beryllium.ruby-lang.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 25917-08 for ; Thu, 15 Dec 2005 22:40:37 +0900 (JST) Received: from centrmmtao04.cox.net (centrmmtao04.cox.net [70.168.83.80]) by beryllium.ruby-lang.org (Postfix) with ESMTP id B50D433D16 for ; Thu, 15 Dec 2005 22:40:36 +0900 (JST) Received: from localhost.localdomain ([68.97.67.155]) by centrmmtao04.cox.net (InterMail vM.6.01.05.02 201-2131-123-102-20050715) with ESMTP id <20051215133839.MWJU8318.centrmmtao04.cox.net@localhost.localdomain> for ; Thu, 15 Dec 2005 08:38:39 -0500 Delivered-To: ruby-talk@ruby-lang.org Date: Thu, 15 Dec 2005 22:40:38 +0900 Posted: Thu, 15 Dec 2005 08:38:39 -0500 From: Ruby Quiz Reply-To: ruby-talk@ruby-lang.org Subject: [SUMMARY] Kalah (#58) To: ruby-talk@ruby-lang.org (ruby-talk ML) Message-Id: <20051215133839.MWJU8318.centrmmtao04.cox.net@localhost.localdomain> X-ML-Name: ruby-talk X-Mail-Count: 25 X-MLServer: fml [fml 4.0.3 release (20011202/4.0.3)]; post only (only members can post) X-ML-Info: If you have a question, send e-mail with the body "help" (without quotes) to the address ruby-talk-ctl@ruby-lang.org; help= X-Original-To: ruby-talk@ruby-lang.org X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at ruby-lang.org X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on beryllium.ruby-lang.org X-Spam-Level: X-Spam-Status: No, score=-5.0 required=7.0 tests=AWL,BAYES_00, NOTINCONTENTTYPE,RCVDFRMLOCALIP autolearn=no version=3.0.3 Precedence: bulk Lines: 185 List-Id: ruby-talk.ruby-lang.org List-Software: fml [fml 4.0.3 release (20011202/4.0.3)] List-Post: List-Owner: List-Help: List-Unsubscribe: X-Virus-Scanned: by AMaViS snapshot-20020531 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 Quiz 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 Balmain'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 Quiz fans, our first prize awarding competition...