Алгоритмы расчета ходов логических игр.

[Slider]

Подскажите где можно посмотреть/загрузить. В частности интересуют алгоритмы от игр "Редн-зю", шахмат, шашек.

[Гром]

А в Яндексе искать не пробовал?

[Sashok]

Andrey MAG, а какие алгоритмы ты имеешь ввиду? Всякие там переборы в глубину и в ширину? Или тебя интересует что-то конкретное по поводу указанных игр?

[Slider]

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

[Sashok]

Andrey MAG, когда-то я этим немножко интересовался, попытаюсь изложить по памяти. Для более детальной информации ищи на инете, по ключевым словам ИИ и Программирование игр.

Вкратце, так. Ищем путь по графу. Каждый узел - позиция. Ребро - ход. Если найдешь хорошую оценочную функцию для позиции - совсем хорошо. Основных поисков 2 (со всякими модификациями): в ширину и в глубину.
В обоих методах есть два списка: найденных и пройденных позиций. Шаги:
1. Исходную позицию считаем текущей.
2. Для текущей позиции применяем по очереди все допустимые операторы (ходы), получая тем самым набор позиций, отстоящих от нее на 1.
3. Помещаем все позиции, найденные в шаге 2, в конец списка найденных(поиск в ширину) или в начало списка найденных(поиск вглубину).
4. Помещаем текущую в список пройденных.
5. Если список найденных не пуст, извлекаем оттуда первую позицию и считаем текущей.
6. Возвращаемся к п. 2.

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

[Slider]

Sashok, видел программку одну китайцем каким-то написанную. Она расчитывает форсированный выигрыш в ренд-зю. Причем в примере к ней была позиция где форсированный выигрыш получался ~60 ходов длиной. Расчет длился примерно 3-4 секунды. Вряд ли она просчитывает все возможные ходы на такую глубину. Скорее всего есть какие-то принципы отсева заведомо негодных позиций. Шахматные программы тоже наверняка таким фильтром пользуются. Этот момент для меня совершенно не понятен.
Либо здесь как в шутке мол "посади миллиард обезьян и заставь их миллиард лет стучать по пишущей машинке - в конце концов, одна из них напишет "Войну и мир"    :?:

[Alf]

Не знаю даже какие виды бывают кроме переборов ходов.   Да и для них какие-то алгоритмы нужны.

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

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

Типовое решение - построение так называемого AB-дерева, узлы которого соответствуют ходам игроков A и B. Сначала генератор ходов выдает допустимые в данной позиции ходы игрока А, из которых отбирается некоторое количество наиболее перспективных (при помощи оценочной функции и эвристик). Потом на каждый из возможных ходов аналогично перебираются ответные ходы противника В, из которых также отбираются наиболее сильные. И таким образом АВ-дерево строится на заданную глубину (например, 5 ходов). После этого выбирается тот ход, который ведет к вершине дерева с оптимальным значением оценочной функции. Получается что-то сродни классической оптимизации.
Описывались подобные алгоритмы в серии книг по искусственному интеллекту под редакцией Мото-Ока (если кто помнит, идейный отец проекта ЭВМ пятого поколения, после смерти которого проект как-то плавно сошел на нет). Номер тома, к сожалению, не помню, нужно рыться.
Если действительно интересно, найди полный дистрибутив Borland C++ 3.1 (думаю, это не проблема, поскольку здесь в клубе на нем обучают программированию новичков, и он где-то должен быть доступен для загрузки). Там в качестве примера идет шахматная программа. Погляди ее, она вполне работоспособна. По крайней мере, такого невеликого шахматиста, как я, уделывает на раз при достаточной глубине просмотра. Разберешься в ней - сможешь писать собственные, аналогичные.

[Alf]

Кстати, в журнале "В мире науки", помнится, читал статью, посвященную перспективным в те годы шахматным компьютерам "Deep Thought" и "Deep Blue". Конечно, статья научно-популярная, готовых алгоритмов там не найдешь. Но основные идеи почерпнуть можно. Если сможешь найти, рекомендую почитать.

[Slider]

Alf, как я понял основная сложность - сделать качественный оценочный алгоритм для отбора перспективных ходов. Я, например, в шахматы играю, но как-то попытался проанализировать как же я ходы делаю. Как лучший ход выбираю - так ничего и не понял. Как тот ёжик - чуть дышать не разучился.
В случае с матом - вроде понятно, единственный ход который приводит к выигрышу. Как можно оценить промежуточные позиции с точки зрения перспективности :?: :!:  Ну шахматы все-таки сложная игра, взять к примеру шашки. Каким образом, по каким критериям можно обсчитать позицию чтобы получить некий коэффициент "перспективности"?
Чисто интуитивно, например, понятно что один ход лучше другого. Как же это выразить в числовом выражении?

