Tick5 Tutorial

What's new
About
Download
License
Screenshots
Manual
Tutorial
sf.net page
Contact

5. Evaluate possible moves

Now, we know the battlefield and have the evaluator in hand, we can realize the first sentence in the algorithm. In this section, we'll add a function evalmoves() to AI class, which generates and evaluates possible moves.

Let's open boora-0.4.wz with a text editor and save it as boora-0.5.wz.

Add data members mystone and movelist to AI class. (Listing 5-1) mystone is the color of the stone the AI player plays, movelist stores the generated moves.

-- AI class
-----------------------
do
   local bound = nil
   local hotspots = nil
   local mystone = nil
   local movelist = nil

                                            Listing 5-1

mystone is initialized in initAI(). (Listing 5-2)

   local function initAI( board )
      if bound == nil then 
         bound = board:dimension() - 1
         hotspots = newHotspots( bound, 2 )
         mystone = mycolor()
      end
   end

                                            Listing 5-2

Add compvals() and evalmoves()to AI class. (Listing 5-3)

Function comvals() compares two moves by their evalues. We don't directly call this function, but use it to sort movelist by values of moves (see the last line in function evalmoves().)

Function evalmoves()loops over hotspots, calling putstone() to place a stone on an empty spot, calling evaluate() to calculate the value of the move, calling remove() to get the stone removed, adding index of the spot and its value to movelist. The function, in the end, sorts movelist by the values of moves in descending order, so the first one is the best move so far.

   -- compare moves by their values,
   local function compvals( move1, move2 )
      return move1.val > move2.val 
   end

   -- generate, evaluate and sort possible moves
   local function evalmoves()
      movelist = {}
      local index = 1
      local x, y, v
      for i, spot in ipairs( hotspots ) do
         --- good practice ---
         if not keeprunning() then 
            break
         end

         x, y = spot.x, spot.y
         if board:putstone( x, y, mystone ) then
            v = evaluate( board, x, y, mystone )
            board:remove( x, y )

            movelist[index] = {idx = i, val = v}
            index = index + 1
         end
      end

      table.sort( movelist, compvals )
   end

                                            Listing 5-3

Modify makemove() in order to test evalmoves()and movelist. (Listing 5-4)

   -- a method that makes a move
   local function makemove( ai, board )
      local x, y, color = board:lastmove()
      if x ~= nil and y ~= nil then
         hotspots:log( x, y )
      end

      for index = 1, table.getn(hotspots), 1 do
         x, y = hotspots:get( index )
         print( "(", x, ", ", y, ")" )
      end
      
      evalmoves( board )
      if table.getn( movelist ) >= 1 then
         x, y = hotspots:get( movelist[1].idx )
      else
         x, y = randmove( board )
      end

      hotspots:log( x, y )

      return randmove( board )
      return x, y
   end
                                            Listing 5-4

After calling evalmoves() to generate and evaluate possible moves, the function picks up the first entry, the best move so far, from movelist, if movelist is not empty; otherwise, it calls randmove() to make a random move. It logs the move to hotspots.

Play against the program. We notice that it has the trend to form winning patterns and it does have chance to win if we don't take it seriously. This means evalmoves() works. Let it pay against a previous version, say, boora-0.1.wz, it definitely wins, no matter whether it plays black or white stone. Pretty exciting, huh? Our program won't just goof around anymore!

Watch carefully, we find out that its first move is still random, if it plays black stone. The reason is that evalmoves() cannot generate any move, if hotspots is empty. We treat this special case by hard-coding a move. (Listing 5-5)

   -- a hard-coded move on center
   local function fixedrmove()
      local x, y = bound/2, bound/2
      hotspots:log( x, y )
      return x, y
   end

   -- a method that makes a move
   local function makemove( ai, board )
      if board:isempty() then
         return fixedrmove() 
      end

      local x, y, color = board:lastmove()
      if x ~= nil and y ~= nil then
         hotspots:log( x, y )
      end

      evalmoves( board )
      if table.getn( movelist ) >= 1 then
         x, y = hotspots:get( movelist[1].idx )
      else
         x, y = randmove( board )
      end

      hotspots:log( x, y )

      return x, y
   end
                                            Listing 5-5

Test again, we see that it won't make random move anymore. Instead, it simply puts a stone on the center of the board, if it plays black stone. So, we don't need randmove() anymore. After goofing around for four programming episodes, randmove() can retire now, of course, with honor. Shall we throw a party to celebrate its retirement?

Before we go, let's do some clean up as usual. (Listing 5-6) randmove() is retired. Checking the returns of lastmove() is not necessary, because it is guaranteed to return a move if the board is not empty. The details of getting the best-so-far move are hidden in the new function greedymove().

   -- best move so far
   local function greedymove()
      assert( table.getn( movelist ) >= 1 )
      return hotspots:get( movelist[1].idx )
   end

   -- a method that makes a move
   local function makemove( ai, board )
      if board:isempty() then
         return fixedmove() 
      end

      local x, y, color = board:lastmove()
      if x ~= nil and y ~= nil then
         hotspots:log( x, y )
      end

      evalmoves( board )
      x, y = greedymove()
      if table.getn( movelist ) >= 1 then
         x, y = hotspots:get( movelist[1].idx )
      else
         x, y = randmove( board )
      end

      hotspots:log( x, y )

      return x, y
   end
                                            Listing 5-6

Play against the program. For the the first time, we need to pay a bit more attention in order to win.