Предпросчет возможных ходов в игре Nine Men's Morris (Мельница)

@Ksardas_178 · Регистрация: 01.01.2018

Студворк — интернет-сервис помощи студентам

Сообщение от Sun Serega

Что именно вы пытаетесь сделать?

Пытаюсь сделать хотя бы частичный предпросчет возможных ходов в игре Nine Men's Morris (Мельница). Была мысль построить что-то вроде дерева развития игры, выкинуть лишние варианты и использовать как базу знаний. А в имена папок/подпапок записывать состояния поля.

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

Пока склоняюсь к мысли просчета начальной стадии - выставления фишек. Дальше придется все же писать обход.

@JuriiMW · 23.12.2019, 08:49

А в памяти разве так трудно дерево поиска развернуть?

@Ksardas_178 · 23.12.2019, 08:59 **[ТС]**

Сообщение от JuriiMW

А в памяти разве так трудно дерево поиска развернуть?

Тоже вариант, скорее я пока слабо представляю, сколько памяти на это уйдет. Еще в процессе осмысления. Опять же, если это предпросчет, записывать куда-то придется.

Если интересно, то на тему решений самой игры есть статья на английском:
http://library.msri.org/books/... gasser.pdf

@JuriiMW · 23.12.2019, 09:07

Ну, дык, нужно сначала делать в памяти, а только потом (если не будет вмещаться) можно свопить на диск.
Кстати, операция чтения/записи самая долгая по времени.

@Sun Serega · 23.12.2019, 09:31

Сообщение от Ksardas_178

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

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

Только file of T не используйте, он устарел. Вместо него надо использовать BlockFileOfT:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
uses BlockFileOfT;
 
type
  Состояние = record
    //ToDo всё что надо для описания состояния
  end;
 
begin
  var f := new BlockFileOf<Состояние>;
  f.Rewrite('состояния.bin');
  
  f.Size := int64(BigInteger.Pow(3, 24)); // размер можно задать сразу
  
  f.Pos := 123563243;
  f.Write(new Состояние);
  
  f.Pos := 83409203;
  var x := f.Read;
  
end.

Сообщение от JuriiMW

Ну, дык, нужно сначала делать в памяти, а только потом (если не будет вмещаться)

Если каждое состояние описывать 1 байтом (что в целом нереально, всегда будет больше) - 3^24 состояний это 282 ГБ.
Но и делать всё через диск - тоже плохо вообще, потому что работа с диском это таки медленно.

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

Благо, кишки BlockFileOfT уже это умеют. Всё что прочитано и записано - хранится в оперативке до вызова .Flush . Главное только .Flush вызывать не забывать по своему усмотрению, а то его будет вызывать тогда - когда система решит что вы достаточно прочитали/записали, что может сильно расходится с задачей.

Но, над скоростью и достаточным объёмом диска - стоит всё же подумать перед тем как писать код. Вот у вас есть хотя бы 282 свободных ГБ на диске? А если бы вы это решали создавать тучу папок - на одни только заголовке в файловой системе больше потратилось бы (если система вообще разрешит эти заголовки выделить).

@Ksardas_178 · 23.12.2019, 10:25 **[ТС]**

Сообщение от Sun Serega

Вот у вас есть хотя бы 282 свободных ГБ на диске?

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

@Sun Serega · 23.12.2019, 11:14

Сообщение от Ksardas_178

Откопал почти терабайт

Ну, это даже integer хранить не получится...

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

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

Если всегда возможны все 3 хода - памяти так понадобится только больше. Но если нет - можно сильно сэкономить.

@Ksardas_178 · 23.12.2019, 23:32 **[ТС]**

Сообщение от Sun Serega

А там как - получается после каждого хода (кроме конца игры) есть всегда по 3 варианта следующего хода, или бывает меньше?

Ой, там 2 этапа игры: поочередное выставление фишек (9 штук) на доску (24 ячейки), потом перемещение по линиям на ней в попытке собрать 3 в ряд и отнять фишку соперника. Оценка очень 'на глазок'.

Из интересного: нашел в интернете базу данных для игры с компьютером. 78 гб весит. И это если учесть, что неликвидные ходы для компьютера-оппонента оттуда, очевидно, вырезаны. Перспектива пока удручает.

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

Добавлено через 36 минут
Думаю отказаться от полного перебора и немного схалтурить:

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

2) Проверка явных угроз постройки мельниц белыми в один ход. Нашли такую - пытаемся устранить за один ход. Без других вариантов

3) А лучшее на конец: если через n ходов мы никого не съели или нас поели больше, чем мы их - рубим ветку

Должно сильно облегчить жизнь

@Ksardas_178 · 24.12.2019, 10:13 **[ТС]**

Сообщение от Sun Serega

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

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

Сообщение от Sun Serega

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

