Справка по отладке алгоритма Tic Tac Toe C ++ - PullRequest
Новая
       10

Справка по отладке алгоритма Tic Tac Toe C ++

1 голос
/ 05 июня 2011

Пожалуйста, помогите мне понять, почему это не работает. Я не знаю, есть ли ошибка в моем коде, или мой алгоритм принципиально ошибочен.

Мой алгоритм основан на минимаксе, но я упустил эвристическую функцию оценки для более простой техники. Из-за простоты простого крестика 3х3 я просто хочу рассчитать все возможные результаты игры для каждого потенциального хода и выбрать тот, который набрал наибольшее количество очков. Я создаю вектор допустимых ходов «верхнего уровня», а также вектор соответствующего размера для их соответствующих «показателей» - т.е. за каждый возможный исход, следующий за этим ходом: ++ за победу и - за поражение.

Однако мой вектор оценок хода получает странные несимметричные значения. Хотя даже если бы код работал, логически возможно, что ход, рассчитанный на то, чтобы привести к наибольшему количеству побед и наименьших потерь, был бы слепым к простой тактике, такой как форк? Мои инстинкты говорят да, но я не проработал математику в деталях. 

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
    }
}

1 Ответ

2 голосов
/ 05 июня 2011

Я думаю, вы поймете, в чем проблема, если вы сделаете оценку, верните счет, а не используете возврат по ссылке.

Оценка должна быть минимаксной, но сейчас я думаю, что она делает какую-то странную суммуузлов листа из-за побочного эффекта сложений и вычитаний.

Почему суммирование результатов неверно

Предположим, у меня есть доска: 

. . O
. . .
. X X

Тогда у О есть только один ход (блок), потому что следующий ход Х выиграет, если О не сделает этого.Тем не менее, существует множество игровых путей, которые начинаются с О и делают другие ходы, причем О выигрывает, например: 

O2 O1 O
.  .  X1
.  X  X

Где число указывает, какой ход пришел первым.

Итак,просто получение суммы не даст вам правильного ответа.

Причина, по которой я рекомендую передавать значения вверх по дереву, заключается в том, что это вынуждает вас выписывать, какой счет наузел как функция детей.В вашем коде сейчас функция - это сумма, в минимаксе это либо мин, либо макс, в зависимости от хода игрока.

...