Предпросчет возможных ходов в игре 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.

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

@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 346 / 276 / 134 Регистрация: 25.07.2014 Сообщений: 4,537 Записей в блоге: 22
	29.12.2019, 19:55
	Ksardas_178, должна. Сбоку слева появляется кнопка для сворачивания и разворачивания региона. 0

@Sun Serega 2357 / 1460 / 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