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 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 .
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
-----
- Name the start position.
- Display the start position.
- Create a new position by shuffling the start position 100 times.
- Display the new position.
- Again, create a new position from the start position.
- 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.
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
]
- We will also reduce the number of moves - this helps speed up running many searches.
Our analysis function will:
-
create a random position using shuffle for
num_shufflessteps - run each of the three searches on this position, recording the result
- repeat the above 100 times
-
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 "|===" ] - Initial values for each of the statistics to record.
- Run the loop 100 times, to make an easy percentage.
- Shuffle the start position the given number of times.
- Run each of the search techniques, keeping their result value.
- Record the results of successful searches.
- Results are output preformatted for use in asciidoc, which is used to write this document.
- Check for possible 'divide by zero' error.
Running this function for different problem difficulties - the number of shuffles - produces results like these:
Results from comparing search techniques (shuffle= 20 )
| Technique | Proportion Solved | Average Moves |
|---|---|---|
| Random | 3 | 338.6666666666667 |
| Heuristic | 65 | 6.984615384615385 |
| Lookahead | 83 | 22.26506024096386 |
Results from comparing search techniques (shuffle= 50 )
| Technique | Proportion Solved | Average Moves |
|---|---|---|
| Random | 3 | 19.33333333333333 |
| Heuristic | 36 | 9.111111111111111 |
| Lookahead | 55 | 63.70909090909091 |
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.