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

[Vovka17]

Несколько определений:
Доска - стандартная доска для русских шашек 8х8. Игра ведется только на черных полях, итого у нас есть 32 игровых поля.
Фигура - простая шашка или дамка. Всего у каждого игрока возможно не более 12 фигур. В начальной позиции - 12 простых белых и 12 простых черных.
"Легальная" позиция - позиция в которой выполняются условия:
1) Количество фигур одного цвета не менее 1 (недопустимы позиции, состоящие только из одного цвета)
2) Количество фигур одного цвета не более 12 (как следствие из начального соотношения сил)
3) Недопустимо наличие на восьмой горизонтали белых простых шашек, и на первой горизонтали - черных простых шашек (так как это дамочные поля и простые шашки на них превращаются в дамки).
(некоторые из "легальных" позиций будет, тем не менее, невозможно получить в игре, но мы на это закрываем глаза)...
Итак, требуется:
1. Вычислить число n-фигурных легальных позиций (N) - это будет (условно) размер базы окончаний для n фигур.
2. Ввести однозначное взаимное соответствие между самой позицией и её номером (от 0 до N-1) в n-фигурной базе окончаний.
Переборные варианты решения надо отбросить сразу. Это слишком долго и неэффективно. Наоборот, необходимо научиться очень быстро находить номер позиции в базе. Первая часть задачи должна решаться в рамках комбинаторики и, в принципе, она мне по силам (надо только собраться с духом и написать формулу). Но это лишь число позиций. А вот как ввести соответствие позиции и её номера - это я совершенно без понятия... Прошу помощи.

[arseniiv]

(Плохой способ.)

Первое, что приходит на ум — двоичная система. Это не то. На смену ей идёт троичная. Опять не то — дамки. Ну, тогда пятеричная. На этом можно и остановиться, если есть возможность держать базу из $5^{32}$ записей. Если под состояние клетки доски всё-таки отдавать целый байт или полубайт, а не неудобные для обработки 3 бита, и хранить отдельно массив указателей на позиции (одни используются, другие — для неправильных позиций — просто стоят себе пустые) на $5^{32}\cdot4$ или $5^{32}\cdot8$ байт, и отдельно не более $5^{32}\cdot32$ (или $5^{32}\cdot16$ в случае полубайтов) под все позиции. Вычислите количество правильных позиций — если оно на много порядков меньше $5^{32}$, мой совет ужасен, но его можно было бы трансформировать во что-то получше.

-- Пн дек 23, 2013 03:05:29 --

Чёрт, в $n$-фигурной же, а не $1..n$-фигурной. Тогда это точно неудачный способ.

[Vovka17]

Может кому-то третье условие легальности проще будет понять из рисунка:

Это начальное расположение сил в русских шашках. Белые простые шашки дойдя до 8-ой горизонтали (чёрные - до 1-ой) превращаются в дамки и не могут там присутствовать в качестве простых.

-- 23.12.2013, 08:22 --

arseniiv, база из $5^{32}$ элементов описывает все возможные расположения фигур на 32 полях доски, без всяких условий. Это действительно первое, что приходит в голову. И очень легко из позиции получить её номер в такой базе, а по номеру - построить позицию...
К сожалению, база из $2,3 \cdot10^{22}$ элементов немыслима и недостижима.
К счастью, наша задача гораздо проще и реальнее.

Без учета условий легальности число n-фигурных позиций равно:

$$N(n)=C_{32}^n\cdot4^n\eqno (1)$$

n            N(n)
2            7936
3          317440
4         9205760
5       206209024
6      3711762432
7     55146184704
8    689327308800
9   7352824627200
10 67645986570240
...

С учетом легальности, число позиций будет ещё меньше.

[arseniiv]

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

[Vovka17]

Вот что получилось по первой части задачи:

$$N(n)=\sum\limits_{i=\max(1,n-12)}^{\min(12,n-1)}\left(\sum\limits_{Z(i,n)} C_4^{w_1}\cdot C_{4-w_1}^{b_1}\cdot C_4^{w_8}\cdot C_{4-w_8}^{b_8}\cdot C_{24}^{i-w_1-w_8}\cdot C_{24-i+w_1+w_8}^{n-i-b_1-b_8}\cdot 2^{n-b_1-w_8}\right) \quad(2)$$

где $Z(i,n)=$$\left\{w_1,b_1,w_8,b_8|w_1\geqslant{0};b_1\geqslant{0};w_8\geqslant{0};b_8\geqslant{0}; w_1+b_1\leqslant{4};w_8+b_8\leqslant{4};w_1+w_8\leqslant{i};b_1+b_8\leqslant{n-i} \right\}$
Здесь:
$i$ - количество белых ($(n-i)$ - количество черных);
$w_1$, $b_1$ - количество белых и черных на первой горизонтали доски;
$w_8$, $b_8$ - количество белых и черных на восьмой горизонтали доски.
Не слишком компактная формула , но она работает и выдаёт верные значения:

n            N(n)
2            3488
3          196032
4         6209316
5       139450808
6      2426085676
7     34243113624
8    403190250561
9   4033171712096
10 34712907199296
...

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

По второй части - как по позиции вычислять её номер - никаких идей. Знаю лишь, что это возможно.

[Null]

Попробуйте перебрать возможные варианты игры из начального положения на 8-10 ходов вперед. На этом этапе(если меня не глючит) много шашек обязательно будет съедено. Потом посмотрите сколько максимум шашек могло остаться. Тогда у вас значительно сократиться число вариантов.

[Vovka17]

