Tick5 Tutorial 4

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

4. Where is battlefield?

Now, we have an evaluator that can tell us how good a move is. Recall that the first sentence in the algorithm is "evaluate all possible moves." We could implement our program in a way that it takes all empty spots on the board as possible moves. That is, it scans each spot on the board one by one from (0,0) to (14,14), makes a move on each empty spot and evaluates the move. Obviously, this is inefficient, because it seeks attack far away from the battlefield, especially at the opening of the game when there are only few stones on the board.

What really are the possible moves? When we (human players) play the game, we always seek attacks in the area that is close to the spots occupied by stones, we never do in vacant area. For example, after we place a stone on the board, our next move is most likely on one of the spots marked by yellow crosses in Figure 4-1. These spots form a star pattern centered to the stone. This is the battlefield our program needs to be aware of. Our program will be much efficient, if it chooses and evaluates possible moves from within the battlefield. Figure 4-2 shows the battlefield when there are two stones on the board, which is the superposition of two star patterns.

Image for Hotspots

Figure 4-1 Figure 4-2

The goal in the section is to implement a class, let's call it Hotspots. When the x- and y-coordinate of a move is logged, the class adds the coordinates of those spots which form a star pattern as shown in Figure 4-1. It stores the superposition of the star patterns, when more moves are logged, as illustrated in Figure 4-2. We'll use this class to generate possible moves later in this section.

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

As usual, we first define Hotspots and its interface. Basically, it is a table that stores the coordinates of hot spots. (Listing 4-1)

-----------------------------------------
-- Hotspots class
-----------------------------------------
do
   local bound = nil
   local directions = { south = { x = 0, y = 1 },
                        east  = { x = 1, y = 0 },
                        southeast = { x = 1, y = 1 }, 
                        northeast = { x = 1, y = -1}
                      }

   -- log a move made on x, y
   local function log( hotspots, x, y )
   end

   -- get a spot using index
   local function get( hotspots, index )
   end

   -- metamethod
   local function newindex( hotspots, index, spot )
   end

   -- method table
   local methodtbl = {log = log, get = get}

   -- metatable
   local metatbl = { __index = methodstbl,
                     __newindex = newindex 
                   }
 
   -- creates an instance of hotspots class
   function newHotspots( b, w )
      bound = b
      local hotspots = { width = w }
      return setmetatable( hotspots, metatbl )
   end
end

                                           Listing 4-1

Variable bound is the upper bound of the board. Variable directions looks familiar. Yes, it's same as the one in Evaluator class, because the class needs to navigate a star pattern, too. bound and directions are static data members of the class. Variable width is an instance data member, which is the width of the star pattern and is 2 in the case in Figure 4-1. We don't hard-code it, because we can reuse it to track other hot spots later in this tutorial.

Function log() is one of public member functions. It logs a move by adding spots that form the star pattern centered on the move. Function get() is another public member function. It returns the coordinates of a hot spot when called with an index.

What's new is that the meta table contains metamethod __newindex, which gets called when new field is to be add into the able.

Let's get AI class ready to test Hotspots, before we implement it. (Figure 4-2) We add two data members and get them initialize in function initAI(). Again, we use opponent's last move to test Hotspots, add a for-loop to print out the results.

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

   -- a method that makes a random move
   local function randmove( board )
      math.randomseed( os.time() )

      local bound = board:dimension() - 1

      local x = math.random( 0, bound )
      local y = math.random( 0, bound )

      while not board:isempty( x, y ) do
         x = math.random( 0, bound )
         y = math.random( 0, bound )
      end

      return x, y
   end

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

      for index = 1, table.getn(hotspots), 1 do
         x, y = hotspots:get( index )
         print( "(", x, ", ", y, ")" )
      end
      
      return randmove( board )
   end

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

   -- a table that lists methods of AI class
   local methodtbl = { makemove = makemove }

   -- a table that lists a meta method
   local metatbl = { __index = methodtbl }

   -- a method that creates an instance of AI class,
   -- like a ctor or a factory method
   function newAI( board )
      initAI( board )
      return setmetatable( {}, metatbl )
   end
end

                                           Listing 4-2

Accordingly, modify tick5think() as shown in Listing 4-3.

function tick5think( board )
   AI = newAI( board )
   return AI:makemove( board )
end

                     Listing 4-3

Implementation of the functions of Hotspots class are listed from Listing 4-4 to Listing 4-6.

Similar to function evaluate() of Evaluator class, function log() navigates each spot of the star pattern in Figure 4-1, creates a table that has two fields to accommodate the x- and y-coordinate of the spot, adds the table as a new field to hotspots. (Listing 4-4)

   -- log a move made on x, y
   local function log( hotspots, x, y )
      local x0, y0
      for dir, offset in pairs( directions ) do
         for j = -hotspots.width, hotspots.width, 1 do
            x0 = x + j*offset.x
            y0 = y + j*offset.y
            if x0 >= 0 and x0 <= bound and y0 >= 0 and y0 <= bound then
               hotspots[table.getn(hotspots) + 1] = { x = x0, y = y0 }
            end
         end
      end
   end

                                           Listing 4-4

Function get() returns x- and y-coordinate of the field in hotspots. (see Listing 4-5)

   -- get a spot using index
   local function get( hotspots, index )
      return hotspots[index].x, hotspots[index].y
   end

                                           Listing 4-5

Metamethod newindex() checks the existence of spot, returns without doing anything, if it already in hotspots; invokes rawset() to add the new entry. (see Listing 4-5) This function gets called, when a new field is to be added, for example

hotspots[table.getn(hotspots) + 1] = { x = x0, y = y0 }

This implementation prevents the table from storing duplicated spots.

   -- metamethod
   local function newindex( hotspots, index, spot )
      -- check the existence of the spot
      for idx, spt in ipairs( hotspots ) do
         if spot.x == spt.x and spot.y == spt.y then
            return
         end
      end

      rawset( hotspots, index, spot )
   end

                                           Listing 4-6

Play against the program, test cases of one stone, two stones, and three stones, etc., test in different locations. The list of hot spots grows very fast.

Before we move on to next section, let's do the following refactorings. (Listing 4-7 and 4-8) In case that you may ask what's the purpose, we just let the code document itself.

   local function withinbound( x, y )
      return x >= 0 and x <= bound and y >= 0 and y <= bound
   end

   -- log a move made on x, y
   local function log( hotspots, x, y )
      local x0, y0
      for dir, offset in pairs( directions ) do
         for j = -hotspots.width, hotspots.width, 1 do
            x0 = x + j*offset.x
            y0 = y + j*offset.y
            if x0 >= 0 and x0 <= bound and y0 >= 0 and y0 <= bound then
            if withinbound( x0, y0 ) then
               hotspots[table.getn(hotspots) + 1] = { x = x0, y = y0 }
            end
         end
      end
   end

                                           Listing 4-7

   local function exist( hotspots, spot )
      for idx, spt in ipairs( hotspots ) do
         if spot.x == spt.x and spot.y == spt.y then
            return true
         end
      end

      return false
   end

   -- metamethod
   local function newindex( hotspots, index, spot )
      -- check the existence of the spot
      for idx, spt in ipairs( hotspots ) do
         if spot.x == spt.x and spot.y == spt.y then
            return
         end
      end
      if not exist( hotspots, spot ) then
         rawset( hotspots, index, spot )
      end
   end

                                           Listing 4-8

Play against the program, it still works as expected.