告诉你什么是优雅的代码(11)----html5 之XXOO棋
程序员文章站
2022-05-17 19:39:54
...
项目结项后的一星期又两天后,我又有了写些优雅代码的欲望。在我的记忆中, 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。