Tick5 Tutorial 2

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

2. How good is a move?

Recall the algorithm we're going to implement, our program, when given a move, needs to identify whether it forms a 5-in-a-row or not? whether it can best block opponent's last move or not? whether it forms best attacking for us or not? In short, our program needs a generic component that can evaluate how good a move is, from our perspective as well as our opponent's.

According to the game rules, a stone can only form a 5-in-a-row with other stones on the spots marked by yellow crosses in Figure 2-1. We need a component which, when given a move such as the one in Figure 2-1, can navigate all four directions, detecting the status of each spot (whether a black stone, a white stone, or empty,) identifying the patterns stones form, and assign a value to the move based on the identified patterns. The higher the value, the better the move.

Figure 2-1

The goal in this section is to start a new component -- an evaluator. It returns a value when being fed with a move. We're not going to finish it in this section, we take two steps instead. By the end of this section, we'll make it able to navigate the spots that form the star pattern and collect the status of each spot. In next section, we'll add code to identify patterns these stones form.

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

Add a do-end block into the file. (Listing 2-1)

------------------------------------------------
-- Evaluator
------------------------------------------------
do
   local directions = { south = { x = 0, y = 1 },
                        east  = { x = 1, y = 0 },
                        southeast = { x = 1, y = 1 }, 
                        northeast = { x = 1, y = -1 }
                      }

   -- evaluate a stone
   function evaluate( board, x, y, color )
   end
end

                      Listing 2-1

This do-end block contains a table and a function. The table directions has four fields representing the four directions of the star pattern. Each field itself is a table which has two fields corresponding to x- and y-offset of each step in the direction. The function evaluate()takes a board and a move (x-, y-coordinate and color) as inputs, returns a value that measures how good the move is.

Before we implement evaluate(), let's get AI class ready to test the evaluator. Modify function makemove()by adding code that queries opponent's last move and invokes the evaluator with the move. (Listing 2-2)

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

      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

                      Listing 2-2

We can choose other moves else to test the evaluator. However, choosing opponent's last move has the advantage that the move is under our control when we test the program by playing against it. For example, we put a stone right beside another and watch whether the program can identify the two consecutive stones or not. Furthermore, the algorithm requires our program to evaluate opponent's last move.

Add two nested for-loops to evaluate(). (Listing 2-3) The outer one loops over all four directions; the inner one, all spots in one direction.

   function evaluate( board, x, y, color )
      local x0, y0
      for dir, offset in pairs( directions ) do
         print( dir )
         for i = -4, 4, 1 do
            x0 = x + i*offset.x
            y0 = y + i*offset.y
            print( board:getstone( x0, y0 ) )
         end
      end
   end

                                           Listing 2-3

Play against the program. It can correctly print out stones or empty spots. It runs without problem, until we click on a spot which is close to the edge of the board, for example (2,2). The error massage complains that getstone() is called with a bad argument. Take a look at Figure 2-1, if the star pattern is centered on (2,2), some of the spots will exceed the boundary of the board. We need to a protection as shown in Listing 2-4.

   function evaluate( board, x, y, color )
      local x0, y0
      for dir, offset in pairs( directions ) do
         print( dir )
         for i = -4, 4, 1 do
            x0 = x + i*offset.x
            y0 = y + i*offset.y
            if board:inboard( x0, y0 ) then
               print( board:getstone( x0, y0 ) )
            end
         end
      end
   end

                                           Listing 2-4

Play against the program and purposely click the board edges and corners. It works just as expected

Instead of printing out the status of the spots, we add a table called stream to store them, and add another for-loop to print out stream in order to test it. (Listing 2-5) We'll use stream in next section.

   function evaluate( board, x, y, color )
      local x0, y0
      for dir, offset in pairs( directions ) do
         print( dir )
         local stream, idx = {}, 1
         for i = -4, 4, 1 do
            x0 = x + i*offset.x
            y0 = y + i*offset.y
            if board:inboard( x0, y0 ) then
               stream[idx] = board:getstone( x0, y0 )
               idx = idx + 1 
               print( board:getstone( x0, y0 ) )
            end
         end

         for spot, status in ipairs( stream ) do
            print( status )
         end
      end
   end

                                           Listing 2-5

Play against the program, it still works as pexcted.

As we did in previous section, let's clean up somehow before we move on to next section.

Take look at makemove(). It's getting bigger. Let's move the portion that generates random moves into a new function randmove(). (Listing 2-6)

   -- 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
         evaluate( board, x, y, color )
      end

      return 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

                      Listing 2-6

Play against the script, it still works as expected.