|
мне понравилась одна мелкая Flash-игра, но комп в ней слабо играет. игра простая и я попытался было построить выигрышную стратегию, но не справился с этим. поэтому я зарегистрировался на этом форуме и задаю сейчас этот вопрос.
МОДЕЛЬ:
дебют игры пропускаю и сразу перехожу к тому, что меня интересует: на доске 6х6 полей находится какое-то количество фигур, наших и противника, достоинством от 1 до 6 включительно. ходы делаются поочерёдно, каждый ход- обязательное перемещение одной своей фигуры. все фигуры ходят и бьют одинаково: в любую из четырёх сторон, на примыкающее поле, соседнее по горизонтали или вертикали. причём, фигура может бить только те фигуры, достоинство которых не выше, чем у неё. исключение составляют фигуры достоинством 1 и 6: фигура достоинством 1 может побить фигуру достоинством 6, а фигура достоинством 6 не может побить фигуру достоинством 1.
игра заканчивается, если произошло одно из следующего:
1) у одной из сторон не осталось фигур (это выигрыш противной стороны)
2) совершено 25 полуходов без взятия подряд
во втором случае суммируются достоинства фигур каждой стороны и либо побеждает сторона с б0льшей полученной суммой, либо признаётся ничья.
ПРОБЛЕМА:
1) для любой ситуации распознавать, есть ли у нас выигрышная стратегия.
2) для ситуаций, в которых у нас есть выигрышная стратегия, найти эту стратегию.
РЕШЕНИЕ:
собственно, решения я не нашёл, потому и пришёл сюда. но какие-то соображения есть:
- если у нас и у противника ровно по одной фигуре и наша фигура может бить фигуру противника и наш ход и расстояние между фигурами- чётное количество полей, то у нас есть выигрышная стратегия, и она такая: поскольку расстояние между фигурами чётное, то обязательно получится, что разница одной из координат фигур(например, Х), будет больше. соответственно, ходим так, чтобы уменьшить эту(б0льшую) разницу. и, таким образом, постепенно загоняем врага в угол, где он вынужден подставиться под бой и погибнуть.
- если ход противника, и расстояние между фигурами- нечётное количество полей, то- тоже самое, но в дальнейшем я буду предполагать, что мы рассматриваем ситуации только тогда, когда наш ход. то есть, когда мы должны принять решение и ходить.
- если у нас одна фигура, а у противника более одной фигуры, то очевидно, что мы не можем вынудить противника ходить под бой. и остаётся только возможность выиграть по очкам.
- если у нас две фигуры, а у противника одна фигура, и хотя бы одна из наших фигур может бить фигуру противника, то точно так же одной фигурой загоняем фигуру противника в угол. а вторую фигуру убираем так, чтобы не мешала, не беспокоясь о том, что противник может её взять. (но как в такой ситуации оценить максимальное количество ходов до взятия?)
- если у нас больше двух фигур, а у противника одна фигура, то- тоже самое- отводим лишние фигуры в сторону и загоняем противника одной фигурой.. (тут уж, если мы не ведём по очкам, то проблема успеть взять, встаёт в полный рост.)
- если у нас более одной фигуры и у противника более одной фигуры, то наличие у нас выигрышной стратегии зависит от того, сможем ли мы побить одну фигуру противника так, чтобы свести ситуацию к той, в которой у нас есть выигрышная стратегия.
- в-общем, стратегия может быть в том, чтобы убить всех потенциальных убийц одной из старших своих фигур("5" или "6") и далее- уже беспрепятственно загонять одной своей фигурой фигуры противника поочерёдно.
сложность вызывают попытки проработать следующие моменты:
- как эффективно устранять или обходить свои фигуры, чтобы они не мешали загонять противника?
- как эффективно избегать побития противником своих фигур, которые нужны для выигрыша?
если рассматривать задачу с точки зрения построения компьютерной программы, то напрашивается полный перебор дерева возможных ходов на несколько ходов вперёд. но это жутко неэффективно: одна фигура может десяток ходов потратить на то, чтобы зажать в углу другую. здесь не шахматы, где ладья или королева за пару ходов куда угодно дойдёт и ситуация может резко измениться. здесь ситуация меняется постепенно и перебор получается неэффективным. поэтому вся надежда на правильный алгоритм. и я надеялся, что его построить реально, а получается, что- нет.
хорошим подспорьем в деле построения выигрышной стратегии может дать хорошая оценка ситуации. то есть, мы устраиваем полный перебор, например, на 3 полных хода(=6 полу-ходов) вперёд и, согласно хорошей оценке и минимаксной стратегии, понимаем, куда нам сейчас надо ходить.
вот, это и всё, до чего я смог додуматься. буду рад, если форумчане смогут помочь мне в доведении разработки выигрышной стратегии до победного конца.
мне кажется, что вопрос мой не слишком сложный для местных умов и достаточно интересный.
|
