Logo for Tick5 Game

What's new
sf.net page

SourceForge.net Logo

Image of Lua Logo

Image for wxWidgets Logo

6. Add missing pieces

Now, our program can make meaningful moves and can definitely defeat its predecessors. However, to fully implement the algorithm, our program still has some pieces missing: our program needs to 1) explicitly determine whether a move can form a won pattern or not; 2) identify whether opponent's last move forms any threats or not; 3) figure out a move that can best block opponent's threats. In this section, we're going to add these missing pieces.

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

Modify function makemove() of AI class to conform the algorithm. (Listing 6-1)

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

local x, y, color = board:lastmove()
hotspots:log( x, y )

evalmoves( board )
if wonpattern() then
x, y = greedymove()
elseif threatening( board, x, y ) then
x, y = defend( board, x, y )
x, y = greedymove()

hotspots:log( x, y )

return x, y

Listing 6-1

wonpattern() checks the move in the first entry of movelist, and returns true, if its value is bigger than 5000; false, otherwise. (Listing 6-2)  Refer back to function evaluate(), 5000 is the weight of 5-in-a-row patterns. (Listing 3-15)

   -- won pattern?
local function wonpattern()
assert( table.getn( movelist ) >= 1 )
return movelist[1].val >= 5000

Listing 6-2

threatening()evaluates opponent's last move, and returns true, if it's threatening; false, otherwise. This is the place that decides under what condition the program should immediately response to opponent's last move. In this implementation, the move is evaluated from opponent's perspective, its value is compared with the weight of 3-in-a-row patterns.  (Listing 6-3)

   -- is the move threatening?
local function threatening( board, x, y )
assert( board:inboard( x, y ) )
return evaluate( board, x, y, -mystone ) >= 100

Listing 6-3

defend() takes opponent's last move as input, and searches for next move the opponent most likely to make. (Listing 6-4)

Here, we use the heuristic that opponent's next move is most likely the one that has the biggest value from opponent's perspective. Therefore, if we can predict 
opponent's next most likely move, we place our stone on the spot, which will most likely prevent opponent from gaining the value and, in turn, block the threats.

We also use another heuristic that only some of the spots on the board with which opponent's last form 5-in-a-row patterns. Therefore, we search, instead of the whole board, only those spots that form the star pattern in Figure 2-1.

The first line of the function creates an instance of
Hotspots with a width of four; the second line logs opponent's last move into it, which forms the star pattern. Similar to evalmoves() (Listing 5-3), in the for-loop, an opponent's stone is placed on each of the empty spots and is evaluated, and the one that has the biggest value is memorized.

   -- find next move opponent most likely to make
local function defend( board, x0, y0 )
local hisspots = newHotspots( bound, 4 )
hisspots:log( x0, y0 )

local x, y, val
local xmax, ymax, valmax = nil, nil, -1

for i, spot in ipairs( hisspots ) do
x, y = spot.x, spot.y
if board:putstone( x, y, -mystone ) then
val = evaluate( board, x, y, -mystone )
board:remove( x, y )

if val > valmax then
valmax = val
xmax, ymax = x, y

return xmax, ymax

Listing 6-4

Play against the program. We notice that very time we form a 3-in-a-row, the program tries to block it. We need to pay even more attention in order to win, because it has the ability to defend itself. Let the program play against its predecessor boora-0.5.wz. It wins, if it plays black stone; loses, if white.