1

私は、決して負けないほどスマートな 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;
    }
4

2 に答える 2

2

問題はあなたのevaluateBoard()機能にあります。評価関数は、ミニマックス/ネガマックス アルゴリズムの心臓部です。AI の動作が悪い場合、問題は通常、移動ごとのボードの評価にあります。

ボードの評価では、勝つ手、ブロックする手、フォークになる手の 3 つを考慮する必要があります。

勝利の動き

静的評価関数は、移動の結果が現在のプレーヤーの勝ちか負けかを知る必要があります。移動によって現在のプレーヤーが負ける場合は、非常に小さい負の数 (通常の移動よりも小さい) を返す必要があります。移動によって現在のプレーヤーが勝利した場合、非常に大きな正の数 (通常の移動よりも大きい) を返す必要があります。

覚えておくべき重要なことは、この評価は、AI が行っている順番のプレーヤーに関連している必要があるということです。AI が現在、人間のプレイヤーがどこに移動するかを予測している場合、評価は人間のプレイヤーの視点からボードを見る必要があります。AI の手番の場合、評価はコンピューター プレイヤーの視点からボードを見なければなりません。

ブロックの動き

評価関数を実行すると、AI は実際には人間のプレイヤーをブロックすることが有益であるとは考えません。あなたの評価関数は、利用可能な移動の数を数えて結果を返すだけのように見えます。代わりに、AI が勝つのに役立つ動きに対して、より大きな正の数を返す必要があります。

ブロッキングを説明するには、プレーヤーが開いた行、列、または対角線に 2 つのトークンを持っているかどうかを把握し、ブロッキング スクエアを他のどのスクエアよりも高くスコアリングする必要があります。したがって、コンピューターが移動する番であり、人間のプレイヤーが空いている列に 2 つのトークンを持っている場合、列の 3 番目のマスには正の大きな数字が必要です (ただし、勝利のマスほど大きくはありません)。これにより、コンピューターはその正方形を他の正方形よりも優先します。

勝つ動きとブロックする動きを考慮に入れるだけで、かなりうまくプレイできるコンピューターを手に入れることができます。

フォークの動き

分岐移動は、コンピューターに問題を引き起こします。主な問題は、コンピューターがそれ自体の利益に対して「賢すぎる」ことです。人間のプレイヤーが常に最良の動きをすることを前提としているため、人間のプレイヤーが実行できるすべての動きが最終的に敗北に終わる状況を見つけることができるため、ボード上で可能な最初の動きを選択するだけです。他には何も関係ありません。

あなたの例を見てみると、これが起こることがわかります: 人間のプレーヤーは左下でプレーし、コンピュータは中央の上でプレーします。

   | O |
---+---+---
   |   |
---+---+---
 X |   |   

人間のプレイヤーが右下隅に移動すると、コンピューターは、その動きをブロックしようとすると、人間のプレイヤーが行う最善の動きは中央の正方形を取ることであり、その結果、フォークと人間の勝利になります。 (人間は間違いやすいので、これはすぐには起こりませんが、コンピューターはそれを知りません)。

   | O |
---+---+---
   | X |
---+---+---
 X | O | X  

コンピューターは人間の勝利をブロックするかブロックしないかにかかわらず負けるため、人間をブロックすると、実際には可能な限り低いスコアがバブルアップします (コンピューターの損失になるため)。これは、コンピュータが可能な限り最高のスコアを取ることを意味します - 中央の四角。

このような状況を処理する最善の方法は何かを理解する必要があります。それは知っておくべきことです。

于 2013-10-16T14:47:44.257 に答える
1

Tic-Tac-Toe の純粋な Minimax 実装により、AI が負けることはありません。最悪の場合、引き分けになるはずです。

純粋な Minimax とは、すべての可能な移動 (実際には、ある移動から別の移動への遷移) を調査し、その移動と遷移のツリーを作成する実装を意味します (ツリーの上部にある空のボードから始まり、次のように分岐します)。考えられるすべての最初の動き、次に考えられるすべての 2 番目の動きなど)。

(最初からツリー ノード内のすべての位置をレンダリングするのではなく、特定の深さだけをレンダリングするヒューリスティック ミニマックスもあります。)

ツリーは、ゲームを終了する (X 勝、O 勝、または引き分け) ボード上の位置のみをリーフとして持つ必要があります。Tic-Tac-Toe (3x3 ボード) を分類するためのこのようなツリーには、5477 個のノードが含まれます (上部のすべて空のボードはカウントされません)。

このようなツリーが作成されると、ゲームがどのように終了したかを評価するだけで、リーフが直接スコアリングされます。AI が勝利したボード状態を含むリーフ ノードの最高スコア、引き分けのスコアは 0、人間が勝利したボード状態のノードの最低スコアです。プレイヤーが勝った。

(ヒューリスティック Minimax では、部分ツリーの葉を評価し、それに応じて最小/0/最大スコアを割り当てる「推測」関数を作成する必要があります。この実装では、AI が最後に負ける可能性があります。 、そしてその可能性は、部分的なゲームの状態を評価する際の「ゲスティメーター」機能の良さに反比例します。)

次に、ツリーのすべての中間の非リーフ ノードが、それらの子に基づいてスコア付けされます。明らかに、これはボトムアップで行います。最初は、最下位の非リーフ ノードのみが子 (リーフ ノード) をスコアリングし、そこから独自のスコアを引き出します。

(Tic-Tac-Toe のコンテキストでは、Minimax のヒューリスティックな実装を作成しても意味がありません。5477 + 1 ノードのツリーをレンダリングし、それらすべてをスコアリングするのはかなり安価だからです。この種の実装は、多くの分岐 (特定のゲーム状態で可能な多くの動き) があるため、チェスなどのように、低速でメモリを大量に消費する完全なツリーが作成されます))

最終的に、考えられるすべての Tic-Tac-Toe ゲームを含むデータ構造と、人間のプレイヤーが行うあらゆる動きに対応して実行するのに最適な動きは何かという正確なアイデアが得られます。そのため、Tic-Tac-Toe ルールの仕組みにより、Minimax AI は勝つ (人間のプレイヤーが少なくとも 1 つの重大なミスを犯した場合) または引き分け (人間のプレイヤーが常に可能な限り最善の動きをする場合) のみになります。これは、誰が最初の動きをしても当てはまります。

私はこれを自分で実装しましたが、期待どおりに機能します。

ここにいくつかの細かい点があります(私が少し苦労しました):

  • ボードを評価するために使用する関数が適切に機能することを確認してください。つまり、X と O のどちらかが勝ち/引き分けの状況が発生したときに正しくスポットされるようにします。この関数は、構築時に Minimax ツリーのほぼすべてのノードで使用されます。バグアウトすると、一見動作しているように見えますが、実際にはコードに欠陥があります。この部分を広範囲にテストします

  • 特に中間ノードをスコアリングしている場合 (ただし、次の移動を検索している場合も同様)、ツリーを適切にナビゲートするようにしてください。単純な解決策は、ツリーの横に、ツリーの深さのレベルごとに各中間ノード (非リーフ ノード) を含むハッシュ テーブルを作成することです。こうすることで、ボトムアップ スコアリングを行うときに、適切なタイミングですべてのノードを確実に取得できます。

于 2014-08-19T15:38:44.803 に答える