项目结项后的一星期又两天后,我又有了写些优雅代码的欲望。在我的记忆中, AI,在这个领域,我已近乎白痴,剪枝与寻路两种剑法,就在我离开校园之后,连同那蓝天碧草,相忘于江湖。江湖中只有 SSH, 只有 SQL,只有汽车尾气,只有路人甲 。
在计算机语言的圣经中,hello world 永远写在第一页。如果没有翻开过这一页,就如少男没有翻开过少女的裙子一样充满好奇,困惑。我难以忍受这种无知,于是我的剑出鞘,翻开AI的圣经,在屏幕上刻下 XXOO 四个字。
XXOO棋 ,又称井字棋 。三子相连者胜 ,四子相连 ...是不可能的。
算法就如剑法,速度,力度都要有良好的把握。理解剑法,需要口诀。算法亦然。
以下为负值最大函数的伪代码:
int NegaMax(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = -NegaMax(depth - 1); // 注意这里有个负号。
UnmakeMove();
if (val > best) {
best = val;
}
}
return best;
}
理解了这个伪代码,也就明白了我的代码:
this.getPos = function(depth){
var best = -Chess.MAX-1;
var index = -1;
var val = 0;
for (var i = 0 ;i < board.length; i++) {
if(board[i] == 0){
board[i] = aiChess;
val = -negaMax(depth -1,personChess);
board[i] = 0;
if(val > best){
best = val;
index = i;
}
}
}
return index;
}
function negaMax(depth,chess) {
var best = -Chess.MAX;
if (depth <= 0) {
return evaluate(chess);
}
var val = 0;
for ( var i = 0 ;i < board.length; i++) {
if(board[i] == 0){
board[i] = chess;
val = -negaMax(depth -1,chess==Chess.X?Chess.O:Chess.X);
board[i] = 0;
if(val > best){
best = val;
}
}
}
return best;
}
function evaluate(chess) {
var xMark = 0;
var oMark = 0;
var X = Chess.X;
var O = Chess.O;
var f = chess == X?1:-1;
for (i = 0; i < 8; i++) {
var sum = board[pos[i][0]] + board[pos[i][1]] + board[pos[i][2]];
if(sum == 3*X)
return f*Chess.MAX;
if(sum == 3*O)
return -f*Chess.MAX;
if(sum < O)
xMark++;
if(sum % O == 0)
oMark++;
}
return f*(xMark - oMark);
}
附件有完整的代码,可直接开启你的XXOO。