DD2380 presentation - Search - Fishing Derby

# DD2380 presentation - Search - Fishing Derby ## Q1: Describe the possible states, initial state, transition function of the game. Possible states: Uniquely defined by (depth, player_hook_{x,y}, opponent_hook_{x,y}, points, fishes_on_hooks) - Depth: Assuming fish positions are deterministic according to time and independent of moves depth keeps track of the state of fishes. - Points+fishesonhooks: Makes the state independent of the path to get to the current state. - Hookx,y: The current position of the hooks are obviously part of the state. Initial state: initial_tree_node() <- state_hash Transition function: node.compute_and_get_children() ? (up down right left stay) Should be noted that we also filter these moves such that if up_move == stay_move for example we will not consider the up_move. ## Q2: Describe the terminal function of the Game We chose the terminal state to be the following: $$ |\texttt{points_player} - \texttt{points_opponent}| > \sum _{fish \in uncaught \ fishes} |\texttt{fish_points}[\texttt{fish}]| $$ Note the absolute value inside the sum. The reasoning behind this terminal state is that if the difference in points between two players can not be overcome by the fishes left, then the winner of the game has already been decided. The absolute value is due to the existance of negative valued fishes. Catching a fish with a negative value is equivalent to the opponent catching a positive fish of the same value. ## Q3: Why is $\nu = Score(Green) - Score(Red)$ a good heuristic? It correctly estimates the state of the game in the terminal state, and it somewhat accurately estimates the probability of winning. Therefore, if we had infinite computing power and could reach the state where we catch the next fish this heuristic would work. But it is not a good heuristic in the sense of estimating the goodness of a move before actually catching it. This will result in a worse ability to search the game tree and if a significant depth can't be reached the state will not be improved. ## Q4 *When does ν best approximate the utility function, and why?* At the very end, when the precise scores, and nothing else, are what determine the winner. Why? In the terminal state, the winner of the game is entirely determined by the score. It is obvious why it follows it. It is also somewhat accurate directly after both players having just caught a fish. Why? Then the hooks are in the same y-position, and the boats' x-positions are (likely?) going to be above the caught fishes' original position, which likely gives neither player an advantage after catching the fish. ## Q5: Can you provide an example of a state s where ν(A,s) > 0 and B wins in the following turn?  Yes. If A has 9 points and B has 8, but B is one move away from reeling in a fish worth 10 points, then B will win with 18 points versus 9. ## Q6: Will η suffer from the same problem (referred to in Q5) as the evaluation function ν?  **Example:** Lets say boat A is to the left of boat B and that there are two fishes left worth 1 point each, 1 and 2 steps to the right of boat B respectively. Assume that the score is 1 for A and 0 for B. In this case there are 3 terminal states. If A catches any fish he will win and if B catches both fishes he will win instead. $\eta(A)$ will therefore be positive as there are 1 more winning terminal state for A than B. But as the boats can not pass each other B will win the game. This can happen in 1 move if the second fish also moves one step to the left after B has made his move.