Question 7
SEARCH
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties. Note: When we say a node (a state) is inspected/expanded/refined it means: the node (the state) is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Note: RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 positions inspected by Depth-First Search. List the positions in the order they are inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions. NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: X,Y,Z Answers Case Sensitive : No