SLIDE

The 24-puzzle: can YOU program a solution?

Program by MARK MOORE
Article by MICHAEL CIRAOLO, Antic Associate Editor

A computerized version of the 24-tile puzzle grid, Slide is easy to type in and a good starter for advanced programmers who want to try their hands at intelligent game design. Written in BASIC, Slide requires a joystick and 16K RAM on any Atari, disk or cassette.

Tile puzzles-grids of 8 tiles in a 3 x 3 arrangement or 24 tiles in a 5 x 5 arrangement- have been around a long time. Can you solve the 24 Puzzle? Can your Atari solve it? For an introduction to the design of intelligent games, read on. You'll find a jumping-off point for further programming and research. (Also be sure to read the article about Computer Chess in this issue.)
   If you only want to play the game, type in Listing 1, check it with TYPO II, and SAVE a copy. Use the joystick to move the cursor in the desired direction. Move the lettered tiles by pressing the joystick button. You can move a tile into any vacant square.
   When you get the tiles in alphabetic order, press the [SPACE] bar. The computer will verify your result-the time it took to complete the puzzle, or an obnoxious razz signifying that you need to try again.

INTELLIGENT GAMES
There are two types of "intelligence" you could use to set your Atari solving the 24 Puzzle. You could use an algorithm, which is a logical set of steps for solving a specific problem (or showing if no solution is possible). Since the program would have to examine every possible move until the best solution was discovered, this would be very slow and possibly beyond the limits of a computer's memory.
   The alternative is devising a heuristic problem solving technique. This means developing a set of rules that cut out a lot of the false moves. Most electronic games favor heuristics since they require less moves, which makes them faster and more memory-efficient than algorithms.
   If you are going to write a program to solve the 24 Puzzle, you might wish to use a common heuristic device called a "tree."
   The game's starting position is called the "root." Spreading up from the root are all the legal moves, produced by a subroutine called a legal move generator. Each legal move, in turn, begets another generation of possible moves. It is up to the computer to evaluate each end position to see if that position is near a solution.
   Intelligent game programs use a device called an evaluation function to supply a numerical score for each end position. Such a function for the 24 Puzzle might count the number of vertical and horizontal tiles between the current position and the target position. For instance, the "A" tile might be three spaces away from the upper left corner. Add this to the "B" tile's distance of five from its target position. Add this sum to the position for the "C" tile, and so on.
   The score resulting from the evaluation function tells the computer which branches are closer to a solution; the program can then disregard the least promising result with a process called "pruning."

SOLUTION STRATEGY
Now we have a strategy:

   1. The program will generate all possible moves from the root.

   2. It will then evaluate each position to see how close a position is to the target.

   3. Next, it will draw a new tree, based on the most promising results of the previous tree.

   Each time the program draws a new tree, or picks the best possible position from a choice of branches, it is determining its next move.
   In the world of electronic gaming, it is also important for a program to function quickly. The program needs to take as few moves as possible to win. One idea here is to always prune the tree of possible moves that are identical to the previous move-the program shouldn't spend its time retracing its steps.
   The hardest part of intelligent game design here is to produce a reasonable quiescence function, the subroutine that prunes branches that don't seem fruitful.
   Your function will be measured by the number of spurious nodes that are expanded to a solution en route-the perfect function will always prune all spurious nodes. The worst function will expand each node at one level in the tree before looking to the next level-this is called an exhaustive search, and wastes computer time and memory.
   If the design of "artificial intelligence" intrigues you, why not see if you can use this puzzle program as a starting point for your own program which solves the 24 Puzzle? Antic would be interested in publishing the shortest and most elegant solution sent in by a reader.

Mark Moore is from Weatherford, Oklahoma and this is his first publication in Antic.

Listing 1    SLIDE.BAS Download