Page Contents

2021-11-21 #heuristics #red

Table of Contents

The Red Language is an interesting language, not least because of its tiny compiler/run-time, which makes building and distributing programs fun.

Here, I write a Red version of a simple Tile Game program. The ideas are taken from Chapter 2 of the book Artificial Intelligence in BASIC by Mike James, 1984.

This example introduces a number of useful AI (Artifical Intelligence) concepts:

  • representing a world as a state;

  • how different moves transform one state into another;

  • using an heuristic to measure how far a state is from a goal; and

  • the use of lookahead to try to find the best move.

By comparing different forms of problem solving behaviour, using random, heuristic and lookahead searches, we can investigate the advantages and short-comings of some elementary AI techniques.

From a programming perspective, the example will touch on several Red concepts:

  • creating objects to represent game states: an object holds data and functions;

  • working with series to store, retrieve and adapt information about the current game state; and

  • general coding in the form of functions, conditions and loop constructs.

The complete code can be downloaded from tile.red

Description

The tile game is played on a 3x3 grid. Tiles consist of the 8 numbers from 1 to 8, with the remaining place in the grid taken up by a space. Tiles adjacent to the space can be moved into the space. The objective is to make a sequence of such moves to return an arbitrary arrangement of tiles to the starting order:

1 2 3
4 5 6
7 8 .

Core Data Structures

The first part of the program provides some basic features for creating and managing the game state. For this, I shall create an object, and add data and functions.

Internally, the board will be represented simply as a 9-element series.

We need the following functions:

  • show - displays the current position to the terminal

  • is_finished - checks if the current position is the target position

  • get_moves - returns a series of possible new positions

Internally, we also create functions:

  • space_position - returns the position of the space character

  • board_after_move - returns a new board position, obtained by swapping the values of two cell positions over.

A map, moves_from, stores the possible moves from a given cell.

This gives us the position object:

position: object [
  board: [1 2 3 4 5 6 7 8 "."]
  moves_from: make map! [1 [2 4] 2 [1 3 5] 3 [2 6] 4 [1 5 7] 5 [2 4 6 8] 6 [3 5 9] 7 [4 8] 8 [5 7 9] 9 [6 8]]

  ; print the tile position to terminal
  show: function [] [
    print ""
    print "-----"
    print [pick board 1 pick board 2 pick board 3]
    print [pick board 4 pick board 5 pick board 6]
    print [pick board 7 pick board 8 pick board 9]
    print "-----"
  ]

  ; check if current board is the target position
  is_finished: function [] [
    return board = [1 2 3 4 5 6 7 8 "."]
  ]

  ; return the index of the space
  space_position: function [] [
    repeat i 9 [
      if "." = pick board i [return i]
    ]
  ]

  ; returns a new board (series) with the items in the given cells swapped
  board_after_move: function [cell1 cell2] [
    result: copy board

    poke result cell1 pick board cell2
    poke result cell2 pick board cell1

    return result
  ]

  ; returns a series of new positions, with updated board positions
  get_moves: function [] [
    result: copy []

    space_cell: space_position
    foreach move_square select moves_from space_cell [
      new_posn: copy self
      new_posn/board: board_after_move space_cell move_square
      append result new_posn
    ]

    return result
  ]
]

The position defined above sets up the board for the standard start position. To create a puzzle to solve, we need to shuffle the board by randomly moving the tiles around. It is easy to get a random move, by adding random_move to the position object:

  ; returns a new position, after selecting a random valid move
  random_move: function [] [
    return first random get_moves
  ]

A shuffle function can then simply call random_move a number of times:

shuffle: function [posn n] [
  repeat i n [
    posn: posn/random_move
  ]

  return posn
]

