9井字游戏Ku的状态复杂度和博弈树复杂度是多少？

谢谢邀请我。状态复杂度指的是游戏中可能出现的状态的数量。博弈树的复杂程度是指从开始到结束有多少种可能性可以下棋。状态复杂度和博弈树复杂度很难精确计算，只是给出1可信上界。具体数据参考:中国的棋步有限吗？如果是有限的，有没有可能先走或后走的人会赢？具体到井字游戏，这是1非常简单的棋。首先，考虑状态复杂性。每个格子做多有三种可能:黑白:空。9格最多有3 ^ 9 = 19和68310 ^ 5种可能。即状态复杂度小于10 5。然后考虑博弈树的复杂程度。1人有9招(其实考虑到对称性，只有3招:中、侧、角)。但是数量级是一样的。别管他。)第二个人最多8招。那么1的人最多有7招，以此类推。最终博弈树的复杂度上限是9！=362,88010^6。再加上对称性，一些小技巧(只有1个选择，不离开这里就输了)等。，实际上状态复杂度和博弈树复杂度都远小于估计值。所以井字游戏是1非常简单的棋。手算1也可以得到最佳策略:第一个最佳策略是走中间。如果双方都选择了最佳策略，最后就是平局。