目前我正在用c ++开发奥赛罗/黑白棋游戏.我把它"完成"了,除了当我将它设置在产生半挑战AI的深度时,我用于计算机播放器的Minimax算法非常缓慢.
我的游戏的基本设置的是,板由2维阵列表示,与板上每个单元阵列中的分配值(xMarker,oMarker,或underscore).
这是迄今为止的minimax算法:
signed int Computer::simulate(Board b, int depth, int tempMarker) {
if (depth > MAX_DEPTH || b.gameOver()) {
int oppMarker = (marker == xMarker) ? oMarker : xMarker;
return b.countForMarker(marker) - b.countForMarker(oppMarker);
}
//if we're simulating our turn, we want to find the highest value (so we set our start at -64)
//if we're simulating the opponent's turn, we want to find the lowest value (so we set our start at 64)
signed int start = (tempMarker == marker) ? -64 : 64;
for (int x = 0; x < b.size; x++) {
for (int y = 0; y < b.size; y++) {
if (b.markerArray[x][y] == underscore) {
Board *c = b.duplicate();
if(c->checkForFlips(Point(x,y), tempMarker, true) > 0) {
int newMarker = (tempMarker == xMarker) ? oMarker : xMarker;
int r = simulate(*c, depth+1, newMarker);
//'marker' is the marker assigned to our player (the computer), if it's our turn, we want the highest value
if (tempMarker == marker) {
if(r > start) start = r;
} else {
//if it's the opponent's turn, we want the lowest value
if(r < start) start = r;
}
}
delete c;
}
}
}
return start;
}
该函数checkForFlips()返回在给定单元格中播放所产生的翻转次数.此时MAX_DEPTH设置为6,并且速度非常慢(每次播放可能大约10-15秒)
到目前为止,我想出的唯一想法是每次都存储树,然后从我离开的地方拿起,但我不确定如何实现它或者它是否太有效.任何想法或建议将不胜感激!