Null, не до конца уловил вашу мысль.
Конечно, за 8-10 ходов много шашек может быть съедено, но это вовсе необязательно. Например, вот первое, что мне пришло сейчас в голову:
1.c3-b4 f6-g5 2.d2-c3 e7-f6 3.e3-d4 d6-e5 4.b4-c5 g5-f4 5.a3-b4 h6-g5 6.b2-a3 g7-h6 7.c1-b2 f8-g7 8.c5-d6 b6-a5 9.d6-e7 f4-e3 10.b4-c5 e3-d2 11.a3-b4 d2-c1 12.b2-a3 c7-b6 13.e7-f8 d8-c7 14.g3-h4 g5-f4 15.f2-g3 c1-d2 16.e1-f2 d2-e3 17.f8-d6 h6-g5 18.a1-b2 g7-h6 19.d6-f8 h8-g7 20.f8-d6 e3-c1 (см. рис.)...

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

Цель - не сократить число вариантов, наоборот, нам необходимы все(!) варианты расстановок заданного количества материала. То, что невозможно залить всю игру в базы - это ясно. Мы рассуждаем сейчас только об окончаниях. Например, для n<=6 размер баз вполне приемлемый. А на силу игры программы в окончании эта база уже окажет очень сильное положительное влияние.

[Vovka17]

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

[Null]

Я предлагаю разбить позиции на начальные(пустых мест меньше чем черных или белых) и конечные(все остальные).
Просто значительное количество расстановок в игре получить невозможно и размер базы сократится.

[Vovka17]

Да, я вас понял.
Но, во-первых, "дотянуться" из начальных позиций (дебюта), до конечных (эндшпиля) для компьютера не представляется возможным на современном этапе развития техники. Это было бы, по сути, полное решение шашек.
Во-вторых, я гарантирую, что почти все возможные позиции из эндшпиля $n\leqslant6...8$ возникают из начальной позиции. Исключения будут составлять ничтожную часть. И уж проще считать всё сейчас, чем потратить пол жизни на исключение этой части. Эти невозможные позиции не окажут никакого ощутимого влияния на размер базы.
(Вот если бы речь шла о дебюте и $n\geqslant20$, то я с вами согласился бы полностью. Там число позиций возникающих при игре значительно меньше общего числа позиций которые можно получить случайной расстановкой фигур).
Посмотрите на размеры баз у шахматистов по вышеприведенной ссылке. У нас базы для $n\leqslant6$ значительно меньше и позволяют легко с ними работать (см. результаты расчета по формуле (2)). Сейчас нужно только научиться по позиции вычислять её номер в $n-$фигурной базе вот и всё.

[Aritaborian]

Я ещё лет пять назад где-то читал, что шашки решены полностью.

[mustitz]

Aritaborian в сообщении #805408 писал(а):

Я ещё лет пять назад где-то читал, что шашки решены полностью.

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

-- 24.12.2013, 11:19 --

Eсли взять и почитать четвертый том TAoCP (что считаю обязательным перед решением таких задач), то в пункте 7.2.1.3 находим интересное свойство сочетаний:

Сочетание $c_1$, $c_2$, ..., $c_n$ посещается [в лексикографическом порядке] после посещения ровно

$$ { c_t \choose t } + \dots + { c_2 \choose 2 } + { c_1 \choose 1} $$

других сочетания.

Что прямо дает нам нумерацию на основе комбинаторной системы счисления. Например, у нас есть окончание 3 простые плюс дамка vs 2 простые плюс дамка. Смотрим,

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

$$ { 2 \choose 3 } + { 1 \choose 2 } + { 0 \choose 1} = 0 + 0 + 0 = 0 $$

для сочетания 860 получаем номер

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

Далее, две простые можно расположить $ 28 \choose 2 $ способами (часть из них может перекрываться шашками белых). Но если брать за основу перекрытия с белыми шашками, то $28 < 29 = 32 - 3$, поэтому такой вариант выгоднее. Далее, одна дамка это 27 способов, еще одна дамка 26 способов. Итого получаем для этой комбинации:

$ { 28 \choose 3 } \cdot { 28 \choose 2 } \cdot 27 \cdot 26 $

вариантов плюс нумерация этих вариантов. Опять же, все перестановки можно просчитать заранее и поместить в некоторый массив choose[32][32].

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

[Vovka17]

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

Aritaborian в сообщении #805408 писал(а):

Я ещё лет пять назад где-то читал, что шашки решены полностью.

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

Да, верно. Эта чекерсная программа - Chinook. И стала она такой непобедимой не без участия легендарного Мариона Тинсли. Критические замечания по поводу игры этой программы легко найти в интернете. От себя добавлю - да, Chinook никогда не проигрывает из начальной позиции, но при этом его игра далеко не самая сильная...

mustitz, спасибо за интересную информацию. Займусь-ка я, пожалуй, обязательным четвертым томом TAoCP, который, чувствую, мне поможет. А то пока я, к своему стыду , почти не могу "прочитать" ваш ответ ...

Может кто подскажет где его найти, этот четвертый том? Что-то ничего не вижу .

[Vovka17]

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

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

Да, хочется совсем экономить - если допускать наложение шашек это плохо и вызовет чувствительный рост базы (лень считать, но чем больше $n$, тем опаснее закрывать глаза на наложения шашек).
Думаю, что можно и после белых простых сразу учитывать сколько из них попадает на поля доступные для черных простых шашек. Сделать черные простые. А следом переходить уже к белым и черным дамкам...
Надо подумать, разобраться...

[Aritaborian]

Vovka17 в сообщении #805559 писал(а):

Может кто подскажет где его найти, этот четвертый том? Что-то ничего не вижу

Вот в оригинале, вот в переводе.