TicTacToe with minimax and MCTS algorithm

Introduce

分别用minimax算法和蒙特卡洛树搜索实现了井字棋

minimax

minimax.py

最基础的minimax算法，无任何剪枝

minimax_optimize.py

在minimax的基础上使用了alpha-beta剪枝，降低时间复杂度

MCTS

MCTS.py

使用纯随机的方式搜索模拟，性能较差，且胜率低

MCTS_optimize.py

引入了启发式算法，提高性能和胜率

ATTENTION

我在MCTS_optimize.py中使用“-------------------------”标出了一个位置，你可以修改两个参数：C(计算UFC时的系数)和iterations(迭代次数)来调整电脑下棋的强度，具体内容见MCTS_optimize.py

Extra

理论上来说你无法击败使用minimax算法的电脑，击败MCTS有可能（如果C设置的很极端或者iteration设置的很小的话）
如果你击败了minimax算法的电脑，请务必联系我，下次让你去单防alphago (:

Usage

所有文件之间没有依赖关系，你可以把整个文件夹下载下来，也可以单独下载你想要的代码。运行的时候单独运行你需要的代码即可
推荐环境：python3.10(其他版本不知道行不行)

Personal Words

如果有bug请联系我，万分感谢
Thanks for your watching

ENGLISH VERSION

Introduce

The Tic-tac-toe is realized by minimax algorithm and Monte Carlo tree search respectively

minimax

minimax.py

The most basic minimax algorithm, without any pruning

minimax_optimize.py

Based on minimax, alpha-beta pruning is used to reduce time complexity

MCTS

MCTS.py

Using pure random search simulation, the performance is poor, and the win rate is low

MCTS_optimize.py

Heuristic algorithm is introduced to improve performance and win rate

ATTENTION

I use "-- -- -- -- -- -- -- -- - - - - - - - - - - - - - - - - -" to mark a position in MCTS.py and MCTS_optimize.py. You can modify two parameter: C(coefficient when calculating UFC) and iterations(number of iterations) to adjust the intensity of computer chess, see MCTS_optimize.py for details

Extra

In theory, you can't defeat a computer using minimax, it's possible to defeat MCTS (if the C Settings are too extreme or the iteration Settings are too small). If you beat the minimax algorithm computer, please be sure to contact me and let you go to single-defense alphago next time (:

Usage

There are no dependencies between all the files, you can download the entire folder or download the code you want individually. When running, just run the code you need separately
Recommended environment: python3.10(maybe python>3.6 is ok. I haven't tried it)

Personal Words

Please contact me if there are any bugs. Thank you very much
Thanks for your watching