[NeilPryde]

А как тебе такой принцип оценки перспективности:
1) забираем шашку противника - +1
2) теряем свою шашку –1
3) становимся дамкой +2
4) противник выходит в дамки –3
Подсчитываем сумму в результате всех шагов. И последовательность ходов, для которой она будет максимальной, считаем наиболее перспективной.

[Alf]

Andrey MAG, оценочная функция - это действительно изюминка шахматной (да и любой другой) программы, все остальное - дело техники, причем в принципе несложной.
По моим обрывочным сведениям, в шахматных программах оцениваются:
- набор фигур (из литературы помнится примитивный критерий слон и конь = 3 пешки, ладья = 5 пешек, ферзь = 8, но это наверняка не догма, тем более что в зависимости от фазы игры и конкретной позиции слон с конем могут быть весьма неравноценны);
- развитие, например, слон, заблокированный стеной пешек, слабее слона, который держит под боем открытую диагональ;
- близость к центру: чем ближе фигура к центру доски, тем ее ценность выше;
- для пешек: сдвоенные теряют ценность, проходные - повышают;
- масса других секретов, благодаря которым одна программа обыгрывает другую.
Каждому критерию приписывается его удельный вес, и в результате сумма всех критериев, помноженных на удельный вес, дает значение оценочной функции. Тонкая настройка этих параметров и задает в результате "интеллект" программы.
Кстати, не помню уже, кто из разработчиков подобных программ выдумал такой способ оптимизации. Он заставил два экземпляра программы играть в цикле между собой. Одна программа является эталоном, а другая постоянно "мутирует", немного изменяя коэффициенты и удельные веса критериев.
Грубый пример: эталон считает, что ферзь= 8 пешек. "Мутант" меняет ценность своего ферзя до 9 пешек, после чего они играют 10 партий. Если "мутант" проигрывает, то мутация считается неудачной и откатывается обратно. Если же "мутант" начинает стабильно выигрывать, то более оптимальная комбинация копируется в эталон, а "мутант" продолжает свои эксперименты в другом направлении, пытаясь победить уже чуть более сильного соперника. В результате, как и в живой природе, удачные мутации закрепляются естественным отбором. В результате длительных экспериментов автору метода удалось подобрать довольно сильную комбинацию параметров.

[Sashok]

Andrey MAG, оценочную функцию используют, в частности, для ограничения перебора. 60 форсированных ходов просто означает, что небольшой набор ответов (в рэндзю, похоже, 1 или 2) на каждом форсированном ходу приводит к настолько лучшей позиции, чем все остальные ходы, что остальные можно и не рассматривать. Ничто, кстати, не мешает вставить такой алгоритм, когда ограничение перебора задается не глубиной, а количеством включенных в рассмотрение позиций. Тогда для форсированных последовательностей перебор автоматически получится глубже.

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

По поводу программирования игр, была у меня в начале 80-х книга Адельсона-Вельского (с соавторами) "Программирование игр" - там очень многое разбиралось.

Если у тебя ДЕЙСТВИТЕЛЬНО есть много времени, и ты хочешь взяться за ДЕЙСТВИТЕЛЬНО трудную и интересную задачу - займись программированием Го. У меня есть уверенность, что на сегодняшний день это наиболее трудная для программирования игра при сравнительно небольшом количестве правил.
Кстати, премия за создание программы, способной играть на равных с профессионалами (не с чемпионом, а со слабейшими профессионалами, т.е. уровень, в шахматных программах уже давно достигнутый) составляет не то 2 не то 5 миллионов долларов.

[Slider]

Sashok, Го это что за игра? Не другое название Ренд-зю случаем?
ЗЫ: А кто такие премии дает?    А то за такие деньги можно и постараться.

Alf, спасибо за интересную идею о самообучающихся программах, имхо, стоит попробовать.