Тогда дерево индексов практически совпадет по размерам с самой базой знаний?

The hash function we decided to use maps the 7,673,759,269
states into a range of 9,074,932,579 indices.

Добавлено через 16 минут
Для нормальной доски как верхний предел существует около 3^24 (282 млрд) состояний (24 клетки, каждая может быть пуста или занята командой). Я, увы, не в состоянии справиться с составлением хорошей хеш-функции.

Из идей: разбить на 5 байт, где каждый байт кодирует 5 клеток доски, то есть мы получаем 5 байт на всю доску. Это пока минимум. Дальше можно уменьшать количество вариантов, но вроде не критично. Получим что-то около (5 байт * 9 млрд состояний) или 45 Гб, по скромным прикидкам. Паршивый результат, но на диске поместится. Неликвидные ходы можно будет и позже отсортировать.

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

@mr-Crocodile · 24.12.2019, 11:11

Ksardas_178, попросите администрацию, всё, начиная с поста #4 выделить в отдельную тему с названием
Игра Nine Men's Morris (Мельница)

Сообщение от Ksardas_178

Ой, там 2 этапа игры: поочередное выставление фишек (9 штук)

18 штук, как я понял - по 9 у каждого игрока.

Сообщение от Ksardas_178

потом перемещение по линиям на ней в попытке собрать 3 в ряд и отнять фишку соперника.

если верить википедии, то при выставлении фишек тоже можно собрать 3 в ряд и отнимать фишку соперника.

А где-нибудь в эту игру можно с компьютером поиграть?

@Ksardas_178 · 24.12.2019, 11:59 **[ТС]**

mr-Crocodile,

Сообщение от mr-Crocodile

если верить википедии, то при выставлении фишек тоже можно собрать 3 в ряд и отнимать фишку соперника.

Там уйма правил и несколько трактовок. Я ориентируюсь на эту статью: http://library.msri.org/books/... gasser.pdf

Сообщение от mr-Crocodile

А где-нибудь в эту игру можно с компьютером поиграть?

Есть версии для скачивания с готовыми базами знаний: http://compalg.inf.elte.hu/~ggevay/mills/

Онлайн-реализаций много есть, если поискать.

Сообщение от mr-Crocodile

попросите администрацию, всё, начиная с поста #4 выделить в отдельную тему с названием
Игра Nine Men's Morris (Мельница)

Кому писать и что делать? Я тут новенький

@mr-Crocodile · 24.12.2019, 13:46

Сообщение от Ksardas_178

Там уйма правил и несколько трактовок.

понятно.

Ksardas_178, а какая цель вообще? Сделать ИИ играющий в эту игру с человеком?
так для этого не нужно все возможные варианты хранить.
или что делаешь и для чего?

Сообщение от Ksardas_178

Кому писать и что делать? Я тут новенький

ничего не надо. Модераторы сами всё сделают.
я ZX Spectrum-128 написал в личку, попросил. Если он посчитает нужным - выделит сообщения в отдельную тему.

@Ksardas_178 · 24.12.2019, 13:53 **[ТС]**

mr-Crocodile,

Сообщение от mr-Crocodile

а какая цель вообще? Сделать ИИ играющий в эту игру с человеком?

В общем, да

Сообщение от mr-Crocodile

так для этого не нужно все возможные варианты хранить.

Все возможные для человека. Бота можно ограничить. Уровень сложности ему выставлять не планировалось

@mr-Crocodile · 24.12.2019, 14:04

Сообщение от Ksardas_178

Все возможные для человека.

не понял. Ты о чём?!

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

@Ksardas_178 · 24.12.2019, 14:18 **[ТС]**

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

@mr-Crocodile · 24.12.2019, 14:20

Сообщение от Ksardas_178

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

почитайте, как статьи ИИ играет в шахматы. Думаю, что многие вопросы отпадут.

@Ksardas_178 · 24.12.2019, 14:24 **[ТС]**

mr-Crocodile, неполный поиск в ширину? Можно, но далеко не так эффективно. Придется задуматься над оценкой позиции. Каковы будут критерии?

Опять же, если существуют реализации, основанные на предпросчете, наверное, они не так уж плохи?

@mr-Crocodile · 24.12.2019, 14:38

Ksardas_178, мы уже говорим про эффективность?
Тогда я снимаю своё предложение.
Безусловно, полная база знаний по всем возможным вариантам намного эффективнее, чем любая эвристика и оценочная функция. Я, конечно, сомневаюсь, что ты сам сможешь составить такую базу, но, если есть готовая и ты сможешь ей воспользоваться, то - ВПЕРЁД!

Сообщение от Ksardas_178

Придется задуматься над оценкой позиции. Каковы будут критерии?

ты это от меня хочешь услышать?

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

Сообщение от Ksardas_178

