Logo for Tick5 Game

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


SourceForge.net Logo

Image of Lua Logo

Image for wxWidgets Logo

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   Image for Hot Spots 2
        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.