Tree Search

Perhaps Lemmings games can be solved by tree search. If so, it will be a very sophisticated tree search.

First consider a brute force tree search. The actions available to a player can be described as clicking the mouse on a point on the computer screen or doing nothing. An action must be taken at an interval which is less than one second but probably not less than 0.1 seconds. Some parts of the screen are unresponsive, so we can regard doing nothing as clicking on such a place. The screen on a Macintosh PowerBook is 640 by 480 pixels. Thus the player has 307200 choices every 0.1 seconds. Even if the player could fully observe the consequences of each choice, the branching would make tree search of the full tree impractical.

What must we do to make tree search practical? We first consider what reduced trees to use.

1. First we merge clicking on a quality and clicking on a lemming. This eliminates clicking on two qualities in succession which is pointless, because it is equivalent to clicking on just the second quality.
2. Now we choose a delay. The most common delay is 0. Most things you want to do are done right away. We want to avoid branching on times, so we choose times by events. Thus a clicking on a lemming x the next time lemming y is in a particular position is a choice. Naturally, the case when x is the same lemming as y is distinguished. We still have too much branching, and we must avoid even generating far-off events, at least until earlier parts of the tree have been searched.
3. Now we choose the lemming that is to receive the quality. For this search to be efficient the lemmings must be grouped into equivalence classes, so that choosing only one lemming in the class is considered. Indeed when the lemmings are close-packed, it isn't possible to tell one walker from another.
4. A common type of event is a lemming, usually the one we intend to modify, reaching a certain place. If the lemmings move a pixel at a time (I'm not sure of that.), then there may be several hundred places where we could choose to click. Many consecutive choices of place are likely to be equivalent. In order to reduce the choices the horizontal or vertical line along which the lemming is moving has to be divided into heuristically different regions.

   Here is where a real difference with previous tree search algorithms must arise. We need to make the division into regions tentative and refine it when this is required.

5. In one game a blocker is needed, but 100 percent of the lemmings are to be saved, and therefore having to blow up the blocker will result in a loss. The tree search, if that's what it is, is abstract, because the node in which there is a leftover blocker is at the end of the game. The solution is that the very first lemming out of the source is made into a floater (parachute jumper) and then into a blocker; the very last lemming out of the source is made into a floater and then into a miner just when it can undermine the blocker. Both then parachute to safety.

   If we regard this reasoning as tree search, then we consider making the first lemming a blocker as one edge, solving the rest of the game as another edge, see this as a loss, backtrack and put in making the lemming into a floater, etc.

6. In building a bridge or digging a hole, the precise place to start is sometimes important.

The tree search algorithm itself has to decide in what order to examine the nodes. This clearly requires many heuristics, most specifically considering first moves and sequences of moves that are recommended by some idea. This is where logic will surely creep back in.

It is not obvious that all the above notions can be applied in a way that will reduce the tree search to managable proportions. My intuition is that they can--at least for large parts of many games.

Tree search often becomes inefficient when the sequence of actions is divisible into actions that independently affect different aspects of the situation. Then it usually becomes more efficient to break the problem into parts that can be thought about separately, solve the separate problems and then combine the results. I think Lemmings has enough of this to make a pure tree search algorithm impractical.

(This phenomenon is what makes pure tree search algorithms impractical for Go. It is necessary to consider the different areas of the board separately and then combine the results.)

Lemmings tree searches can include retries of games. For example, when the place a blocker is exploded turns out to be too thin, the program should take another look at the pixel map and find a thicker place to explode the blocker.