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

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

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

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

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

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

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

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

@Ksardas_178 · 26.12.2019, 10:42 **[ТС]**

Sun Serega,

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

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

Да, функцию хеширования корректнее назвать функцией состояния. Тогда при хорошей функции состояния можно индекс использовать как код текущего состояния, а элемент в нем - как код следующего. Все упирается только в функцию состояния. Пока выходит 2^34 (282 млрд) состояний по 5 байт в каждом, иначе 282*5 Гб, что многовато. Надо оптимизировать функцию состояния, да еще не забывать, что для "сырой" базы знаний придется хранить вероятность успеха того или иного хода, а это дополнительные траты памяти

Добавлено через 2 минуты

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

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

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

Добавлено через 4 минуты
И как можно красиво хранить значение из 5 байт информации? Ссылочные типы здесь не проходят.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
uses BlockFileOfT;
 
type
  w = record
    s:array [0..4] of byte;
  end;
 
begin
  var f := new BlockFileOf<w>;
  f.Rewrite('состояния.bin');
  
  f.Size := 54; 
end.

@Sun Serega · 27.12.2019, 01:04

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

array [0..4] of byte;

Не используйте статичные массивы в PABC.Net, никогда! Она реализованы как костыль, хранящий внутри динамический массив.

И, что важнее, из за того что статичный массив это класс - BlockFileOf<T> сохранит в файл ссылку на этот массив, вместо содержимого (это из за алгоритма сохранения в файл, без него - будет так же медленно как и у file of T).

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

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
uses System;
uses System.Runtime.InteropServices;
 
uses BlockFileOfT;
 
type
  [StructLayout(LayoutKind.Sequential)] // чтоб процессор, ес чо, не мог вставить отступы для своего удобства. Иначе магия с указателями не будет работать
  Arr5Byte = record
    b0,b1,b2,b3,b4: byte;
    
    /// читает или задаёт число int64, первые 5 байт которых соответствуют содержимому этой записи
    property AsNum: int64
    read PLongword(pointer(@b0))^ + int64(b4) shl 32
    write
    begin
      PLongword(pointer(@b0))^ := value;
      b4 := value shr 32;
    end;
    
  end;
  
  w = record
    data: Arr5Byte;
    next: int64; // Arr5Byte как отдельная запись, чтоб StructLayout влиял только на те 5 байт, а тут описываем отдельные поля
  end;
 
begin
  var f := new BlockFileOf<w>;
end.

=======================
Подробнее про отступы и [StructLayout(LayoutKind.Sequential)]:

Процессору удобно читать память из оперативки - "словами". Для 32-битного процессора - слово это 32 бита, а для 64-битного - 64 бита. При чём, читать им удобно не из любой рандомной точки.

Вся оперативная память разбита на эти слова, если читать int64 из pointer(80) - читает байты #80-#87 (всего 8 байт) как 1 слово. Но если читать из pointer(81) - процессору приходится читать байты #80-#87 и ещё #88-#85, потому что мимо слов нельзя. Ну и потом побитовыми сдвигами и т.п. резать эти слова чтоб получить отдельно те 8 байт из 16 прочитанных.
(это всё пример, офигеть какой упрощённый. К примеру байты в районе pointer(80) вообще зарезервированы системой)

Если читать число, размером меньше слова - читает всё равно 1 слово и потом режет, но это не проблема. Но если в записи находится 1 поле типа byte, а затем 1 поле типа int64 - получается int64 будет хранится мимо слова. Вот чтоб такого не было - обычно JIT компилятор смотрит на битность процессора на котором запустили .exe и вставляет нужный отступ между byte и int64. То есть 3 или 7 байт, которые вообще ничем никогда не заполняются и служат только чтоб процессору было удобнее читать.

Но, кстати, в типизированный файл - эти пустые байты отступа тоже запишет, потому что BlockFileOf<T> копирует память целиком, 1 блоком, как она хранилась в оперативной памяти (отсюда название).
Вообще, раз объём памяти в этом случае проблема - тот атрибут, убирающий отступы можно вставить во все записи. Но это, разумеется, ударит по производительности работы с этими данными.

@Соколиный глаз · 27.12.2019, 13:26

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

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

Насколько мне известно, разработчики этого не говорили публично. Максимум - тут было сказано:

Добавлен экспериментальный модуль для быстрой работы с типизированными файлами BlockFileOfT (разработчик Латченко Сергей aka @Sun_Serega)

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

@Ksardas_178 · 29.12.2019, 17:18 **[ТС]**

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

По управлению, буде кто заинтересуется:

