NegaMax не работает должным образом - PullRequest
Новая
       6

NegaMax не работает должным образом

0 голосов
/ 28 февраля 2012

У меня проблема с реализацией простого NegaMax в моей шахматной программе.

В соответствии с несколькими сайтами negamax в моем коде должно выглядеть следующим образом: 

int Position::negaMax(int curr_depth, int depth) {
    cd = curr_depth-1;
    if (curr_depth==depth) return evaluate();

    int max = -500000;

    calc_moves(true);
    doBackup(cd);
    for (int i=0;i<mvSize[cd];i++) {
        move_figure(mvD[cd][i][0],mvD[cd][i][1],mvD[cd][i][2],mvI[cd][i][0],mvI[cd][i][1]);    
        int score = -negaMax(curr_depth+1,depth);
        cd--; undoMove(cd);

        if (curr_depth==1)
            cout << "Move: " << getMoveString(i) << ", Score: " << score << endl;        

        if (score>max)
            max=score;
   }
   return max;
}

Но с этим кодом яполучить этот вывод: 

Move: a2a3, Score: 0
Move: a2a4, Score: 0
Move: b2b3, Score: 0
Move: b2b4, Score: 0
Move: c2c3, Score: 0
Move: c2c4, Score: 0
Move: d2d3, Score: 0
Move: d2d4, Score: 0
Move: e2e3, Score: 0
Move: e2e4, Score: 0
Move: f2f3, Score: 0
Move: f2f4, Score: 0
Move: g2g3, Score: 0
Move: g2g4, Score: 0
Move: h2h3, Score: 0
Move: h2h4, Score: 0
Move: b1a3, Score: 0
Move: b1c3, Score: 0
Move: g1h3, Score: 0
Move: g1f3, Score: 0
score: 0

Это не может быть правильно, если я negaMax для ply3 из начальной позиции.

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

Move: a2a3, Score: 0
Move: a2a4, Score: 30
Move: b2b3, Score: 0
Move: b2b4, Score: 30
Move: c2c3, Score: 0
Move: c2c4, Score: 30
Move: d2d3, Score: 295
Move: d2d4, Score: 295
Move: e2e3, Score: 295
Move: e2e4, Score: 295
Move: f2f3, Score: 0
Move: f2f4, Score: 30
Move: g2g3, Score: 0
Move: g2g4, Score: 30
Move: h2h3, Score: 0
Move: h2h4, Score: 30
Move: b1a3, Score: 30
Move: b1c3, Score: 30
Move: g1h3, Score: 30
Move: g1f3, Score: 30
score: 295

Я пыталсяреализовать различные версии MinMax, NegaMax и AlphaBeta.Но я всегда получаю оценку 0. Я был бы очень благодарен за любые подсказки.

1 Ответ

0 голосов
/ 28 февраля 2012

Фактический скелет negamax, похоже, реализован правильно. (Однако я более привык видеть одну переменную глубины, передаваемую в рекурсивную функцию, которая вычитается из каждого слоя - и возвращает оценочный результат, когда он равен 0). Но трудно диагностировать вашу проблему как постороннего из-за большой зависимости от другого кода.

Вместо того, чтобы ловить рыбу для вас, я думаю, что было бы лучше научить вас ловить рыбу. Я бы посоветовал потратить некоторое время на создание процедуры, которая каким-то образом визуально выводит древовидную структуру и совокупный счет. Кажется, что у вас уже есть строительные блоки такой вещи. Сначала это может занять много времени, но в долгосрочной перспективе это очень поможет с отладкой - и, поверьте мне, с шахматным движком траление через это дерево будет, к сожалению, частой реальностью, особенно когда вы выполняете более непонятные движения, такие как en -пассант - это может вызвать всевозможные проблемы в дереве (я был там).

Попробуйте вывести что-то вроде этого: 

<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<move-white ---->
    <move-black ----><eval score>
    <move-black ----><eval score>
    <best black score>
<best white score>

... где ---- обозначает ход.

Очевидно, это будет намного больше и глубже, но, по крайней мере, вы сможете увидеть, что происходит, более дружественным для человека образом. Надеюсь, это поможет вам и в будущем. Как вы, вероятно, найдете, очень важно настроить хорошую систему отладки с шахматным движком.

...