2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Программирование баз окончаний русских шашек
Сообщение22.12.2013, 23:44 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 00:04 
Заслуженный участник


27/04/09
28128

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

Первое, что приходит на ум — двоичная система. Это не то. На смену ей идёт троичная. Опять не то — дамки. Ну, тогда пятеричная. На этом можно и остановиться, если есть возможность держать базу из $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$-фигурной. Тогда это точно неудачный способ.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 08:44 
Аватара пользователя


10/11/12
121
Бобруйск
Может кому-то третье условие легальности проще будет понять из рисунка:
Изображение
Это начальное расположение сил в русских шашках. Белые простые шашки дойдя до 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
...

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 13:03 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 14:15 
Аватара пользователя


10/11/12
121
Бобруйск
Вот что получилось по первой части задачи:
$$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$ - количество белых и черных на восьмой горизонтали доски.
Не слишком компактная формула :wink: , но она работает и выдаёт верные значения:
Код:
n            N(n)
2            3488
3          196032
4         6209316
5       139450808
6      2426085676
7     34243113624
8    403190250561
9   4033171712096
10 34712907199296
...

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

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 15:09 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 21:24 
Аватара пользователя


10/11/12
121
Бобруйск
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 размер баз вполне приемлемый. А на силу игры программы в окончании эта база уже окажет очень сильное положительное влияние.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение23.12.2013, 23:44 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 08:48 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 10:11 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 10:31 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Я ещё лет пять назад где-то читал, что шашки решены полностью.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 11:40 


10/04/12
704
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].

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 18:06 
Аватара пользователя


10/11/12
121
Бобруйск
mustitz в сообщении #805415 писал(а):
Aritaborian в сообщении #805408 писал(а):
Я ещё лет пять назад где-то читал, что шашки решены полностью.

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

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

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

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 19:14 
Аватара пользователя


10/11/12
121
Бобруйск
mustitz в сообщении #805415 писал(а):
Если совсем хочется экономить, то нумерацию можно усложнить. Начинать с дамок и белых простых, а черные простые оставлять на закуску, высчитывая количество доступных белых полей в зависимости от расположения белых шашек.

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 20:04 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Vovka17 в сообщении #805559 писал(а):
Может кто подскажет где его найти, этот четвертый том? Что-то ничего не вижу
Вот в оригинале, вот в переводе.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 43 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group