Ход вводится в формате <откуда двигаем фишку?> <куда двигаем?> <кого в процессе едим?>
Так, ввод "2 3 6" - ход из 2 в 3, съедается ячейка 6.
Значения по умолчанию: -1 ("-1 2 -1" - ставим фишку на 2)
Система управления позволяет жульничать, но всю ответственность за корректную работу в данной версии вы берете на себя.

Замечания по коду (преимущественно тому, что сейчас задействован в работе) приветствуются. Во многом за этим и скидываю сюда:

https://cloud.mail.ru/public/4ny2/4MbijA9MQ

@Sun Serega · 29.12.2019, 17:36

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

Добавлено через 13 минут
По коду - из того что сразу видно:

1. Я уже говорил, статичные массивы реализованы как костыль, использующий динамичные.
К примеру в GameFieldInfo.pas на строчке 8:

Pascal
1
    private elements: array [1..2] of byte;//Число фишек у команд

Лучше заменить на:

Pascal
1
    private elements := new byte[2];//Число фишек у команд

При этом индексы будут 0 и 1. Для начала то что придётся менять индексы может показаться проблемой но:
1) при первой же попытке запуска - вы увидите где индекс был 2.
2) можно делать как то так:

Pascal
1
2
3
4
    public procedure remove(team_red: boolean); // true если красная команда, иначе false
    begin
      elements[integer(team_red)] -= 1;
    end;

integer(team_red), то есть преобразование из boolean в integer - ничем не отличается от преобразования byte в integer, которое у вас было раньше.
То есть внутреннее представление не меняется (true и byte(1) выглядят одинаково в памяти, и так же false и byte(0) ).
Но размер значения увеличивается (и у byte и у boolean - размер 1 байт, а у integer - 4).

Если принимать параметр как boolean - передать неправильное значение будет вообще невозможно.

2. Экономить память на стеке нет смысла, потому что размер стека задаётся при старте программы (или потока, если вы создаёте свои). Поэтому нет разницы, принимаете вы byte или integer параметром. Зато арифметика над числами меньше integer будет медленнее, потому что для операций вроде +-*/ и т.п. - числа меньше integer переводит в integer (или longword), а после операции - переводит назад.

Содержимое массивов, других классов и статичных полей - хранится в куче. Но и ту память экономить - не к чему. При том что даже у самых убогих компов есть хотя бы 1 гигабайт оперативки - то что тип элементов elements из п.1. это byte - будет вообще незаметно. Зато операции -= и += на них будут медленнее.

@Ksardas_178 · 29.12.2019, 17:42 **[ТС]**

Sun Serega, какой-то путь вышел длинный, но попробую разобраться. Первый раз через консоль. Idea отучила совсем.

https://github.com/Ksardas178/... 1%86%D0%B0

@Соколиный глаз · 29.12.2019, 17:49

Ksardas_178, Вы можете использовать директивы

Pascal
1
2
3
{$region Comment here}
// code here
{$endregion}

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

@Sun Serega · 29.12.2019, 18:58

Сообщение от Соколиный глаз

{$endregion}

А я предпочитаю ставить имя региона и в $endregion, то есть так:

Pascal
1
2
3
{$region Comment here}
// code here
{$endregion Comment here}

Если регион большой - особо удобно получается.

Добавлено через 31 минуту
В остальном просмотрел - код в целом неплохой. И явно лучше чем я ожидал, всё красиво разложено по полочкам и модулям. Некоторые вещи применены не к месту, но чтоб это понять - нужен только опыт (и желание разобраться как правильно использовать на себя принципы ООП).

Из мелочей:

1. В некоторых местах (как GameBorders.pas) у вас модификаторы доступа только у половины имён. Не хорошо так.

2. GameMill.pas - если уже используете список, задавайте ему в конструкторе размер 3. А вообще раз размер не меняется - лучше использовать массив.

3. В основном файле у вас есть:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
  {field_1.makeTurn(new Turn(-1,1,-1),1);
  field_1.makeTurn(new Turn(-1,2,-1),1);
  field_1.makeTurn(new Turn(-1,4,-1),1);
  field_1.makeTurn(new Turn(-1,6,-1),1);  
  field_1.makeTurn(new Turn(-1,7,-1),1); 
  field_1.makeTurn(new Turn(-1,8,-1),1);
  field_1.makeTurn(new Turn(-1,3,-1),2);
  field_1.makeTurn(new Turn(-1,5,-1),2);
  field_1.makeTurn(new Turn(-1,15,-1),2);
  
  t:=field_1.findTurn(0);
  field_1.makeTurn(t);}