Вроде ситуация начала немного проясняться и приобретать осязаемые очертания. Хотя, с другой стороны, во время игры (я во всяком случае) не перебираю всех возможных ходов. Часть из них сразу отбрасывается, как заведомо плохие. Среди них могут быть и ходы с жертвами фигур (на которые я [будь я на месте программы] бы непременно купился), за которые покупается хорошая позиция. Или наоборот, свои ходы с жертвами.
Да и вообще, по моим наблюдениям, в определенный момент времени формируется некая "Стратегия развития и обороны" с достаточно долговременными и неопределенными перспективами. Дальнейшие ходы (примерно 90%) делаются   исходя из этой стратегии. Оставшиеся 10% - являются вынужденными. Остальные варианты даже не рассматриваются. Имхо, такой подход значительно сокращает время на размышление. Тк. приходится обдумать всего 1 раз стратегию и при последующих ходах - продумать ее возможные модификации/корректировки.
При обычном же обсчете после каждого хода придется заново обсчитывать весь граф вариантов 99,9% которого уже расчитано. И так КАЖДЫЙ ход :!: Какой непроизводительный расход вычислительных ресурсов.
Я так думаю необходимо предусматривать каким-то образом реализованый алгоритм стратегии. Только вот каким :?:
Может у кого возникнут какие идеи по поводу его реализации :?:

[Alf]

Разумеется, ресурсы компьютера ограничены, поэтому просчитать все возможные ходы на достаточное число шагов вперед вряд ли возможно, время работы программы растет очень быстро. Поэтому хорошие программы имеют  правила, по которым заведомо слабые ходы отбрасываются. Это позволяет использовать освободившееся время на просчет более перспективных направлений на большую глубину.
С другой стороны, как определить, что ход заведомо слабый? Мне помнится, когда я в юности всерьез увлекался шахматами, я разбирал классическую партию, сыгранную молодым американцем Полом Мерфи против двух совещавшихся шахматистов. За давностью лет некоторые детали стерлись в памяти, но я точно помню, что Мерфи пожертвовал подряд две ладьи и, кажется, ферзя, а потом поставил мат то ли слоном, то ли конем.
Примитивная программа наверняка сочла бы такое направление слабым, поскольку временно возникает большой ущерб в фигурах, а конечный результат можно получить, только досчитав цепочку до конца. Так что опять же, если бы был единый надежный критерий для выигрыша, шахматы как игра тут же умерли бы.
По этой же причине мне не очень нравится идея хранения уже обсчитанного дерева в памяти и добавлять к нему только следующий ход. Допустим, твоя программа считает на 5 ходов вперед. Допустим, что есть сильный ход, который приведет к выигрышу после 6-го хода после жертвы на 4-м. Программа просчитывает ущерб от жертвы, но не видит выигрыша (он лежит на 1 ход глубже). То есть эта ветка будет выкинута из дерева как слабая и в дальнейшем просчитываться не будет. Если же просчитывать дерево по новой, есть вероятность не потерять подобные ветки. Но за это, разумеется, придется платить издержками повторных расчетов.

[Sashok]

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

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

[Sashok]

Andrey MAG, нет, Го - это не Рэндзю, хотя обе игры к нам пришли из Японии (а в Японию, похоже, из Китая очень много лет назад), и в Москве одно время даже клубы занимали одно и то же помещение. Из распространенных у нас "народных" игр Рэндзю ближе всего к крестикам и ноликам на бесконечной доске, а Го - к точкам.

Другие названия Го - Вей Чи (китайское) и Бадук (корейское), если поищешь на инете - наверняка найдешь. Если интересно - могу выслать подробную информацию.

Кто учредил премию я точно не помню, вроде бы господин Инь (Ing) - крупный спонсор Го с Тайваня. Узнать, конечно, можно, но над этим вопросом люди работают уже много лет - так ничего, даже близкого к достижениям компьютерных шахмат не получилось.

Кстати, если займешься Го, сразу учти, что:
1. Доска большая, простым перебором многого не достигнешь.
2. Оценочную функцию на протяжении игры придется менять несколько раз.
И т.д.

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

[Sashok]

Да, кстати, вот тебе одна ссылочка на програмирование Го. Там, конечно, нет общего описания, но, может быть, тебя заинтересует:
http://www.smartgo.com/implementation_details.htm

[Dimka]

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

[Sashok]

Dimka, а ты все-таки не ленись, опиши игру-то - интересно же!

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

[Dimka]

2. Не, если гоняться за сохранением высокой маневренности, то, мне кажется, можно никогда не добраться до победы.

1. Игра (старая советская настольная игрушка) Морская игра. Есть поле, на нём кораблики, которые могут ходить, поворачиваться, бить друг друга. Есть состояния со статусом гвардейского корабля (аналогично дамкам в шашках). Короче говоря, флотилия на флотилию. Целей несколько: захват базы противника, уборка минных полей противника, уничтожение кораблей противника. Главная цель: уничтожение всех кораблей противника. Отличием от шашек/шахмат является большое число возможных ходов на каждом следующем шаге, возможность стояния на месте (вращая кораблик), сложность в "загоне в угол" из-за размера поля и маневренности фигур, потребность решать сразу несколько задач: т.е. динамически определять наиболее выгодную стратегию для данного хода.

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

