Optimizing minimax algorithm
I've made games of TicTacToe and Nine Men's Morris in JavaFX and implemented AI for each. For Nine Men's Morris, I haven't yet implemented removing mills, so it is more like complex TicTacToe for now. I've used minimax algorithm with alpha-beta pruning, and while AI is doing quite decent moves, calculating move for Nine Men's Morris is painfully slow. If I let AI play the whole game, it takes a couple of minutes.
For evaluation function I've been using function that evaluates each line on board, where line value is:
100 for 3-in-a-line,
10 for 2-in-a-line,
1 for 1-in-a-line,
negative (-100, -10, -1) for opponent cells,
0 otherwise.
Minimax algorithm is more or less the same one, but for Nine Men's Morris, there are 16 lines to be evaluated, opposed to 8 lines in TicTacToe, yet AI is much slower for Nine Men's Morris.
How can I further improve performance of my AI?
I've been doing research on this matter, and I've found the idea to use neural networks to focus minimax search or replace evaluation function with neural network. Could these solutions improve performance of my AI?
There are many ways to improve over minimax with alpha beta pruning without involving neural networks. Furthermore, in a game like nine men's morris with a relatively low branching factor, neural networks are likely to hurt your AI more than help it. Instead I would look into different approaches. A useful option would be to use transposition tables with iterative deepening. This technique is very useful for this type of game. Here is a link to an article about transposition tables: https://en.wikipedia.org/wiki/Transposition_table
If you have more specific questions involving implementation, chess programming wiki has well written articles on the topic. Although related to chess, it should be easy to apply to any game.
https://chessprogramming.wikispaces.com/Transposition+Table
I have used this technique in both chess and connect 4 and seen fantastic reductions in search time. Post a comment if you want more specific information as to how to implement this technique.
链接地址: http://www.djcxy.com/p/56404.html上一篇: 如何计算minimax的启发式值
下一篇: 优化minimax算法