2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 выигрышная стратегия Tomb Chess
Сообщение26.02.2013, 18:43 


26/02/13
7
мне понравилась одна мелкая Flash-игра, но комп в ней слабо играет. игра простая и я попытался было построить выигрышную стратегию, но не справился с этим. поэтому я зарегистрировался на этом форуме и задаю сейчас этот вопрос.

МОДЕЛЬ:
дебют игры пропускаю и сразу перехожу к тому, что меня интересует: на доске 6х6 полей находится какое-то количество фигур, наших и противника, достоинством от 1 до 6 включительно. ходы делаются поочерёдно, каждый ход- обязательное перемещение одной своей фигуры. все фигуры ходят и бьют одинаково: в любую из четырёх сторон, на примыкающее поле, соседнее по горизонтали или вертикали. причём, фигура может бить только те фигуры, достоинство которых не выше, чем у неё. исключение составляют фигуры достоинством 1 и 6: фигура достоинством 1 может побить фигуру достоинством 6, а фигура достоинством 6 не может побить фигуру достоинством 1.

игра заканчивается, если произошло одно из следующего:
1) у одной из сторон не осталось фигур (это выигрыш противной стороны)
2) совершено 25 полуходов без взятия подряд
во втором случае суммируются достоинства фигур каждой стороны и либо побеждает сторона с б0льшей полученной суммой, либо признаётся ничья.

ПРОБЛЕМА:
1) для любой ситуации распознавать, есть ли у нас выигрышная стратегия.
2) для ситуаций, в которых у нас есть выигрышная стратегия, найти эту стратегию.

РЕШЕНИЕ:
собственно, решения я не нашёл, потому и пришёл сюда. но какие-то соображения есть:

- если у нас и у противника ровно по одной фигуре и наша фигура может бить фигуру противника и наш ход и расстояние между фигурами- чётное количество полей, то у нас есть выигрышная стратегия, и она такая: поскольку расстояние между фигурами чётное, то обязательно получится, что разница одной из координат фигур(например, Х), будет больше. соответственно, ходим так, чтобы уменьшить эту(б0льшую) разницу. и, таким образом, постепенно загоняем врага в угол, где он вынужден подставиться под бой и погибнуть.

- если ход противника, и расстояние между фигурами- нечётное количество полей, то- тоже самое, но в дальнейшем я буду предполагать, что мы рассматриваем ситуации только тогда, когда наш ход. то есть, когда мы должны принять решение и ходить.

- если у нас одна фигура, а у противника более одной фигуры, то очевидно, что мы не можем вынудить противника ходить под бой. и остаётся только возможность выиграть по очкам.

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

- если у нас больше двух фигур, а у противника одна фигура, то- тоже самое- отводим лишние фигуры в сторону и загоняем противника одной фигурой.. (тут уж, если мы не ведём по очкам, то проблема успеть взять, встаёт в полный рост.)

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

- в-общем, стратегия может быть в том, чтобы убить всех потенциальных убийц одной из старших своих фигур("5" или "6") и далее- уже беспрепятственно загонять одной своей фигурой фигуры противника поочерёдно.

сложность вызывают попытки проработать следующие моменты:
- как эффективно устранять или обходить свои фигуры, чтобы они не мешали загонять противника?
- как эффективно избегать побития противником своих фигур, которые нужны для выигрыша?

если рассматривать задачу с точки зрения построения компьютерной программы, то напрашивается полный перебор дерева возможных ходов на несколько ходов вперёд. но это жутко неэффективно: одна фигура может десяток ходов потратить на то, чтобы зажать в углу другую. здесь не шахматы, где ладья или королева за пару ходов куда угодно дойдёт и ситуация может резко измениться. здесь ситуация меняется постепенно и перебор получается неэффективным. поэтому вся надежда на правильный алгоритм. и я надеялся, что его построить реально, а получается, что- нет.

хорошим подспорьем в деле построения выигрышной стратегии может дать хорошая оценка ситуации. то есть, мы устраиваем полный перебор, например, на 3 полных хода(=6 полу-ходов) вперёд и, согласно хорошей оценке и минимаксной стратегии, понимаем, куда нам сейчас надо ходить.

вот, это и всё, до чего я смог додуматься. буду рад, если форумчане смогут помочь мне в доведении разработки выигрышной стратегии до победного конца.

мне кажется, что вопрос мой не слишком сложный для местных умов и достаточно интересный.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group