Предпросчет возможных ходов в игре 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. Для записей она особо хорошо работает.

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

@JuriiMW 5095 / 2661 / 2355 Регистрация: 10.12.2014 Сообщений: 10,059
	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