Copyright Notice: This article is Copyright AI Factory Ltd. Ideas and code belonging to AI Factory may only used with the direct written permission of AI Factory Ltd.
Much of the work at AI Factory Ltd is directed at 2-player turn-based games. However our generic resource is designed not only to provide a uniform platform for creating 2-player games but also to easily support multi and single player games. Of these, a substantial group of "single player games" are actually puzzles. A previous article "Off-the-Shelf AI: Plug-in Minimax" referred to use of our generic AI for this purpose, and this article concentrates on the puzzle sub-genre.
Puzzle Development Requirements
Puzzle creation is one of the black arts, mastered by the few. Since this involves the creation of the game as well as how to play it, it requires more tools than would be needed to create (for example) a program to just play the game of chess. One of the great practitioners of this art was the famous Nobuyuki Yoshigahara, who published some 80 books on puzzles. However behind his inspirational skill was a strong programming ability, which assisted in both the solving and creation of puzzles. To progress you need the following:
The traditional puzzle creator might manage without all of these, but if you want to be able to create many such puzzles, then some automated means of 3 and 4 above is pretty well essential.
Fitting Puzzles to the Generic Fireball Framework
The first issue is representation. The generic testbed framework is driven by game states and moves. These are the only significant conceptual elements of this system, but this rather basic framework was also used to develop a complex bio-emulation (see Spring 2007's "Developing Biological Emulation Using a Generic Turn-based Testbed"). The latter seems to have no obvious linkage with the concept of a "game move", but actually the testbed proved to be an ideal framework for developing this. The mature support tools embedded in our generic framework immediately contributed to development. Given that, it is clear that moving from 2-player games to puzzles is only a small step.
The first requirement is simply to represent all stages in the puzzle and a means of managing the history of "plays" made. This maps very simply. For example consider a tile-sliding game: The "plays" would simply be "Slide tile". The move history would simply consist of a long sequence of slide tile moves. The puzzle engine would validate and execute these "slide" moves.
From this alone we have a means for "2" above.
Mapping "Move-it!" to the Framework
Taking a particular example from our web (below), the game "Move-it!" presents the user with the problem of moving a block from the top left to the bottom right hand corner. This simple looking puzzle is actually quite hard. If you consider this as an issue of puzzle creation, then the task becomes even harder.
In this case you could design a layout, but you would then need to solve it to check for the validity of the puzzle. Again, a genius might have no problem, but even a genius might make a mistake.
What is needed is a means of automatically solving the puzzle as set. We have already asserted that the move history for this game can represent the sequence needed to solve the puzzle, but the game above needs to be mapped to a program representation. This is easy, as follows:
| A | A | B | B | C | D |
| A | A | B | E | F | G |
| H | H | - | I | G | G |
| J | J | K | - | L | M |
| J | K | K | N | L | M |
The simple table above maps the puzzle to a 5 x 6 grid or array. Each tile has its own unique ID, represented by a letter. Each time a tile is slid, then each grid point with that ID also needs to move the same way. This provides an easy way of detecting legal plays (thereafter referred to just as "moves").
This offers a possibility of at least having a testbed that could allow the puzzle creator to automatically experiment with legal plays. It also allows tiles of any shape that can be mapped to a grid. However to solve it requires a bit more.
Using Minimax to solve "Move-it!"
The AI Factory generic AI toolset has a plug-in minimax solver. However this cannot literally be solved using minimax, as minimax depends on turn-based play. In this instance there is no opponent!
Those readers familiar with minimax might then realise that if the imaginary side was only allowed to play "Null moves", then this solves the problem as the opponent can elect to do nothing, although it means creating move trees flooded with null moves. This is not needed and actually our minimax framework can support just one side playing.
Given that, and considering the experience of tree searching, the problem of solving Move-it! can be compared to solving chess.
In those terms this already looks very promising. In the puzzle above, the number of legal moves is obviously going to be very small. In the position above it is only 3. In chess it is about 30, and yet this large number can be managed. If the average number is only 3, then a puzzle requiring 10 plays would generate only 3 to the power 10 possible positions = 59049. Considering that moves that reverse the previous move can be eliminated, and positions that have already been seen can be ignored, then the effective number of unique positions that can be created within 10 moves is actually very limited.
However this does not allow the inheritance of all minimax enhancements. In particular the powerful alpha-beta algorithm cannot be used. This is a pity as it can shrink a huge search tree to a very small one, but depends on refutation, and there is no refutation as there is no opponent trying to play refutation moves!
Exploiting the Solver for Puzzle Generation
With a minimax solver in use, this makes puzzle creation very easy. The creator need only input a position and do a test solve. The puzzle tested may be unsolvable or too trivial to solve. If it is valid, then the solver can also provide an assessment of the puzzle difficulty. This could be linked just to the number of moves to solve the puzzle, or maybe also take into account the number of possible moves available en-route to the solution.
Automatic Puzzle Creation
Given this basic premise of block sliding, then the next obvious step is to automatically generate layouts and test them. This could be entirely randomised, perhaps trying larger grids and grids with obstacles. Once set-up, the generator can try 1000s of possible layouts per minute. This can be tuned to allow a more creative variety of layouts, rather than endlessly re-test very similar layouts. This is where the puzzle creator's attention can be spent, in finding creative ways to automatically generate puzzles to be tried.
This solves the 4 basic requirements in the initial paragraph.
Using a Puzzle Inside Another Game
An adventure game may need embedded mini-games. To insert something like chess is easy as this would simply require a declaration of the type:
Class Chess;
This would then provide member functions to start up and run the game. E.g. Chess.Fb_InitialiseGame() and Chess. Fb_PlayMove etc. Puzzles can be handled the same way. However a puzzle might not be some board game, but some feature of the game. For example, we have a puzzle lock, which could be added to a game, as follows:
This elaborate lock allows the solver to move 5 horizontal and 5 vertical slide bars that consist of 10 linked blocks. Each bar of 10 blocks would only have 5 inside the lock at any one time. The blocks could be two types, Blocks with holes through them and solid blocks. The objective is to align 5 see-through blocks to line-up with the central cross (shown in blue). The lock then opens.
To use this the developer would insert a declaration for this puzzle, in the same way as chess above, and lock operations would be played as "moves". The puzzle engine would then return the current state of the lock, so it could be rendered, and whether the lock had been solved.
This is a powerful and easy drop-in solution that can be used to enrich games that need satisfying embedded tasks to be solved.
Conclusion
Puzzle creation can be easily managed inside our generic framework. It can be totally solved and thoroughly tested before moving it into any 3rd party product. This is particularly useful where we might need to create some unique puzzle for 3rd party use. Given that, it is highly desirable that the puzzle be thoroughly tested before it is embedded in the product. Of course the solver may also be inherited into the product, allowing the product to provide hints when the player is having difficulty.
This is a mature and well-managed system. We expect to see many 3rd party games ship with our embedded puzzles and games.
Daniel Orme and Jeff Rollason : March 2008
