hardDynamic Programming 2DAI-applied~35 min
Probability an Agent Remains on the Board After K Moves
A reinforcement-learning agent moves like a knight on an n x n board, choosing each of 8 moves uniformly at random. Starting from a cell, compute the probability it is still on the board after exactly k moves.
Problem
On an n x n board, an agent starts at (row, column) and makes exactly k moves. Each move is one of the 8 knight moves chosen uniformly at random, even if it would leave the board (after which the agent stops). Return the probability the agent remains on the board after k moves.
Input
Integers n, k, row, and column.
Output
A floating-point probability.
Constraints
- 1 <= n <= 25
- 0 <= k <= 100
- 0 <= row, column < n
Examples
Example 1
Input
n = 3, k = 2, row = 0, column = 0
Output
0.06250
After two moves the survival probability is 0.0625.
Example 2
Input
n = 1, k = 0, row = 0, column = 0
Output
1.00000
With no moves the agent is trivially on the board.