Comments 19
Манкала оказалась вполне крепким орешком, у меня часа полтора ушло на то чтобы найти выигрышную стратегию. Хотя, может так долго потому что играл в неё впервые в жизни.
Ирония заключается в том, что если первый игрок всё делает правильно — он выигрывает.
Так ли это? Второй игрок может загнать игру в цикл и таким образом не проиграть. Мне удалось 2 раза выиграть, но это, похоже, баг алгоритма. Алгоритм иногда делает разные ходы из одинаковых состояний. Можно пользоваться кнопкой назад и повторять ход и получать разные результаты. Или не получать, я не разобрался от чего это зависит. Немного странно, учитывая то, что автор писал про сложность (отсутствие) рандомизации.
Буду обозначать ход игрока буквами L и R — брать шарики из левой лунки или правой соответственно. Состояние игры буду обозначать четырьмя цифрами [ЛевыйВерх, ПравыйВерх, ЛевыйНиз, ПравыйНиз].
Перовые ходы из состояния [2222] должны быть такие:
L[3014] L[0116] R[0332 или 3032].
Если мы попали в состояние [0332], то нужно делать такие ходы, опять же обязательно:
R[0440*] L[3122] L[4013] L[1115] R[0332 или 3032].
В результате попадаем в одно из тех двух состояний, которые были после третьего хода.
Второй игрок может всегда сводить игру к состоянию [0322] и никогда не проигрывать.
* Иногда на этом ходу можно получить состояние [2141] вместо [0440]. Один раз я выиграл из этого состояния. Потом несколько раз в него попадал, но довести до победы не удавалось.
Состояние [3032] более сложное, там гораздо больше вариантов. Один раз удалось победить через эту комбинацию, но стратегию не нашел. Да это и не важно. Второй игрок не обязан допускать такое состояние.
Резюмируя: выигрышной стратегии у первого игрока, похоже, нет. Но если все время ходить правильно и не делать ошибок, то ошибки может делать алгоритм и тогда у него можно победить. Поправьте меня, если я ошибаюсь.
Анализ проводить не буду, для этого придется более глубоко разобраться в теме.
Но я попробовал нажимать стрелку вперед. В одной игре раз 5 прошел цикл (не совсем цикл, ходы немного отличались, но в итоге в игре несколько раз были одинаковые состояния, например [0440]). Надоело. А один раз я проиграл, но тогда первые 3 хода я сделал сам, чтобы не ждать.
Так что, все-таки, похоже на баг в алгоритме. Хотя с ним играть даже интереснее. Но это если играть, а не пытаться найти выигрышную стратегию, которой нет.
Поправьте, пожалуйста, в тексте, чтобы не вводить людей в заблуждение.
Ок, возможно не баг, а фича. Я не знаю, на сколько ходов вперед просчитывает алгоритм. Возможно, он действительно не досчитывает до того момента, когда проигрыш становится очевидным.
Я думаю, что Вам это проще проверить: увеличить глубину поиска, кешировать гарантировано проигрышные стратегии, возможно, есть смысл как-то отдельно обрабатывать циклы. И запустить просчитать все подольше. Выигрышная стратегия если и есть, то только у второго игрока. Но, скорее всего нет, т.к. скорее всего алгоритм бы ее нашел и использовал бы.
Вообще, работа прикольная, для поиграть — вполне устраивает. Притензия была только к наличию выигрышной стратегии. На самом деле я бы вообще не открыл игру, если бы не челлендж с поиском стратегии. Одно дело найти что-то хитрое, что сложно уложить в голове и совсем другое дело взять противника измором, надеясь, что он где-то провтыкает. Особенно при игре с ботом :)
Да, не проиграть первому игроку, наверно, можно. Второму — точно можно. Насчет гарантировано выиграть — не уверен.
Смотрите, у Вас на графике есть положение, крайнее справа, S1421:
2 1
1 4Ход левой нижней лункой, N2105:
2 1
0 5Из этого положения у Вас на графике 2 варианта: S1502 и S1520:
0 2 | 2 0
1 5 | 1 5Или я что-то не понимаю или у Вас ошибка. Оба варианта невозможны из состояния N2105.
Единственный вариант не проиграть это ходить в S0530:
3 0
0 5Поправьте меня, если я ошибаюсь.
Согласен, не разобрался в обозначениях и напутал.
Кстати, спасибо за карту. Не сразу понял, что на позиции можно кликать и это ссылки на игру с соответствующим состоянием. Очень прикольно.
По карте видно, что есть 3 позиции, в которой Север может сделать не правильный ход (и проиграть при правильной стратегии Юга). А может и не делать и не проигрывать. Т.е. эти плохие ходы для Севера бессмыслены, что я и хотел сказать в первом комментарии. Стратегия не проигрывать есть, а стратегии выигрывать нет.
В одном сценарии из 3х цепочка до проигрыша довольно длинная, а в двух других проигрыша Севера наступает через 6 ходов (суммарно для двух игроков). Скорее всего глубина просчета немного меньше.
Когда Вы тестировали, то первый игрок выигрывал скорее всего из-за того, что у него были более короткие цепочки ходов до проигрыша и алгоритм их опознавал раньше. Вот и все :)
Универсальный бот — это ещё та задача!
Dagaz: Сумма технологий