私は、決して負けないほどスマートな Tic Tac Toe 用の AI を実装しようとしています。2 つの異なるアルゴリズムを試しましたが、AI はまだ間違いを犯します。
私はこのミニマックス アルファ ベータ プルーニング アルゴリズムから始めました。ライブデモはこちら: http://iioengine.com/ttt/minimax.htm
エラーなしで実行されますが、最初に左下隅を取得すると、下の行の他の 2 つの正方形のいずれかになります - AI はそれが来るのを認識しません。これはミニマックス アルゴリズムの欠陥ではないと確信しています。ソースにエラーが見られる人はいますか? デモページを調べてすべてを確認できますが、主な ai 関数は次のとおりです。
function bestMove(board,depth,low,high,opponent){
var best=new Move(null,-iio.maxInt);
var p;
for (var c=0;c<grid.C;c++)
for(var r=0;r<grid.R;r++){
if (board[c][r]=='_'){
var nuBoard=board.clone();
nuBoard[c][r]=getTypeChar(opponent);
if(checkWin(nuBoard,getTypeChar(opponent)))
p=new Move([c,r],-evaluateBoard(board,getTypeChar(opponent))*10000);
else if (checkScratch(nuBoard))
p=new Move([c,r],0);
else if (depth==0)
p=new Move([c,r],-evaluateBoard(board,getTypeChar(opponent)));
else {
p=bestMove(nuBoard,depth-1,-high,-low,!opponent);
}
if (p.score>best.score){
best=p;
if (best.score > low)
low=best.score;
if (best.score >= high) return best;
}
}
}
return best;
}
ネガマックスに慣れているなら、それも試してみました。このページから直接ロジックを持ち上げました。ライブデモはこちら: http://iioengine.com/ttt/negamax.htm
勝利状態に達すると、それはフリーズしますが、AI がかなり愚かであることはすでにわかります。コードの統合に何か問題がありますか?
これらのアルゴリズムが適切に実行されないコードの欠陥を見つけた場合はお知らせください。サンクス。
コードで更新:
function checkWin(board,type){
for (var i=0;i<3;i++)
if (evaluateRow(board,[i,0,i,1,i,2],type) >= WIN_SCORE
||evaluateRow(board,[0,i,1,i,2,i],type) >= WIN_SCORE)
return true;
if(evaluateRow(board,[0,0,1,1,2,2],type) >= WIN_SCORE
||evaluateRow(board,[2,0,1,1,0,2],type) >= WIN_SCORE)
return true;
return false;
}
function evaluateBoard(board,type){
var moveTotal=0;
for (var i=0;i<3;i++){
moveTotal+=evaluateRow(board,[i,0,i,1,i,2],type);
moveTotal+=evaluateRow(board,[0,i,1,i,2,i],type);
}
moveTotal+=evaluateRow(board,[0,0,1,1,2,2],type);
moveTotal+=evaluateRow(board,[2,0,1,1,0,2],type);
return moveTotal;
}