Tick5 Tutorial 6

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

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() 
      end

      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 )
      else
         x, y = greedymove()
      end

      hotspots:log( x, y )

      return x, y
   end

                                            Listing 6-1

Function 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
   end

                                            Listing 6-2

Function 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
   end

                                            Listing 6-3

Function 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
            end
         end
      end

      return xmax, ymax
   end

                                            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.