1

これが機能しない理由を理解するのを手伝ってください。コードにバグがあるのか​​、アルゴリズムに根本的な論理的な欠陥があるのか​​ どうかはわかりません。

私のアルゴリズムは minimax に基づいていますが、より単純な手法のためにヒューリスティック評価関数を使用しませんでした。単純な 3x3 tic tac toe は単純であるため、考えられる手ごとに考えられるすべてのゲーム結果を計算し、「スコア」が最も高いものを選択したいと思います。有効な動きの「トップ レベル」のベクトルと、対応する「スコア」の一致するサイズのベクトルを作成します。つまり、その動きに続くすべての可能な結果について、勝ちの場合は ++、損失の場合は -- です。

しかし、移動スコアのベクトルが奇妙な非対称値を取得しています。コードが機能したとしても、論理的には、最大の勝利と最小の損失につながるように計算された動きが、フォークなどの単純な戦術に盲目になる可能性はありますか? 私の本能はイエスと言っていますが、詳細な計算はしていません。 

char board [9] = { '.','.','.','.','.','.','.','.','.' };

int com_turn(int turn) 
    {
    char player=COM; // keeps track of current player  

    cout<<"Computer turn. \n";  

    vector<int> moves = get_valid_moves(board); // top level move list
    vector<int> m_scores (moves.size(), 0);  // top level move scores

    for (int m=0; m < moves.size(); m++) // eval each top level move
    {
        board[moves[m]] = player; // do move

        evaluate(board, turn, &m_scores[m], player); 
        cout<< m_scores[m] <<' '; // for debugging

        board[moves[m]]='.'; // undo move
    }

    int bestmove;
    for (int i=0; i < moves.size(); i++) // find best score
    {
        bestmove = max(bestmove, m_scores[i]);
    }
    for (int i=0; i < moves.size(); i++) // match to best move
    {
        if (bestmove == m_scores[i])
        {
            bestmove = moves[i];
            break;
        }
    }

    board[bestmove]=COM; // finally make com move
    print_board();
}

vector<int> get_valid_moves(char *board) 
{
    vector<int> vmoves;
    for (int i=0; i < 9; i++)
    {
        if (board[i]=='.') vmoves.push_back(i);
    }
    return vmoves;
}


void evaluate(char *board, int turn, int *mscore, char player) 
{
    if (check_win(board)) 
    {
        (player==HUMAN)? *mscore -= 1: *mscore += 1;  
        return;  
    }
    if (turn > 9) return;

    vector<int> child_moves = get_valid_moves(board);
    if (child_moves.size() < 1) return;

    (player==COM)? player=HUMAN: player=COM; // switch player

    for (int m=0; m < child_moves.size(); m++) 
    {
        board[child_moves[m]] = player; // do move

        evaluate(board, ++turn, mscore, player);

        board[child_moves[m]]='.'; // undo move
    }
}
4

1 に答える 1

2

参照渡しを使用するのではなく、評価してスコアを返すようにすると、どこに問題があるかがわかると思います。

Evaluate はミニマックス化する必要がありますが、現時点では、加算と減算の副作用のために、葉ノードの奇妙な合計を行っていると思います。

スコアの合計が正しくない理由

ボードがあるとします：

. . O
. . .
. X X

Oが成功しなかった場合、X の次の動きが勝つため、 O には1 つの手 (ブロック)しかありません。ただし、次のように、O で開始して他の動きを行い、O で勝利するゲーム パスはたくさんあります。

O2 O1 O
.  .  X1
.  X  X

番号は、どの手が最初に来たかを示します。

つまり、合計を求めるだけでは正しい答えは得られません。

値をツリーに渡すことをお勧めする理由は、ノードのスコアを子の関数として書き出す必要があるためです。現在のコードでは、関数は合計であり、ミニマックスでは、プレーヤーのターンに応じて、最小または最大のいずれかです。

于 2011-06-05T04:43:05.180 に答える