Goal Heuristics
It is often the case that the possible worlds tree of some micro-world is too large for a brute force search. If the micro-world being described happens to be a game like chess, it is surely impractical to search beyond a few levels deep in the tree. Search heuristics are thus used to effectively prune the search tree by assigning a score to a set of possible worlds and picking the highest scoring one (or ones) as the only possibility.
Heuristics also go along with our intention to keep the parts of the program isolated, extensible, and understandable. Any number of them can be added or removed, effectively increasing the level of both intelligence and efficiency of the program.
Going back to the chess example, note that humans don't really play chess the way machines do: search of all possibilities. We usually have certain "strategies" in the back of our heads, such as "capture pieces when you can," "avoid being captured," "try to dominate the board with your pieces...", etc. Looking at the board at any given time, we make a move having one or some of those strategies in mind.
The chess SOL program also goes about making moves in a similar fashion. Below are three heuristic we added effectively implementing the strategies mentioned above. Nowhere else in the chess program but the heuristic section you may find a chess strategy/optimization. Any more number of heuristics may be added here that can make the program a stronger player, just as a novice player learns more and more strategies as she becomes a better player.
In the presence of multiple heuristics, the cumulative score for all of them is considered. Thus the weights given to the heuristics allow for prioritizing the heuristics. In chess, all pieces have a worth property, signifying their value relative to other kinds of pieces. Hence summing the worth of each players pieces constitutes an accurate measure of the player's piece strength. Here we're teaching the computer that capturing pieces is more important that having pieces in strategic locations:
heuristic Player win 1000 maximize its pieces worth sum. heuristic Player win 1000 minimize its opponent pieces worth sum. heuristic Player win 1 maximize its centralized-pieces size.
Heuristic Based Search Tree Pruning (or Branch Re-Ordering)
Most heuristic based search methods like A* use the given heuristic at every search tree level to reorder the open list (possible worlds) to explore. I experimented with a slightly different approach to implement the search, which has definite disadvantages as well as some nice properties.
I allow the user to set a parameter called max-time-ahead which tells how many levels of the search tree should we explore, before using any heuristics to give those possible worlds their scores. For instance, going back to the maze example we may have the following scenario.
----- possible worlds tree time
| ? | 4 A1 0
--------- / \
| | ? | 3 A2 B1 1
--------- / \ \
| ? | | ? | 2 A3 B2 B2 2
------------- /\ / | \ /\
| R | ? | X | 1 ----==-----------------
------------- possible worlds ---> | A4 B3 B1 C2 B1 A2 C2 | 3
A B C of t = 3 ----==-----------------
|
> at time 3 Robot position. | say B3 is picked
Possible World values (3 time unit from now): | by heuristics
{ B1, A2 , A4, C2, B3 } V
pruned tree
(move A1 to A2 is certain)
^ A1
| /
| A2
/ \
Repeat above by <---------- A3 B2
getting possible worlds / \ / | \
of t = 6 A4 B3 B1 C2 B1
(and t = 9, so on...)
Now the robot realizes it will not reach the goal before this time and has to use the heuristics to decide which one of the 5 possible worlds it best likes to be at time t= 3. What happens next is that only the tree branch with the root node at time currTime + 1, which includes the picked possible world is kept, and other branches are pruned. The search with the new pruned tree is repeated now with parameter max-time-ahead increased by itself, effectively searching up to t = 6, and the next time up to t = 9, and so on. This continues until the goal is satisfied, or no more possible worlds can be generated, the case of unsatisfiable goal.
The disadvantage of the current implementation is that the search tree is pruned instead of reordered. This makes the algorithm an incomplete one, which means may not find an existing solution because of a heuristic leading it into a trap. This will be implemented in the later versions.
There can be a trade off between heuristics and search speed. The advantage of this method is that it provides the user the flexibility of how much of heuristic evaluation should be done. While most heuristic based searches use max-time-ahead = 1 (follow heuristics at every search level), sometimes in the presence of many heuristics with very large possible worlds trees, the heuristic evaluations themselves may slow down the search. Our method gives more control over the amount of heuristic usage. Also this method still guarantees the found solution is optimum, by effectively implementing an Iterative Deepening Depth First Search (IDDFS).