Dynamic Programming21 sections · 916 units
Open in Course

Lessons from Knight Probability

summary

1.1. State includes position and moves remaining. Both affect the probability.

2.2. Transition sums weighted contributions. Each of 8 moves contributes 1/81/8 of its probability.

3.3. Off-board states return 00. They're absorbing states where the process "fails." This pattern repeats in almost all probability DP: state captures position and progress, transitions are weighted sums, and boundaries return 00 or 11.