алгоритм negamax для игры 3 в ряд на сетке 3х4 (строки х столбцы)

Question

Я борюсь с алгоритмом negamax для игры 3 в ряд на сетке 3х4 (строки х столбцы).Играется как хорошо известная 4-в-рядная, то есть части выпадают (НЕ как TicTacToe).Давайте назовем игроков R и B. У R был первый ход, ходы B контролируются Negamax.Возможные ходы: 1, 2, 3 или 4. Эта позиция, о которой идет речь, была достигнута после R: ход 3 -> B: ход 1 -> R: ход 3:

  1   2   3   4<br />
|   |   |   |   |<br />
|   |   | R |   |<br />
| B |   | R |   |<br />

Сейчас, чтобы защитить от хода 3 с помощью R, B должен сыграть сам ход 3, но он отказывается это сделать.Вместо этого он играет ход 1, и игра заканчивается после следующего хода R.

Я потратил весь день на поиск ошибки в моей реализации negamax, которая, кстати, прекрасно работает для сетки 3x3, но я не смогне могу найти.

Тогда я начал думать: еще одно объяснение поведения алгоритма negamax состоит в том, что B теряется во всех вариациях, несмотря ни на что, после того как R начинает игру с ходом 3 на сетке 3x4.*

Кто-нибудь может опровергнуть это предложение или указать мне доказательство (которое я бы предпочел ;-))?

Спасибо, RSel

Answer 1

Это, на самом деле, выигранная игра с самого начала. И может быть воспроизведено довольно легко вручную. Я предполагаю, что B избегает всех однократных выигрышей для R, и будет отмечать ходы по цвету и выделять место в сетке, где происходит игра.

1. R3,1
  ... B1,1  2. R3,2 B3,3  3. R4,1 B2,1  4. R2,2 (and R1,2 or R4,2 wins next)
  ... B2,1  2. R3,2 B3,3  3. R2,2 B2,3  4. R1,1 (and R1,2 or R1,3 wins next)
  ... B3,2  2. R2,1 (and R1,1 or R4,1 wins next)
  ... B4,1  2. R2,1 B1,1  3. R3,2 B3,3  4. R2,2 (and R1,2 or R4,2 wins next)

Что касается вашего алгоритма, я собираюсь предложить вам изменить его так, чтобы он предпочел выигрыши, а не убытки, и отдаленные потери, а не проигрыши. Если вы сделаете это, он будет «стараться», чтобы избежать неизбежной потери.

Answer 2

Доказательство того, что B3 также проигрывает:

B3: R (1,2,4) -> R1; B (1,2,4) -> B2 (проигрывает), поэтому B1; R (2,4) -> R2 теряет, поэтому R4; B (2,4) -> B2 проигрывает, поэтому B4; R проигрывает на любом из вариантов сейчас ... так что R1 проиграет за R - значит, R не выберет его.

B3: R (1,2,4) -> R2 проигрывает с B2, поэтому R не выберет его B3: R (1,2,4) -> R4; B2 (принудительный); R2 (принудительный); B проигрывает на следующем ходу R

... итак, B3 проигрывает как B, так и B1 ... так что B проиграл в этой ситуации.

РЕДАКТИРОВАТЬ : На всякий случай, если кому-то интересно узнать о других параметрах B (2,4) в конце "B3: R (1,2,4) -> R1; B (1, 2,4) -> B2 (проигрывает), поэтому B1"... они не имеют значения, поскольку, как только красный выберет R1, этот сценарий показывает, что B (компьютер) может выбрать B1 и выиграть. Неважно, что случится с другими вариантами выбора Б - этот выбор победит, поэтому красный не может выбрать R1 или проиграет.