8x8棋盘岩石移动期望步数：Python模拟与数学结果不符排查

将岩石置于8x8棋盘左下角单元格，每秒以相等概率随机移动至可达单元格，求首次到达右上角的期望移动步数。数学解法得出答案为70，但编写的Python模拟代码运行结果约为30，需排查代码逻辑错误或验证数学解法是否正确。

Python模拟代码 #

import math
import random

def main():
    board_size = 8
    iterations = 1000000
    Test(board_size, iterations)

# 返回沿指定方向移动指定步数后的新位置
def Move(pos, direction, steps):
    if direction == "U":
        return (pos[0], pos[1] + steps)
    elif direction == "D":
        return (pos[0], pos[1] - steps)
    elif direction == "L":
        return (pos[0] - steps, pos[1])
    elif direction == "R":
        return (pos[0] + steps, pos[1])
    
# 返回随机方向随机步数移动后的新位置
def RandomMove(pos, board_size):
    direction = random.choice(GetPossibleDirections(pos, board_size))
    steps = GetSteps(direction, pos, board_size)
    return Move(pos, direction, steps)

# 返回当前位置可移动的方向列表
def GetPossibleDirections(pos, board_size):
    result = ["U", "D", "L", "R"]
    if pos[0] == 0:
        result.remove("L")
    elif pos[0] == board_size - 1:
        result.remove("R")
    if pos[1] == 0:
        result.remove("D")
    elif pos[1] == board_size - 1:
        result.remove("U")
    return result

# 返回指定方向上可移动的随机步数
def GetSteps(direction, pos, board_size):
    if direction == "U":
        return math.floor(random.random() * (board_size - pos[1] - 1) + 1)
    elif direction == "D":
        return math.floor(random.random() * (pos[1]) + 1)
    elif direction == "L":
        return math.floor(random.random() * (pos[0]) + 1)
    elif direction == "R":
        return math.floor(random.random() * (board_size - pos[0] - 1) + 1)

# 模拟从左下角到右上角的移动，返回所需步数
def Simulate(pos, board_size):
    steps = 0
    while pos != (board_size - 1, board_size - 1):
        pos = RandomMove(pos, board_size)
        steps += 1
    return steps

# 运行指定次数的模拟并输出平均步数
def Test(board_size, iterations):
    print("Simulating", iterations, "games on a", board_size, "x", board_size, "board...")
    total_steps = 0
    for i in range(iterations):
        total_steps += Simulate((0, 0), board_size)
        progress_bar(i + 1, iterations)
    print("Average number of moves:", total_steps / iterations)

# 进度条显示函数
def progress_bar(current, total, bar_length=20):
    fraction = current / total
    arrow = int(fraction * bar_length - 1) * '-' + '>'
    padding = int(bar_length - len(arrow)) * ' '
    ending = '\n' if current == total else '\r'
    print(f'Progress: [{arrow}{padding}] {int(fraction*100)}%', end=ending)

if __name__ == "__main__":
    main()

数学解法说明 #

采用第一步分析法：设非边缘非终点区域的期望步数为x，与终点相邻的行和列区域的期望步数为y，可得方程：

x = (12/14)(x+1) + (2/14)(y+1)  
y = ( 7/14)(x+1) + (6/14)(y+1) + (1/14)  

解得x=70，即8x8棋盘的期望步数为70。

3x3棋盘示例 #

x = (2/4)(x+1) + (2/4)(y+1)  
y = (2/4)(x+1) + (1/4)(y+1) + (1/4)

x = 10

内容的提问来源于stack exchange，提问作者Locothomas