Программирование баз окончаний русских шашек

[mustitz]

Не все же окончания нужно смотреть за один раз? Вообще, в основном цикле надо работать только с данными для окончаний одного типа. И только на первом проходе смотреть младшие эндшпиля. Например, при первом проходе вы генерируете все хода, и ставите оценку в тех случаях, когда есть переход в младший выигрывающий эндшпиль или уничтожаются все шашки противника или запирание. Потом у вас уже будет проставлены ходы до выигрыша в случае, если ход приводит к моментальному выигрышу ($n=1$), или позиции, для которых есть переход в младшее окончание (тут мы знаем, что позиция выигрывается не более чем за $N_0$ ходов, но в реале оптимальное $N^{*}$ может быть меньше..

Дальше мы в младшие окончания не заглядываем. Берем $n=2$ (до выигрыша два полухода), и смотрим, можем ли мы улучшить проставленные ранее результаты, где $N>2$, а также прописываем оценку для окончаний, у которых нет оценки.

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

Кстати, для задачи идеально подходит OpenCL.

[Vovka17]

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

[mustitz]

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

[Vovka17]

mustitz в сообщении #806825 писал(а):

Число обращений к таблице Налимова растет не очень быстро.

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

[mustitz]

Как минимум для начала это нормальный вариант.

[Vovka17]

mustitz в сообщении #805415 писал(а):

Три простые можно расположить $ 28 \choose 3 $ различными способами (комбинаторная система для перечисления).
для сочетания 860 получаем номер

$$ { 8 \choose 3 } + { 6 \choose 2 } + { 0 \choose 1} = 56 + 15 + 0 = 71 $$

Это было очень полезное для нашей задачи свойство. И оно очень помогло.
Интересно, а как, зная, что у нас 3 шашки на 28 полях расположены по номеру 71, получить сочетание 860. То есть провести обратную операцию. Простой формулы я что-то не встретил, хотя понимаю, что есть однозначное соответствие.

(Оффтоп)

mustitz, просто интересно, вы занимались программированием шашек? Много нового узнал от вас.

[Vovka17]

Хмм...
У нас ведь есть замечательный массив choose[][].
Есть идея!
Проще показать на примере:

Пусть у нас 3 шашки на 28 полях, сочетание {860}, номер 71. Определим сочетание по его номеру:

$${27 \choose 3}=2925>71 \rightarrow {26 \choose 3}=2600>71 \rightarrow \cdots \rightarrow {9 \choose 3}=84>71 \rightarrow {8 \choose 3}=56 \leqslant 71 \Rightarrow c_3=8$$

$$71-56=15 \qquad {7 \choose 2}=21>15 \rightarrow {6 \choose 4}=15 \leqslant 15 \Rightarrow c_2=6$$

$$15-15=0 \Rightarrow c_1=0$$

{c3,c2,c1}={860}.
Готово!

Несложно написать программу действующую по такому алгоритму.
Стоит добавить, что здесь использован линейный поиск по строке массива. Это очень просто. И для наших целей это годится. При проверке максимум 32 ячеек массива мы построим любое возможное сочетание для любого доступного числа шашек, по его номеру.
Если бы у нас было больше полей, например в программировании "космических" шашек с доской 100х100 , то правильнее было бы применить двоичный поиск. Но это уже совсем другая история...

[mustitz]

Vovka17,
Немного вспомнил эту тему. У меня генерация всех 6-фигурных окончаний в русских шашках в DTC метрике заняло 2 часа, 16G оперативной памяти и 2.7G места на жёстком диске. Сильно дотошно не проверял, треугольник Петрова построила и ладно.
Пощупать можно на github.com/mustitz/checkers
Уже сгенерированные бинарники лежат в ветке github.com/mustitz/checkers/tree/etb-bin
Разрабатывал под Linux, проверял там же. В принципе, там ничего военного не используется, поэтому если есть C99 компилятор, то не думаю что будет сложно пересобрать.

[mustitz]

Немного продолжая шашечную тему, можно потестировать алгоритм MCTS для русский шашек (alpha).
Шашки http://35.204.55.174/
Надо нажать “New Game White” или “New Game Black” и играть

Сервер слабый (Google Cloud, 1 CPU), так что если тормозит лучше играть медленнее :)
Уровень игры не очень, надо усиливать. Писал для себя, не тестировал сильно. Работает под Chrome для Linux, под Edge 100% не должен работать. Под Android тоже не работает.

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

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

[kotenok gav]

mustitz в сообщении #1329627 писал(а):

под Edge 100% не должен работать

Работает.

[mustitz]

Обещанные исходники https://gitlab.com/mustitz/rus-checkers (или https://github.com/mustitz/checkers).

Значит Microsoft делают свой браузер более совместимым :) Просто раньше у меня не работал в IE, а сейчас и протестировать негде :)

[gevaraweb]

А почему нельзя сделать "в лоб": создать в таблице поля:

a1 a3 a5 a7 b2 b4 b6 b8 c1 c3 ...

перечисляемого типа со значениями: П (пусто), б, Б, ч, Ч (большая буква значит дамка соотв. цвета).
Или это превратить в одно ключевое поле a1П-a3б-a5П-a7ч-b2П-b4б-b6П-b8Б-c1Ч-c3ч... . Но обычно не есть гуд так.

Плюс дополнительные поля:

- Легальная позиция да/нет
- кто победил ч/б/ничья
- прочее...

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

[mustitz]

gevaraweb в сообщении #1329741 писал(а):

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

Поиск, конечно, быстрый, но это $O(\ln N)$. Поиск по индексу это $O(1)$.

Моя программа строит шестифигурные таблицы примерно за несколько часов, а это $2.6 \cdot 10^9$ различных позиций, и если каждую из них хранить строкой из $10$ байт, что мы уже получаем 26G без учёта индексов для быстрого доступа и служебной информации. А построение такой таблицы это не только $2.6 \cdot 10^9$ транзакций по вставке, но и большое количество чтений (например, 30 проходов). Не говоря о том, что при построении желательно хранить для каждой позиции список возможных ходов (при построении шестифигурных таблиц расход памяти был в районе 20G, при расчёте семифигурных в районе 400G RAM).

Если брать восьмифигурные, то четыре на четыре простые это примерно $400 \cdot 10^6$ позиций, дамки это $18 \cdot 10^9$ позиций.

Так что СУБД врял ли могут помочь тут хоть как-то из-за больших объёмов и низкой скорости.