Minimax-Algorithmus gibt den besten Umzug nicht zurück

Question

Ich schreibe einen Othello-Motor mit Minimax mit Alpha-Beta-Beschneidung. Es funktioniert ok, fand aber das folgende Problem:

Wenn der Algorithmus feststellt, dass eine Position verloren geht, kehrt er als erwartet ein, aber in In diesem Fall kann ich den "besten" Verschieben nicht verfolgen ... Die Position ist bereits verloren, aber es sollte trotzdem einen gültigen Umzug zurückgeben (vorzugsweise ein Zug, der länger überlebt, wie die guten Schachmotoren tut). .

Hier ist der Code: generasacodicetagpre.

Ich nenne es mit: generasacodicetagpre.

Wenn eine verlorene Position (vorstellbar ist, dass es später verloren geht, wird später gesucht, dass die beste Variable oben gleich ist, ist der leere ungültige Bewegung, der als Argument übergab

Danke für jede Hilfe!

Answer 1

Your problem is that you're using -INFINITY and +INFINITY as win/loss scores. You should have scores for win/loss that are higher/lower than any other positional evaluation score, but not equal to your infinity values. This will guarantee that a move will be chosen even in positions that are hopelessly lost.

Answer 2

It's been a long time since i implemented minimax so I might be wrong, but it seems to me that your code, if you encounter a winning or losing move, does not update the best variable (this happens in the (board.checkEnd()) statement at the top of your method).

Also, if you want your algorithm to try to win with as much as possible, or lose with as little as possible if it can't win, I suggest you update your eval function. In a win situation, it should return a large value (larger that any non-win situation), the more you win with the laregr the value. In a lose situation, it should return a large negative value (less than in any non-lose situation), the more you lose by the less the value.

It seems to me (without trying it out) that if you update your eval function that way and skip the check if (board.checkEnd()) altogether, your algorithm should work fine (unless there's other problems with it). Good luck!

Answer 3

If you can detect that a position is truly won or lost, then that implies you are solving the endgame. In this case, your evaluation function should be returning the final score of the game (e.g. 64 for a total victory, 31 for a narrow loss), since this can be calculated accurately, unlike the estimates that you will evaluate in the midgame.