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.
- 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:
- Step Definition The type that defines step of the puzzle will be required to implement IStep(TKey) interface. The
Keyproperty 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.
- Step Comparison Steps are compared to each other based on
Keyproperty to determine which has better score. The comparison can be done in one of following ways:
- The Available Steps from Current Step Next step information can be provided by implementing
INextStepFactory(TKey, TStep)interface, or providing
After which, the algorithm can be run by invoking
FindSolution method with
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
DiscreteHeuristicComparer for different step comparison scenarios.
- If the
Keyproperty can be directly compared to each other without explicit h(n) function, by default,
DiscreteHeuristicComparerwill be used for faster step comparison.
- If h(n) function is explicitly needed in order to compare each of steps, the
HeuristicComparerwill be used to perform traditional estimation f(n) = g(n) + h(n).
Heuristic Function Preference
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.
Path Finding (AlgorithmForce.Example.PathFinding)
The example demonstrates the most common and traditional puzzle that use heuristic algorithms to solve.
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.
The project currently targets .NET Core and .NET Framework 4.5 or above.