井字棋

井字棋 问题 井字棋是在一个九宫格中依次填入O或X，当横、竖、斜出现三个相同棋子时即获胜。以O先下为例，统计各自胜场和平局数。 完全穷举 讨论所有情况的胜率。 程序 class TicTacToeCompleteExhaustive: def __init__(self): self.total_states = 0 self.o_wins = 0 self.x_wins = 0 self.draws = 0 self.unfinished = 0 self.total_moves = 0 # 胜利条件 self.win_conditions = [ [0, 1, 2], [3, 4, 5], [6, 7, 8], # 横线 [0, 3, 6], [1, 4, 7], [2, 5, 8], # 竖线 [0, 4, 8], [2, 4, 6] # 对角线 ] def is_win(self, state, player): """判断某玩家是否获胜""" for condition in self.win_conditions: if all(state[i] == player for i in condition): return True return False def is_draw(self, state): """判断是否平局""" return 0 not in state and not self.is_win(state, 1) and not self.is_win(state, 2) def is_unfinished(self, state): """判断是否未结束""" return 0 in state and not self.is_win(state, 1) and not self.is_win(state, 2) def analyze_state(self, state): """分析一个状态并更新统计""" self.total_states += 1 # 计算当前状态的步数（已下的棋子数） moves_in_state = state.count(1) + state.count(2) self.total_moves += moves_in_state if self.is_win(state, 1): # O赢 self.o_wins += 1 elif self.is_win(state, 2): # X赢 self.x_wins += 1 elif self.is_draw(state): # 平局 self.draws += 1 elif self.is_unfinished(state): # 未结束 self.unfinished += 1 def dfs(self, state, is_o_turn): """深度优先搜索所有可能的局面（完全穷举）""" # 分析当前状态 self.analyze_state(state) # 如果游戏结束，不再继续搜索 if self.is_win(state, 1) or self.is_win(state, 2) or self.is_draw(state): return # 继续搜索下一步 for i in range(9): if state[i] == 0: state[i] = 1 if is_o_turn else 2 self.dfs(state, not is_o_turn) state[i] = 0 def analyze_all_states(self): """分析所有可能的游戏局面（完全穷举）""" print("开始分析井字棋所有可能局面（完全穷举）...") initial_state = [0] * 9 # 0表示空，1表示O，2表示X self.dfs(initial_state, True) # O先手 # 输出结果 print("\n=== 井字棋穷举分析结果（完全穷举）===") print(f"总局面数: {self.total_states:,}") print(f"O 获胜局面数: {self.o_wins:,}") print(f"X 获胜局面数: {self.x_wins:,}") print(f"平局局面数: {self.draws:,}") print(f"未结束局面数: {self.unfinished:,}") # 验证总数 total_calculated = self.o_wins + self.x_wins + self.draws + self.unfinished print(f"验证: {self.o_wins:,} + {self.x_wins:,} + {self.draws:,} + {self.unfinished:,} = {total_calculated:,}") print(f"与实际总数对比: {total_calculated} = {self.total_states}") print("\n=== 比例分析 ===") print(f"O 胜率: {self.o_wins/self.total_states*100:.4f}%") print(f"X 胜率: {self.x_wins/self.total_states*100:.4f}%") print(f"平局率: {self.draws/self.total_states*100:.4f}%") print(f"未结束率: {self.unfinished/self.total_states*100:.4f}%") # 计算平均深度 if self.total_states > 0: avg_moves = self.total_moves / self.total_states print(f"\n平均步数: {avg_moves:.2f}") return self.total_states # 运行分析 if __name__ == "__main__": analyzer = TicTacToeCompleteExhaustive() total = analyzer.analyze_all_states() 执行结果 ...