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()

import tkinter as tk
from tkinter import messagebox, ttk
import itertools

class TicTacToeAnalyzer:
    def __init__(self):
        self.states = {}  # 存储所有局面
        self.unique_states = set()  # 去重后的局面
        self.state_list = []  # 状态列表，用于浏览
        self.current_state_index = 0  # 当前浏览的状态索引
        
        self.o_wins = 0
        self.x_wins = 0
        self.draws = 0
        
        # 对称变换策略
        self.symmetry_strategies = [
            [0, 1, 2, 3, 4, 5, 6, 7, 8],  # 原始
            [2, 1, 0, 5, 4, 3, 8, 7, 6],  # 垂直翻转
            [6, 7, 8, 3, 4, 5, 0, 1, 2],  # 水平翻转
            [8, 5, 2, 7, 4, 1, 6, 3, 0],  # 主对角线翻转
            [0, 3, 6, 1, 4, 7, 2, 5, 8],  # 副对角线翻转
            [6, 3, 0, 7, 4, 1, 8, 5, 2],  # 旋转90度
            [8, 7, 6, 5, 4, 3, 2, 1, 0],  # 旋转180度
            [2, 5, 8, 1, 4, 7, 0, 3, 6],  # 旋转270度
        ]
        
        # 胜利条件
        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]              # 对角线
        ]
        
        self.setup_gui()
    
    def setup_gui(self):
        self.root = tk.Tk()
        self.root.title("井字棋穷举分析器")
        self.root.geometry("900x700")
        
        # 控制面板
        control_frame = tk.Frame(self.root)
        control_frame.pack(pady=10)
        
        tk.Button(control_frame, text="开始分析", command=self.start_analysis, 
                 bg="lightblue", font=("Arial", 12)).pack(side=tk.LEFT, padx=5)
        
        tk.Button(control_frame, text="重置", command=self.reset, 
                 bg="lightcoral", font=("Arial", 12)).pack(side=tk.LEFT, padx=5)
        
        # 统计信息
        stats_frame = tk.Frame(self.root)
        stats_frame.pack(pady=10)
        
        self.stats_text = tk.Text(stats_frame, height=6, width=80, font=("Courier", 10))
        self.stats_text.pack()
        
        # 进度条
        self.progress = ttk.Progressbar(self.root, orient=tk.HORIZONTAL, length=600, mode='determinate')
        self.progress.pack(pady=10)
        
        # 棋盘显示区域
        board_frame = tk.Frame(self.root)
        board_frame.pack(pady=10)
        
        # 创建棋盘
        self.canvas = tk.Canvas(board_frame, width=300, height=300, bg="white")
        self.canvas.pack()
        
        # 状态信息和导航
        nav_frame = tk.Frame(self.root)
        nav_frame.pack(pady=10)
        
        # 状态信息
        self.state_info = tk.Label(nav_frame, text="请点击'开始分析'进行穷举分析", 
                                  font=("Arial", 12), fg="blue")
        self.state_info.pack(pady=5)
        
        # 导航按钮
        nav_buttons = tk.Frame(nav_frame)
        nav_buttons.pack(pady=5)
        
        tk.Button(nav_buttons, text="第一个", command=self.first_state, 
                 font=("Arial", 10)).pack(side=tk.LEFT, padx=5)
        
        tk.Button(nav_buttons, text="上一个", command=self.prev_state, 
                 font=("Arial", 10)).pack(side=tk.LEFT, padx=5)
        
        tk.Button(nav_buttons, text="下一个", command=self.next_state, 
                 font=("Arial", 10)).pack(side=tk.LEFT, padx=5)
        
        tk.Button(nav_buttons, text="最后一个", command=self.last_state, 
                 font=("Arial", 10)).pack(side=tk.LEFT, padx=5)
        
        # 结果显示区域
        result_frame = tk.Frame(self.root)
        result_frame.pack(pady=10, fill=tk.BOTH, expand=True)
        
        # 创建滚动条
        scrollbar = tk.Scrollbar(result_frame)
        scrollbar.pack(side=tk.RIGHT, fill=tk.Y)
        
        self.result_text = tk.Text(result_frame, height=10, width=80, font=("Courier", 9),
                                  yscrollcommand=scrollbar.set)
        self.result_text.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
        scrollbar.config(command=self.result_text.yview)
    
    def draw_board(self, state):
        """绘制棋盘和棋子"""
        self.canvas.delete("all")
        
        # 绘制棋盘网格
        for i in range(1, 3):
            # 垂直线
            self.canvas.create_line(i * 100, 0, i * 100, 300, width=2)
            # 水平线
            self.canvas.create_line(0, i * 100, 300, i * 100, width=2)
        
        # 绘制棋子
        for i in range(9):
            row = i // 3
            col = i % 3
            x = col * 100 + 50
            y = row * 100 + 50
            
            if state[i] == 1:  # O
                self.canvas.create_oval(x-30, y-30, x+30, y+30, width=3, outline="blue")
            elif state[i] == 2:  # X
                self.canvas.create_line(x-30, y-30, x+30, y+30, width=3, fill="red")
                self.canvas.create_line(x-30, y+30, x+30, y-30, width=3, fill="red")
    
    def rearrange(self, state, strategy):
        """根据对称策略重新排列局面"""
        return [state[i] for i in strategy]
    
    def get_symmetric_states(self, state):
        """获取所有对称局面"""
        symmetric_states = []
        for strategy in self.symmetry_strategies:
            symmetric_states.append(self.rearrange(state, strategy))
        return symmetric_states
    
    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 get_state_key(self, state):
        """获取状态的规范表示（用于去重）"""
        # 找到所有对称状态中最小的元组表示
        symmetric_states = self.get_symmetric_states(state)
        min_state = min(tuple(s) for s in symmetric_states)
        return min_state
    
    def dfs(self, state, is_o_turn):
        """深度优先搜索所有可能的局面"""
        state_key = self.get_state_key(state)
        
        # 如果已经访问过这个状态，直接返回
        if state_key in self.states:
            return
        
        # 记录这个状态
        self.states[state_key] = {
            'state': state.copy(),
            'o_win': self.is_win(state, 1),
            'x_win': self.is_win(state, 2),
            'draw': self.is_draw(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_game(self):
        """分析所有可能的游戏局面"""
        self.states = {}
        initial_state = [0] * 9  # 0表示空，1表示O，2表示X
        self.dfs(initial_state, True)  # O先手
        
        # 将状态转换为列表，用于浏览
        self.state_list = list(self.states.keys())
        
        # 统计结果
        self.o_wins = sum(1 for data in self.states.values() if data['o_win'])
        self.x_wins = sum(1 for data in self.states.values() if data['x_win'])
        self.draws = sum(1 for data in self.states.values() if data['draw'])
        
        return len(self.states)
    
    def format_state(self, state):
        """格式化显示局面"""
        symbols = {0: ' ', 1: 'O', 2: 'X'}
        lines = []
        for i in range(0, 9, 3):
            line = ' | '.join(symbols[state[i+j]] for j in range(3))
            lines.append(line)
        return '\n---------\n'.join(lines)
    
    def display_current_state(self):
        """显示当前状态"""
        if not self.state_list:
            return
        
        state_key = self.state_list[self.current_state_index]
        state_data = self.states[state_key]
        state = state_data['state']
        
        # 绘制棋盘
        self.draw_board(state)
        
        # 更新状态信息
        status = "O胜" if state_data['o_win'] else "X胜" if state_data['x_win'] else "平局" if state_data['draw'] else "未结束"
        self.state_info.config(text=f"状态 {self.current_state_index+1}/{len(self.state_list)} - {status}")
        
        # 在结果区域显示详细信息
        self.result_text.delete(1.0, tk.END)
        self.result_text.insert(tk.END, f"局面 #{self.current_state_index+1}:\n")
        self.result_text.insert(tk.END, self.format_state(state))
        self.result_text.insert(tk.END, f"\n\n状态: {status}")
        self.result_text.insert(tk.END, f"\n局面代码: {state}")
    
    def first_state(self):
        """跳转到第一个状态"""
        if self.state_list:
            self.current_state_index = 0
            self.display_current_state()
    
    def prev_state(self):
        """跳转到上一个状态"""
        if self.state_list and self.current_state_index > 0:
            self.current_state_index -= 1
            self.display_current_state()
    
    def next_state(self):
        """跳转到下一个状态"""
        if self.state_list and self.current_state_index < len(self.state_list) - 1:
            self.current_state_index += 1
            self.display_current_state()
    
    def last_state(self):
        """跳转到最后一个状态"""
        if self.state_list:
            self.current_state_index = len(self.state_list) - 1
            self.display_current_state()
    
    def display_results(self):
        """显示分析结果"""
        total_states = len(self.states)
        
        stats_info = f"""
=== 井字棋穷举分析结果 ===
总局面数（去重后）: {total_states}
O 获胜局面数: {self.o_wins}
X 获胜局面数: {self.x_wins}
平局局面数: {self.draws}
未结束局面数: {total_states - self.o_wins - self.x_wins - self.draws}

O 胜率: {self.o_wins/total_states*100:.2f}%
X 胜率: {self.x_wins/total_states*100:.2f}%
平局率: {self.draws/total_states*100:.2f}%
"""
        self.stats_text.delete(1.0, tk.END)
        self.stats_text.insert(1.0, stats_info)
        
        # 显示第一个状态
        if self.state_list:
            self.current_state_index = 0
            self.display_current_state()
    
    def update_progress(self, value):
        """更新进度条"""
        self.progress['value'] = value
        self.root.update_idletasks()
    
    def start_analysis(self):
        """开始分析"""
        self.stats_text.delete(1.0, tk.END)
        self.stats_text.insert(1.0, "正在分析井字棋所有可能局面...\n这可能需要几秒钟...")
        
        # 模拟进度更新
        for i in range(101):
            self.update_progress(i)
            self.root.after(10)  # 小延迟让界面更新
        
        # 执行分析
        total_states = self.analyze_game()
        
        # 显示结果
        self.display_results()
        
        messagebox.showinfo("分析完成", f"分析完成！共找到 {total_states} 个不同的局面。")
    
    def reset(self):
        """重置分析"""
        self.states = {}
        self.state_list = []
        self.current_state_index = 0
        self.o_wins = 0
        self.x_wins = 0
        self.draws = 0
        self.progress['value'] = 0
        self.stats_text.delete(1.0, tk.END)
        self.result_text.delete(1.0, tk.END)
        self.state_info.config(text="请点击'开始分析'进行穷举分析")
        self.canvas.delete("all")
    
    def run(self):
        """运行应用程序"""
        self.root.mainloop()

# 创建并运行分析器
if __name__ == "__main__":
    analyzer = TicTacToeAnalyzer()
    analyzer.run()