The Red Language is an interesting language, not least because of its tiny compiler/runtime, 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 shortcomings 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 9element 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 streetwise, 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 twoply 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_shuffles
steps  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 counterintuitively, 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.