heuristic suite

Heuristic Suite

Important Note

The project is no longer under maintenance. Please visit LINQ to A* for latest version.

Overview

Heuristic Suite is an experimental implementation of a series of heuristic algorithms in generic programming. The project is aimed to provide an infrastructure that can be applied to any puzzle - as long as the puzzle can be resolved with the algorithm.

Implemented algorithms:

• A*
• Iterative Deepening A* (IDA*)
• Best First Search
• Recursive Best First Search (RBFS)

The implementation is fully object-oriented and takes advantages of built-in .NET Framework comparison mechanism such as IComparer(T) and IEqualityComparer(T) to create great compatibility with .NET Standard and entire .NET ecosystem. Source code can be easily brought to other platforms such as Unity and Xamarin.

Solving Puzzle with Algorithm

In order to apply the algorithm to puzzle, following implementations are needed:

1. Step Definition The type that defines step of the puzzle will be required to implement IStep(TKey) interface. The Key property serves two purposes:

   • To test whether two steps are equivalent. For example: same position on the board.
   • To compare two steps to determine which has better score. For example: the distance between position A and goal, and the distance between position B and goal, the closer one is scored better.

2. Step Comparison Steps are compared to each other based on Key property to determine which has better score. The comparison can be done in one of following ways:

   • The IComparable(TKey) implementation.
   • A customized IComparer(TKey) instance.
   • The explicitly given h(n) function where parameter n is the Key.

3. The Available Steps from Current Step Next step information can be provided by implementing INextStepFactory(TKey, TStep) interface, or providing NextStepFactory delegate.

After which, the algorithm can be run by invoking FindSolution method with from and goal steps as parameters. If the solution exists, each of steps can be obtained by calling Enumerate method. Steps can be Reversed before the enumeration starts.

Heuristic Comparer and Discrete Heuristic Comparer

The project provides HeuristicComparer and DiscreteHeuristicComparer for different step comparison scenarios.

• If the Key property can be directly compared to each other without explicit h(n) function, by default, DiscreteHeuristicComparer will be used for faster step comparison.
• If h(n) function is explicitly needed in order to compare each of steps, the HeuristicComparer will be used to perform traditional estimation f(n) = g(n) + h(n).

Heuristic Function Preference

The HeuristicFunctionPreference enumeration enable users to change the balance of estimation f(n) = g(n) + h(n). When two steps are evaluated same score, the enumeration decides which function, g(n) or h(n), will be considered first. The changed balance can affect the behavior of heuristic algorithm.

Examples

• Path Finding (AlgorithmForce.Example.PathFinding)

  The example demonstrates the most common and traditional puzzle that use heuristic algorithms to solve.

• 8-Puzzle (AlgorithmForce.Example.EightPuzzle)

  The example demonstrates how to solve the 8-puzzle with heuristic algorithm. The initial and goal steps of the puzzle are shown below:

• Coins Flipping Puzzle (AlgorithmForce.Example.CoinsFlipping)

  This example demonstrates how the game AI solves the coins flipping puzzle. In the puzzle, only a pair of adjacent coins is allowed to be flipped over at same time. All ten coins that are head is the goal. The puzzle is inspired by brilliant.org.

More examples will be added in future.

Platform

The project currently targets .NET Core and .NET Framework 4.5 or above.