Чтоб комментировать область - лучше выделять несколько строк и нажимать Ctrl+/

Ну а ещё, из древних потерянных техник комментирования:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
begin
  
  {
  
  код1
  
  {}
  
  код2
  
  {}
  
end.

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

А если сделать так:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
begin
  
  (*)
  
  код1
  
  (*)
  
  код2
  
  (*)
  
  код3
  
  (**)
  
end.

То добавление звёздочки в первый (*) - раскомментирует области 1 и 3 и одновременно закомментирует область 2.

@Ksardas_178 · 29.12.2019, 19:24 **[ТС]**

Не совсем понял, как пользоваться регионами. После добавления

Pascal
1
2
3
{$region Comment here}
// code here
{$endregion Comment here}

не должна появиться опция свертки кода? Есть функция "свернуть все регионы", доступная по щелчку ПКМ, но и она не работает

@Соколиный глаз · 29.12.2019, 19:55

Ksardas_178, должна. Сбоку слева появляется кнопка для сворачивания и разворачивания региона.

@Ksardas_178 · 29.12.2019, 20:31 **[ТС]**

Сообщение от Соколиный глаз

Сбоку слева появляется кнопка для сворачивания и разворачивания региона.

Нашел. Стоит отдельным пунктом в настройках редактора. Без этой галочки не работает

@Sun Serega · 30.12.2019, 13:40

power(256, bytes - 1).Round

Используйте shl. Через real жесть как медленно.

@Ksardas_178 · 30.12.2019, 14:17 **[ТС]**

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

Используйте shl. Через real жесть как медленно.

Возведение в степень заменить на цикл сдвигов?

Добавлено через 10 минут
Все, разобрался, цикл не нужен

@Sun Serega · 30.12.2019, 15:32

Да, цикл не нужен потому что 1 shl N это то же самое что Power(2, N), только для integer.
Ну а 256 это уже 2**8, то есть 256**(bytes-1) = (2**8)**(bytes-1) = 2 ** (8*(bytes-1)) = 1 shl (8*bytes-8).

Добавлено через 24 минуты
Но вообще стоит ещё упомянуть что у integer всего 32 бита, а значит формула 1 shl (8*bytes-8) будет работать только для bytes=1..4
Если надо больше (1..8) - пишите int64(1) shl (8*bytes-8). Ну и ответ будет в виде int64.

Новые блоги и статьи Все статьи Все блоги /
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	29.12.2019, 17:18 [ТС]
	Есть пока сырющая версия с неполным обходом дерева решений (минимакс). Интерфейс, возможно, буду дорабатывать, также в коде много "строительных лесов" и заготовок для создания базы знаний. По управлению, буде кто заинтересуется: Ход вводится в формате <откуда двигаем фишку?> <куда двигаем?> <кого в процессе едим?> Так, ввод "2 3 6" - ход из 2 в 3, съедается ячейка 6. Значения по умолчанию: -1 ("-1 2 -1" - ставим фишку на 2) Система управления позволяет жульничать, но всю ответственность за корректную работу в данной версии вы берете на себя. Замечания по коду (преимущественно тому, что сейчас задействован в работе) приветствуются. Во многом за этим и скидываю сюда: https://cloud.mail.ru/public/4ny2/4MbijA9MQ 0

@Ksardas_178 58 / 42 / 21 Регистрация: 01.01.2018 Сообщений: 273
	29.12.2019, 17:42 [ТС]
	Sun Serega, какой-то путь вышел длинный, но попробую разобраться. Первый раз через консоль. Idea отучила совсем. https://github.com/Ksardas178/... 1%86%D0%B0 0

@Соколиный глаз Alvin Seville 343 / 273 / 134 Регистрация: 25.07.2014 Сообщений: 4,537 Записей в блоге: 22
	29.12.2019, 19:55
	Ksardas_178, должна. Сбоку слева появляется кнопка для сворачивания и разворачивания региона. 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	30.12.2019, 15:32
	Да, цикл не нужен потому что 1 shl N это то же самое что Power(2, N), только для integer. Ну а 256 это уже 28, то есть 256(bytes-1) = (28)(bytes-1) = 2 ** (8(bytes-1)) = 1 shl (8bytes-8). Добавлено через 24 минуты Но вообще стоит ещё упомянуть что у integer всего 32 бита, а значит формула `1 shl (8bytes-8)` будет работать только для bytes=1..4 Если надо больше (1..8) - пишите `int64(1) shl (8bytes-8)`. Ну и ответ будет в виде int64. 0