Игра, конечно, не задумывалась как компьютерная. Но вот смотрю на неё, и хочется... .

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

Примерно так выглядит более удачный пример .

[Dimka]

И ещё... В Яндексы всякие не посылайте . Я сам придумывать люблю, а не в книжках вычитывать.

У каждого свои развлечения  .

[alexthunder]

Mit Press Rules Of Play Game Design Fundamentals R

Book Info
Text offers an introduction to game design. Offers a unified model for looking at all kinds of games, from board games and sports to computer and video games. Includes concepts, strategies, and methodologies for creating and understanding games. For game scholars, game developers, and interactive designers. DLC: Computer games--Design.

Book Description
As pop culture, games are as important as film or television--but game design has yet to develop a theoretical framework or critical vocabulary. In Rules of Play Katie Salen and Eric Zimmerman present a much-needed primer for this emerging field. They offer a unified model for looking at all kinds of games, from board games and sports to computer and video games. As active participants in game culture, the authors have written Rules of Play as a catalyst for innovation, filled with new concepts, strategies, and methodologies for creating and understanding games.. Building an aesthetics of interactive systems, Salen and Zimmerman define core concepts like "play," "design," and "interactivity." They look at games through a series of eighteen "game design schemas," or conceptual frameworks, including games as systems of emergence and information, as contexts for social play, as a storytelling medium, and as sites of cultural resistance. Written for game scholars, game developers, and interactive designers, Rules of Play is a textbook, reference book, and theoretical guide. It is the first comprehensive attempt to establish a solid theoretical framework for the emerging discipline of game design

Качаем отсюда. Такие ссылки работают недолго, так что торопиться надо.
http://www.spinzone.org/forums/index.php?showtopic=5403

[Sashok]

И ещё... В Яндексы всякие не посылайте . Я сам придумывать люблю, а не в книжках вычитывать.

Я тоже.

А об игре такой я никогда не слышал - странно...

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

Насчет "армейской" иерархии я не совсем уверен. Пример возможного возражения: в соответствии с тактической ситуацией в данный конкретный момент выгодно передать часть кораблей группы, выполняющей задачу А, в группу Б. Решение об этом может принять только главковерх. Значит, в конце концов, главковерх все равно должен вникать в поведение индивидуальных кораблей, в том числе принимать решение о жертве кораблей, исходя из более важных целей.

Интересно. Держи в курсе.

[Dimka]

Игрушка для детей 10-12 лет. Ленинградское производственное объединение "Игрушка" (пластиковые фигурки), Издетельство "Малыш" (Москва) (коробка, поле и инструкция). Арт. Л1 085-01-9773, ОСТ 17-498-75. Прейскурант № 085-01-ЛГ/178. Цена 95 коп. Дата выпуска моего экземпляра 12.04.87.

Вот и услышал.  

К вопросу о вникании в частную ситуацию главковерха... В словах твоих истину вижу, но... по сути дела всё равно придётся составлять разные оценочные функции для решения каждой отдельно взятой частной задачи. Если отказаться от "дивизионной" организации управления, то всё сведётся к некоторой суперпозиции (а лучше, векторе) этих оценочных функций => результатом каждого хода будет являться действие в решении наиболее приоритетной на данном этапе задачи (значение какой функции перевесит остальные)... критерии сравнения... хотя, всё равно ход является перемещением лишь одной фигуры, а не нескольких сразу (по заданным правилам).

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

[Sashok]

alexthunder, что-то оно уже не грузится...

Dimka, игрушку я пропустил  - ну и ладно.
Твои изменения в правила, безусловно, введут существенные изменения, но не будет ли это некоторым нарушением принципа Оккама по отношению к играм?

В свое время я для себя выработал критерий качества игры (ИМХО, никому не навязываю), как отношение разнообразия возможностей (только не надо просить меня формализовать это описание - не умею :oops: ) к простоте правил. По этому критерию (опять же ИМХО) ведущей игрой в мире является Го. Между прочим, все описанное тобой (создание множества оценочных функций, определение их приоритетов на каждом ходу и даже в разных местах доски на одном ходу и т.д.) в Го присутствует, а различные виды фигур с множеством разнообразных правил - отсутствует.

[Dimka]

Сводится к Го... => см. выше, читать про миллионные премии