Question 6
STATE SPACE SEARCH
Background:
Inspired by Pallanguzhi, a two-person game played in Tamil Nadu, Kerala, Sri Lanka and Malaysia. There are three cups A, B, C, where each cup holds zero or more shells (or seeds).
A state is represented by a three digit number "abc" where the digits a, b and c indicate the number of shells in cups A, B and C, respectively.
A single move (for a player) has three steps: select a non-empty cup, remove all shells from that cup and distribute those shells in a round-robin manner. Complete all three steps to complete a single move.
For example, select cup A, remove all shells from cup A (say N shells) then add one shell to each cup in the round-robin sequence B, C, A, B, C, A, …, until all N shells are placed.
If you select cup B, follow the round-robin sequence C, A, B, C, A, B, ...
If you select cup C, follow the round-robin sequence A, B, C, A, B, C, ...
Valid move: a move ("abc" ---> "xyz") is valid if the first digit 'x' (in output state) is greater than or equal to the first digit 'a' in input state.
MoveGen example: the state 360 allows only two moves: select cup A to generate 171, or select cup B to generate 522. Of the two moves, only 522 is valid, therefore, MoveGen(360) = [522].
Problem statement:
Begin with the state “123” and construct the state space by generating valid moves.
For each state "abc", the heuristic h(abc) = a + b, returns the number of shells in the first two cups as the heuristic value. Use this heuristic when required.
Complete the table shown above and complete the state space graph (call it Graph-123) and then answer the subquestions.
IMPORTANT: your MoveGen function must consider only valid moves and it must return the neighbours in ascending order.
Select the statements that are true in the state space Graph-123.
Every state is connected to every other state.
Every move is reversible.
The number of shells in each state is the same (constant).
None of these.