Problem
A game is played by first placing a token on the bottom right square of an $n \times n$ grid. A coin is then tossed to decide how you will move your token. - If it is a head you move your token one square up - If it is a tail you move your token one square left The game is won if you reach the top left square on the board. The game is lost if you move off the board. You may find it useful to simulate a number of games before attempting the questions below. iii. What is the probability of winning the game on a $4 \times 4$ board?
Solution
Step 1 ：Calculate the probability of winning the game on a $4 \times 4$ board using dynamic programming.
Step 2 ：Start from the bottom right square and move towards the top left square, calculating the probability of winning from each square.
Step 3 ：\(\boxed{0.3125}\) is the probability of winning the game on a $4 \times 4$ board.