Опять же, если существуют реализации, основанные на предпросчете, наверное, они не так уж плохи?

они наверняка ОЧЕНЬ хороши.

Не по теме:

анекдот.
два свехмощных шахматных компьютера начали партию в шахматы.
первый сделал ход E2 - E4
второй задумался и через некоторое время, просчитав все варианты выдал:
- Сдаюсь.

@Ksardas_178 · 24.12.2019, 16:00 **[ТС]**

mr-Crocodile, не зря же говорят, что белые начинают и выигрывают) За идеи по оценке спасибо. Сам не игрок

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

@Sun Serega · 26.12.2019, 07:38

Сообщение от Ksardas_178

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

Нет, это так не работает.

Хеш функций режет информацию на кусочки и берёт только 1 из этих кусочков. Вся остальная информация теряется и восстановить её уже и теоретически невозможно. Хеш функция это не то же самое что архиватор.

.GetHashCode обычно используется в чтоб разложить информацию по полочкам. Пример из реальности: в библиотеке все книги отсортировали по алфавиту.
Имея букву, означающую раздел (то есть первую букву названия всех книг в нём) - нельзя получить всю книгу потому что 1. от всей книги - есть только 1 буква из названия и 2. таких книг может (и скорее всего будет) много.
Зато, если вы знаете что название нужной вам книги начинается с определённой буквы - вам надо искать не по всей библиотеке, а только в 1 разделе.

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

---
Про что говорил я:

Весь смысл типизированных файлов в том, что абсолютно все элементы имеют одинаковый размер. К примеру если размер элемента =L, а номер элемента, который вы ищите =N - можно точно сказать что нужный вам элемент находится в файле начиная с байта № N*L.

Что я имел в виду - использовать что то типа связного списка. Только обычно элемент связного списка хранит свои данные и адрес следующего элемента в оперативной памяти.

А в вашем случае - каждый элемент (то есть состояние) будет хранить свои данные + адрес следующих состояний в файле (то есть не адрес, а номер элемента, который выше я назвал N).

---

Сообщение от Ksardas_178

если через n ходов мы никого не съели или нас поели больше, чем мы их - рубим ветку

Но алгоритм объективной оценки такого - написать не проще чем алгоритм отличающий картинки кошек от собак. Лучше всё же проверять всё. Хотя бы чтоб были более общие статистические данные. А вообще - нереально знать, действительно ли ветка провальная, не просчитав её до конца.

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

Сообщение от Ksardas_178

Я, увы, не в состоянии справиться с составлением хорошей хеш-функции.

Для этого у вас есть доступ к интернету. А вообще в .Net уже есть встроенная хеш-функция - .GetHashCode. Для записей она особо хорошо работает.

Но как я и сказал - хеш таблицы тут вообще ни к месту.

Новые блоги и статьи Все статьи Все блоги /
Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .

@JuriiMW 5096 / 2662 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	23.12.2019, 08:49
	А в памяти разве так трудно дерево поиска развернуть? 0

@JuriiMW 5096 / 2662 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	23.12.2019, 09:07
	Ну, дык, нужно сначала делать в памяти, а только потом (если не будет вмещаться) можно свопить на диск. Кстати, операция чтения/записи самая долгая по времени. 0

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	24.12.2019, 14:18 [ТС]
	mr-Crocodile, я о том, что бот должен знать выход из позиции, которую создаёт человек. Соответственно для хода человека дерево развития игры имеет максимальное ветвление. Фактически после фильтрации полного дерева игры (буде кому-то придет в голову его записывать) мы выбираем единственно верный ход для ИИ и получаем базу знаний и алгоритм работы: человек сделал то-то - мы делаем конкретно вот это, а не выбираем из сотен вариантов, и наше решение при этом с наибольшей вероятностью ведёт к победе. 0

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	24.12.2019, 14:24 [ТС]
	mr-Crocodile, неполный поиск в ширину? Можно, но далеко не так эффективно. Придется задуматься над оценкой позиции. Каковы будут критерии? Опять же, если существуют реализации, основанные на предпросчете, наверное, они не так уж плохи? 0

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	24.12.2019, 16:00 [ТС]
	mr-Crocodile, не зря же говорят, что белые начинают и выигрывают) За идеи по оценке спасибо. Сам не игрок Добавлено через 7 минут К слову об очень хороших вариантах: вообще говоря, если игра не гарантирует победу даже при идеальной стратегии (наш случай), то оценка качества ходов в виде отношения получившихся путей к победе ко всем возможным путям из новой ветки тоже несколько хромает. Надо брать за основу что-то другое. Скажем, неочевидность выбора для оппонента. И если играть против человека, то выбирать те варианты, которые ему труднее будет просчитать и при этом одновременно легче выбрать ошибочное направление. Но это так, мысли вслух 0