What's new
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.

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