Combinatorial Optimization, Search
You may or may not be aware of the game of Peg Solitaire. This problem presents an alternative objective to Peg Solitaire. Given a board with some pegs, where you are allowed to make moves that are valid in Peg Solitaire,
Maximize the number of pegs that are left at the end.
Peg Solitaire is a Combinatorial game. There are finitely many states that are reachable from the initial state. We have to search the state space and end up at the most desirable state.
The desirability of the state is defined by the number of pegs that are left when there is no move possible.
This problem can be solved using some metaheuristic or search technique. Metaheuristics pick a candidate solution and try to optimize them. Search techniques try to explore the solution tree and percolate towards the optimal solution. This editorial is based on Beam Search, which was used by Hiroto while testing this problem.
- Beam Search builds the search tree similar to Breadth First search.
- We iterate through the nodes at each level and find the nodes for the next level.
- But, not all the nodes for the next level are stored. Only the top B nodes ordered by some scoring funciton (that scores each state).
- B is called the Beam Width.
- Beam Search always terminates at Final states (those from which you cannot go ahead).
- Hence we tradeoff Optimality (since we don’t go through the entire search tree) for Completeness (we will always have some valid solution).
Beam Search will always end up in a state in which no moves can be made, while pruning to find a state that hopefully has more pegs remaining.
The scoring function used by the tester’s solution is as follows
- Initialize the score with a large value.
- For every move that could be made, reduce the score by 1.
- For every empty cell, reduce the score by 0.7.
Can be found here.
Can be found here.