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

Question

У меня проблема с внедрением простой 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. Я был бы очень благодарен за любые намеки.

Answer 1

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

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

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

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

... где обозначает движение.

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