An example of using this:

    >> start: position                  1
    == make object! [
        board: [1 2 3 4 5 6 7 8 "."]
        moves_from: #...
    >> start/show                       2

    -----
    1 2 3
    4 5 6
    7 8 .
    -----
    >> posn: shuffle start 100          3
    == make object! [
        board: [5 2 8 1 "." 7 4 3 6]
        moves_from: #...
    >> posn/show                        4

    -----
    5 2 8
    1 . 7
    4 3 6
    -----
    >> posn: shuffle start 100          5
    == make object! [
        board: [1 3 "." 5 2 6 4 7 8]
        moves_from: #...
    >> posn/show                        6

    -----
    1 3 .
    5 2 6
    4 7 8
    -----
1 Name the start position.
2 Display the start position.
3 Create a new position by shuffling the start position 100 times.
4 Display the new position.
5 Again, create a new position from the start position.
6 Display the new position, and notice the new position is different to before.

Given this is such a simple problem, we might as well give random search a try. The code for this is straightforward - given a position, we keep trying a random move until the is_finished function returns true. We make a safety net, so the search stops after a given number of moves:

random_search: function [posn] [
  repeat moves 100000 [
    posn: posn/random_move
    if posn/is_finished [
      print ["Found solution in " moves " moves"]
      exit
    ]
  ]
  print "Failed to find solution in 100000 moves"
]

Surprisingly, this did work (once)!

    >> posn: shuffle start 100
    == make object! [
        board: [1 3 "." 5 2 6 4 7 8]
        moves_from: #...
    >> posn/show

    -----
    1 3 .
    5 2 6
    4 7 8
    -----
    >> random_search posn
    Found solution in  6912  moves

But usually random search is ineffective, and we need a smarter solution - this is where we make our program "artificially intelligent".

Solving the tile game consists of choosing the next move from between 2 to 4 alternatives. Random selection of the next move is not an effective strategy. Usually, when confronted by different choices, we think about what might be the best option. The idea of an "heuristic" is to try to capture that notion of "best".

One way to measure how far our current situation is from the target is using the Manhattan, or street-wise, distance measure. What this does is count how many moves each tile has to make to return to its original place, ignoring the other tiles.

We can add a function to compute this to our position object:

  ; manhattan distance of board from its target
  x_coords: make map! [1 1 2 2 3 3 4 1 5 2 6 3 7 1 8 2 9 3]
  y_coords: make map! [1 1 2 1 3 1 4 2 5 2 6 2 7 3 8 3 9 3]
  manhattan_distance: function [] [
    distance: 0

    repeat cell 9 [
      value: pick board cell
      if not (value = ".") [ ; do not calculate a distance for space
        distance: distance + (absolute ((select x_coords value) - (select x_coords cell))) + (absolute ((select y_coords value) - (select y_coords cell)))
      ]
    ]

    return distance
  ]

And then make a search function which will choose the move which minimises the manhattan distance:

heuristic_search: function [posn] [
  repeat moves 100000 [
    candidate_moves: posn/get_moves   ; retrieve all possible moves
    sort/compare (random candidate_moves) function [posn1 posn2] [posn1/manhattan_distance < posn2/manhattan_distance]
    posn: first candidate_moves

    if posn/is_finished [             ; check for finish state
      print ["Found solution in " moves " moves"]
      exit
    ]
  ]
  print "Failed to find solution in 100000 moves"
]

This has mixed results:

    >> posn/show

    -----
    2 5 3
    1 . 6
    4 7 8
    -----
    >> heuristic_search posn
    Found solution in  6  moves

    >> posn/show

    -----
    2 4 3
    8 7 1
    . 6 5
    -----
    >> heuristic_search posn
    Failed to find solution in 100000 moves

This was also noted by Mike James in his book - he said this simple heuristic did noticeably badly when the original position was shuffled more than 50 times. And he describes various "stuck states" which the heuristic search can find itself in.

Although the heuristic approach works, it assumes we can make an informed decision based only on the possibilities available to us now. Quite often, this is not the case: we may make one move, and then have the option for a very good move, which makes for the best situation in two steps. For this reason, AI systems typically implement some kind of lookahead search, in which they consider options two or more moves deep. Here, we look at a two-ply lookhead search - where "ply" means "move".

To implement this lookahead version, we will add a new function to position called lookahead_distance - this will return the best score achievable by making one move from the current position.

Our search function now simply calls lookahead_distance on each candidate move, to find the best score:

lookahead_search: function [posn] [
  repeat moves 100000 [
    candidate_moves: posn/get_moves   ; retrieve all possible moves
    sort/compare (random candidate_moves) function [posn1 posn2] [posn1/lookahead_distance < posn2/lookahead_distance]
    posn: first candidate_moves

    if posn/is_finished [             ; check for finish state
      print ["Found solution in " moves " moves"]
      exit
    ]
  ]
  print "Failed to find solution in 100000 moves"
]

The lookahead_distance function itself is implemented within the position object and finds the smallest distance from the possible moves:

  lookahead_distance: function [] [
    best_move: 100
    foreach move get_moves [
      this_move: move/manhattan_distance
      if this_move < best_move [
        best_move: this_move
      ]
    ]

    return best_move
  ]

This works as before:

    >> posn: shuffle position 50
    == make object! [
        board: [4 1 3 2 8 5 7 6 "."]
        moves_from: #...
    >> posn/show

    -----
    4 1 3
    2 8 5
    7 6 .
    -----
    >> lookahead_search posn
    Found solution in  20  moves
    >> heuristic_search posn
    Failed to find solution in 100000 moves
    >> lookahead_search posn
    Found solution in  14  moves

Notice how the lookahead search can vary in the number of steps needed to find a solution, and how it can find solutions which heuristic search cannot.

Comparing the Approaches

We have implemented three search techniques: random, heuristic and lookahead. We may be interested in exploring which technique might be "better", in some sense. What could we mean by "better"? One sense in which a technique is better is if it is more likely to find a solution for a random problem. Another sense would be the number of moves used, in those cases where it does find a solution.

To collect some statistics automatically, we need to make a version of each search technique which returns the number of average moves taken and indicates when a solution could not be found - e.g. a negative number.

For example, modify lookahead_search to return a number instead of printing to the terminal:

run_lookahead_search: function [posn] [
  repeat moves 1000 [                 ; 1
    candidate_moves: posn/get_moves   ; retrieve all possible moves
    sort/compare (random candidate_moves) function [posn1 posn2] [posn1/lookahead_distance < posn2/lookahead_distance]
    posn: first candidate_moves

    if posn/is_finished [             ; check for finish state
      return moves`
    ]
  ]
  return -1
]
1 We will also reduce the number of moves - this helps speed up running many searches.

Our analysis function will:

  1. create a random position using shuffle for num_shuffles steps

  2. run each of the three searches on this position, recording the result

  3. repeat the above 100 times

  4. report the overall proportion solved and average moves for each search

compare_searches: function [num_shuffles] [
  successful_random: 0                                ; 1
  moves_random: 0
  successful_heuristic: 0
  moves_heuristic: 0
  successful_lookahead: 0
  moves_lookahead: 0

  ; run the different searches
  repeat i 100 [                                      ; 2
    posn: shuffle position num_shuffles               ; 3

    result_random: run_random_search posn             ; 4
    result_heuristic: run_heuristic_search posn
    result_lookahead: run_lookahead_search posn

    if result_random > 0 [                            ; 5
      successful_random: successful_random + 1
      moves_random: moves_random + result_random
    ]
    if result_heuristic > 0 [
      successful_heuristic: successful_heuristic + 1
      moves_heuristic: moves_heuristic + result_heuristic
    ]
    if result_lookahead > 0 [
      successful_lookahead: successful_lookahead + 1
      moves_lookahead: moves_lookahead + result_lookahead
    ]
  ]

  ; report the statistics as an asciidoc table          6
  print [".Results from comparing search techniques (shuffle=" num_shuffles ")"]
  print "|==="
  print "| Technique | Proportion Solved | Average Moves"
  print ""

  either successful_random = 0 [                      ; 7
    print "| Random | 0 | 0"
  ][
    print ["| Random | " successful_random "| " (moves_random / successful_random)]
  ]
  either successful_heuristic = 0 [
    print "| Heuristic | 0 | 0"
  ][
    print ["| Heuristic | " successful_heuristic "| " (moves_heuristic / successful_heuristic)]
  ]
  either successful_lookahead = 0 [
    print "| Lookahead | 0 | 0"
  ][
    print ["| Lookahead | " successful_lookahead "| " (moves_lookahead / successful_lookahead)]
  ]
  print "|==="
]
1 Initial values for each of the statistics to record.
2 Run the loop 100 times, to make an easy percentage.
3 Shuffle the start position the given number of times.
4 Run each of the search techniques, keeping their result value.
5 Record the results of successful searches.
6 Results are output preformatted for use in asciidoc, which is used to write this document.
7 Check for possible 'divide by zero' error.

Running this function for different problem difficulties - the number of shuffles - produces results like these:

Table 1. Results from comparing search techniques (shuffle= 20 )
Technique Proportion Solved Average Moves

Random

3

338.6666666666667

Heuristic

65

6.984615384615385

Lookahead

83

22.26506024096386

Table 2. Results from comparing search techniques (shuffle= 50 )
Technique Proportion Solved Average Moves

Random

3

19.33333333333333

Heuristic

36

9.111111111111111

Lookahead

55

63.70909090909091

Table 3. Results from comparing search techniques (shuffle= 100 )
Technique Proportion Solved Average Moves

Random

1

36

Heuristic

4

10

Lookahead

23

184.3478260869565

As the number of initial shuffles increases, the positions are harder to solve.

Interestingly, and I think counter-intuitively, the lookahead solutions are several times longer than those found using the heuristic alone. One reason for this could be that lookahead solves more difficult problems than the heuristic search, and these more difficult problems require many more steps.