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

[mustitz]

В нашем случае налагаются черные простые на белые простые. Дамки не налагаются.

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

В той нотации, что я привел, используется для сочетаний запись $ n \choose k$, другое обозначение $C_n^k$. Они вычисляются по формуле:

$$ { n \choose k } = C_n^k = { n! \over k! \cdot (n-k)! } $$

Если $k > n$, то число сочетаний полагается равных нулю.


Для примера, нам надо расставить и занумеровать расположение трех простых на шашечной доске. Пусть клетки имеют номера от 0 до 31, на дамочных полях простых быть не может. Итого нам надо рассмотреть все возможные способы выбрать три элемента из 28, или все сочетания из трех элементов из множества $\{0, 1, 2, \dots, 27 \}$. Итак, в лексикографическом порядке первое сочетание это $\{2, 1, 0 \}$, второе сочетание $\{3, 1, 0 \}$, третье $\{3, 2, 0 \}$, далее $\{3, 2, 1 \}$, потом $\{4, 1, 0 \}$, $\{4, 2, 0 \}$, $\{4, 2, 1 \}$, $\{4, 3, 0 \}$, $\{4, 3, 1 \}$, $\{4, 3, 2 \}$, $\{5, 1, 0 \}$ и т. д. Рассмотрим $\{4, 3, 0 \}$, оно восьмое в нашем списке, но индексы идут с нуля, поэтому нам надо получить $7$.

Наша формула

$$ { c_3 \choose 3 } + { c_2 \choose 2 } + { c_1 \choose 1} $$

или

$$ { 4 \choose 3 } + { 3 \choose 2 } + { 0 \choose 1} = { 4! \over 3! \cdot 1! } + { 3! \over 2! \cdot 1! } + 0 = 4 + 3 = 7$$

Идем дальше, для $\{4, 3, 1 \}$ получаем

$$ { 4 \choose 3 } + { 3 \choose 2 } + { 1 \choose 1} = { 4! \over 3! \cdot 1! } + { 3! \over 2! \cdot 1! } + 1 = 4 + 3 + 1 = 8$$

Для $\{4, 3, 2 \}$ получаем

$$ { 4 \choose 3 } + { 3 \choose 2 } + { 2 \choose 1} = { 4! \over 3! \cdot 1! } + { 3! \over 2! \cdot 1! } + { 2! \over 1! \cdot 1! } = 4 + 3 + 2 = 9$$

Для $\{5, 1, 0 \}$ получаем

$$ { 5 \choose 3 } + { 1 \choose 2 } + { 0 \choose 1} = { 5! \over 3! \cdot 2! } + 0 + 0 = { 5 \cdot 4 \over 1 \cdot 2} = 10$$

и т. п.

[Vovka17]

Aritaborian, mustitz, большое спасибо за помощь.

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

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

[Vovka17]

Вот обновленная формула для расчета числа позиций в $n$-фигурной базе:

$$N(n)=\sum\limits_{i=\max(1,n-12)}^{\min(12,n-1)}\left(\sum\limits_{Z(i,n)} { 4 \choose w_1 } \cdot { 24 \choose w-w_1 } \cdot { 28-w+w_1 \choose b } \cdot { 32-w-b \choose i-w } \cdot { 32-i-b \choose n-i-b }\right) \quad(3)$$

где $Z(i,n)=$$\left\{w,w_1,b| 0 \leqslant w \leqslant i; 0 \leqslant w_1 \leqslant \min(4,w); 0 \leqslant b \leqslant n-i \right\}$
Здесь:
$i$ - количество белых фигур;
$w$ - количество белых простых;
$w_1$ - количество белых простых на первой горизонтали;
$b$ - количество черных простых;

Пока не имею возможности проверить и убедиться, что значения этой формулы совпадают со значениями формулы (2), надеюсь, всё верно.

В формуле (3):
${ 4 \choose w_1 }$ - число расстановок $w_1$ белых простых на первой горизонтали;
${ 24 \choose w-w_1 }$ - число расстановок оставшихся белых простых на 2-7 горизонталях;
${ 28-w+w_1 \choose b }$ - число расстановок черных простых на незанятых белыми простыми полях 2-8 горизонталей;
${ 32-w-b \choose i-w }$ - число расстановок белых дамок на незанятых белыми и черными простыми полях;
${ 32-i-b \choose n-i-b }$ - число расстановок черных дамок на оставшихся полях доски.

[mustitz]

А зачем все эти формулы? Все равно база строится от младших окончаний к старшему. Плюс при построении очередного окончания используются только младшие окончания. Поэтому, начинаем строить от дамка vs дамка Dd. Простых нет, поэтому всего $32 \cdot 31$ вариантов. Таблицы lookup нет. Потом дамка против простой Ds. Всего $28 \cdot 31 \cdot 2$ вариантов. Таблицы lookup нет. Потом простая против простой Ss. Строим табличку длины 28. Для 0, 1, 2, 3 получаем 28 вариантов, поэтому

lookup[0]=0; lookup[1]=28; lookup[2]=56; lookup[3] = 84; lookup[4] = 110;.

Далее, для 4, 5, 6, 7, ... 27 получаем 27 вариантов:

lookup[5]=137; lookup[6]=164; ....

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

[Vovka17]

Проверил. Формула (3) верна!

mustitz, конечно, эта формула не будет постоянно использоваться при работе с базой. Пожалуй это больше нужно для предварительной оценки размера базы.
Ну ладно, пусть мы ничего не считаем. А просто строим базу и заносим в таблицу смещения (lookup - это же смещения, я верно понял?). Уже для двух фигур у вас в lookup-таблице 28 элементов ... Но как будет выглядеть эта таблица, когда доберемся до 6-фигурной базы? Она станет трехмерной? Какого она будет размера? Мне кажется, что она будет огромной, и представлять, по-сути, посчитанные значения для огромного количества вариантов. Хотя, может, я и ошибаюсь...

Формула (3) - она ведь оценивает размер всей $n-$фигурной базы, для всех возможных сочетаний материала. Если нам известно сколько каких фигур, то эта формула упрощается. Например, так:

$$N(ws_1, ws_{2...7}, bs, wd, bd) = $$

$$={ 4 \choose ws_1 } \cdot { 24 \choose ws_{2...7} } \cdot { 28-ws_{2...7} \choose bs } \cdot { 32-ws_1-ws_{2...7}-bs \choose wd } \cdot { 32-ws_1- ws_{2...7} - bs - wd \choose bd } \quad(4)\end$$

где
$ws_1$ - количество белых простых на первой горизонтали;
$ws_{2...7}$ - количество белых простых на 2-7 горизонталях;
$bs$ - количество черных простых;
$wd$ - количество белых дамок;
$bd$ - количество черных дамок;

Вот у меня пока и мысли о том, чтобы сгенерить кучу файлов вида ed_{$ws_1$}{$ws_{2...7}$}{$bs$}{$wd$}{$bd$}.
Например, файл ed_12121 - кусок из 7-ми фигурной базы окончаний - 3 простые (1 на первой горизонтали) плюс 2 дамки белых vs 1 простая плюс 1 дамка черных.
Размер этих кусочков будет определяться по формуле (4). Внутренняя адресация организуется по указанному mustitz принципу. При работе в память подгружаем только требуемые файлы базы.
Число таких файликов, для описания всех конфигураций $n-$ных баз будет равно:

n Files
2     6
3    21
4    50
5    99
6   173
7   277
8   416

Вполне приемлемо ведь (ожидал, гораздо больше).
Это решает все проблемы с расчетом индекса позиции в базе и в базе не держим никаких накладывающихся позиций, ничего лишнего!
Эх, если б не праздники, занялся бы кодингом сейчас вплотную.

[mustitz]

Да, lookup это смещение. Но считать смещения надо только для простых одного цвета. Например, для окончания ssssdSSSD (четыре простых и дамка против трех простых и дамка) надо таблицу lookup размера $C_{28}^3 = 3276$, что не так уж и много от общего числа вариантов.

Итак, у нас есть $C_{28}^3 =3276$ вариантов расположения черных шашек, есть от $C_{28}^4$ до $C_{25}^4$ вариантов расположения белых шашек, есть 25 вариантов расположения белой дамки и 24 варианта расположения черной дамки и 2 варианта очередности.

Интереснее вопрос эффективной генерации ходов :) Как собираешься хранить позицию?

Кстати, при $n=2$ у нас всего три таблицы (sS, sD, dD). Откуда шесть? Для $n=3$ у нас шесть таблиц (ssS, sdS, ddS, ssD, sdD, ddD). Для $n=4$ получаем 14 вариантов: шесть для соотношения 2+2 (ssSS, ssSD, ssDD, sdSD, sdDD, ddDD), восемь для соотношения 3+1 (sssS, ssdS, sddS, dddS, sssD, ssdD, sddD, dddD),

[Vovka17]

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

Интереснее вопрос эффективной генерации ходов :) Как собираешься хранить позицию?

Кстати, при $n=2$ у нас всего три таблицы (sS, sD, dD). Откуда шесть?

Генератор ходов у меня со старых студенческих времён валяется на fasme. Генерил порядка 10-20М ходов в секунду. Хотя, может, перепишу его на C++. Посмотрю ещё, как настроение будет.
Хранить позиции в базе? Зачем? Не будет никаких позиций. Для этого мы ведь и вычисляли индекс позиции и находили её адрес. Там будет храниться только оценка позиции и всё.
Можно делать безранговые эндшпильные базы - тогда храним только оценку - выигрыш, проигрыш, ничья (тогда достаточно 2 бит на позицию).
Я хочу сделать ранговую базу - хранить число ходов до выигрыша/проигрыша и отвести под каждую позицию 1 байт (подумаю ещё) в базе.

при $n=2$ у меня 6 файлов (ed_10100, ed_01100, ed_00110, ed_10001, ed_01001, ed_00011). Я ведь разделяю белые простые на первой горизонтали и белые простые на 2-7 горизонталях и считаю их отдельно. Мне при этом очень легко вычислять индекс в базе (см. моё предыдущее сообщение)

(Оффтоп)

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

[Toucan]

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

Как собираешься хранить позицию?

mustitz, замечание (повторное) за фамильярность. Читайте Правила форума:

Forum Administration в Правилах форума #27356 писал(а):

1) Нарушением считается:
…
е) ..., фамильярность (у нас принято обращаться друг к другу на "Вы")...

[Vovka17]

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

... и 2 варианта очередности.

Это точно лишнее. В базе надо хранить только оценки позиции при ходе белых.
Для нахождения оценки при ходе черных трансформируем позицию переворачивая доску и заменяя цвета фигур на противоположный и находим в базе оценку этой трансформированной позиции.

[mustitz]

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

Хранить позиции в базе? Зачем? Не будет никаких позиций. Для этого мы ведь и вычисляли индекс позиции и находили её адрес. Там будет храниться только оценка позиции и всё.

Не, представление позиции для генерации. Понятно, если хранить позицию в виде 64-битных масок (белые простые, черные простые, белые дамки, черные дамки + некоторые кэши типа всех шашек), то можно используя bitboard быстро генерировать ходы. Заманчиво выглядит хранение позиции в виде 32-битных битовых масок (белые простые, черные простые, белые дамки, черные дамки). Но тогда надо подумать о выборе магических констант для дамок, и как организовать ходы простых...

Например, для случая 64-битных масок ходы простой будут генериться следующим кодом:

Используется синтаксис C++

#define CAN_MOVE_RIGHT 0x55A255A255A25500ull
#define RANK_8 0x00000000000000FFull

struct position_t
{
    uint64_t ws, wd, bs, bd, all;
    int active;
};

void while_simple_move(position_t pos)
{
    /* Simple moves */
    uint64_t next = ((pos.ws & CAN_MOVE_RIGHT) << 9) & ~pos.all;
    while (next) {
        uint64_t tmp = next & (-next);
        next &= next - 1;
        
        struct position_t new_pos = pos;
        new_pos.ws ^= tmp >> 9;
        new_pos.all ^= tmp >> 9;

        uint64_t * destination = tmp & RANK_8 ? &new_pos.wd : &new_pos.ws;
        *destination ^= tmp;
        new_pos.all ^= tmp;

        new_pos.active = ~pos.active;
        push_answers(new_pos);
    }
}
 

-- 26.12.2013, 17:25 --

Идея lookup в том, чтобы иметь один файл для каждого типа позиций. А не несколько одновременно загруженных. Например, если у нас окончание четыре простых против четырех простых, то нам надо будет четыре разных файла для хранения. А если файл предварить таблицей lookup, то мы получим один файл.

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

[Vovka17]

Вот я тут на коленках сделал пример нахождения позиции в базе:
Пусть у нас следующее расположение сил:

(ход черных)

1. Так как у нас ход черных, то трансформируем позицию переворачивая доску и заменяя цвета фигур на противоположный:


2. Определим имя файла базы:
$ws_1=2$, $ws_{2...7}=1$, $bs=2$, $wd=1$, $bd=2$.
Имя файла - ed_21212 - восьмифигурная база окончаний.

3. Из формулы (4) найдём следующие коэффициенты (это можно сделать заблаговременно):

$$k_4={ 32-ws_1- ws_{2...7} - bs - wd \choose bd }={ 32-2- 1 - 2 - 1 \choose 2 }={ 26 \choose 2 }=325$$

$$k_3={ 32-ws_1-ws_{2...7}-bs \choose wd } \cdot k_4={ 32-2-1-2 \choose 1 } \cdot 325={ 27 \choose 1 } \cdot 325=27 \cdot 325 = 8775$$

$$k_2={ 28-ws_{2...7} \choose bs } \cdot k_3={ 28-1 \choose 2 } \cdot 8775={ 27 \choose 2 } \cdot 8775 =351 \cdot 8775= 3080025$$

$$k_1={ 24 \choose ws_{2...7} } \cdot k_2={ 24 \choose 1 } \cdot 3080025=24 \cdot 3080025= 73920600$$

$k_0={ 4 \choose ws_1 } \cdot k_1={ 4 \choose 2 } \cdot 73920600=6 \cdot 73920600= 443523600$ - этот коэффициент считать не нужно, он определяет число позиций в файле ed_21212.

4. На пустой доске "расставляем" белые простые:

И вычисляем номера сочетаний для $ws_1=${3,0}, $ws_{2...7}=${9}:

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

$$B={ 9 \choose 1 } = 9$$

5. "Добавляем" черные простые:

И вычисляем номер сочетания для $bs=${24,7}:

$$C={ 24 \choose 2 }+{ 7 \choose 1 } = 276 + 7 = 283$$

6. "Добавляем" белые дамки:

И вычисляем номер сочетания для $wd=${26}:

$$D={ 26 \choose 1 } = 26$$

7. "Добавляем" черные дамки:

И вычисляем номер сочетания для $bd=${25,22}:

$$E={ 25 \choose 2 }+{ 22 \choose 1 }= 300 + 22 = 322$$

8. Всё готово для определения индекса:

$$I=A \cdot k_1 + B \cdot k_2 + C \cdot k_3 + D \cdot k_4 + E = 3 \cdot 73920600 + 9 \cdot 3080025 + 283 \cdot 8775 + 26 \cdot 325 + 322 = 251974122$$

Я подробненько всё расписал, но видно, что расчет очень несложный и быстрый. $A$, $B$, $C$, $D$, $E$ находятся элементарно сложением. Коэффициенты $k_1$, $k_2$, $k_3$, $k_4$ - умножением, а можно и заранее посчитать для каждого файла базы. Остаётся только всё подставить и найти $I$, как показано в 8-м пункте. (Все перестановки, естественно, посчитаны заранее и хранятся в двумерном массиве)

[mustitz]

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

[Vovka17]

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

Понятно, если хранить позицию в виде 64-битных масок (белые простые, черные простые, белые дамки, черные дамки + некоторые кэши типа всех шашек), то можно используя bitboard быстро генерировать ходы. Заманчиво выглядит хранение позиции в виде 32-битных битовых масок (белые простые, черные простые, белые дамки, черные дамки). Но тогда надо подумать о выборе магических констант для дамок, и как организовать ходы простых...

Я храню позицию в трёх 32-битных регистрах:
; ebx - black bitmap 0-nothing, 1-any black | and = dead (it must be marked like w&b)
; ecx - white bitmap 0-nothing, 1-any white | or = anybody bitmap 0-nothing, 1-anybody
; edx - damas bitmap 0-nothing, 1-any damas

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

Идея lookup в том, чтобы иметь один файл для каждого типа позиций. А не несколько одновременно загруженных. Например, если у нас окончание четыре простых против четырех простых, то нам надо будет четыре разных файла для хранения. А если файл предварить таблицей lookup, то мы получим один файл.

Понятно. Если объединить мои файлы для одинакового соотношения материала в один и предварить это таблицей, то получаем примерно то же самое. Можно, вообще, все файлы $n-$фигурной базы объединять в один общий файл. В этих подходах нет принципиальной разницы. (Если честно, я больших файлов баз боюсь - не знаю как я с ними уживусь . Никогда не работал с большими файлами, и есть некоторые серьёзные вопросы по скорости доступа к данным).

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

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

Если скачивать что-то конкретное, то да - не удобно. Хотя никто не запрещает делать архив из нескольких файлов и называть его, например, "1простая1дамкаVS2простые1дамка" . Но я всегда считал, что для анализа нужны все файлы из базы - вся база целиком...
Если скачать, как вы говорите, базу четыре простых на четыре простых, то вы сможете анализировать только это окончание. Зачем это? В чём его такая ценность?
Использование баз позволяет решать гораздо более интересные задачи. Например, у нас позиция 5простых vs 5простых. Как её оценить, если у нас есть только базы для 8-ми фигурных окончаний. Легко! Строим дерево ходов, пока не "дотянемся" из этого 10-ти фигурного окончания до нашей 8-ми фигурной базы. Оцениваем ветви и возвращаем оценку для исходной позиции, которой не было в базах! То, на какое соотношение сил в 8-ми фигурной базе мы выйдем - неизвестно. Поэтому нам нужно всё (ну или почти всё ).

[Vovka17]

Кстати тут, возникает попутная проблема, которую уже можно озвучить.
Как организовать максимально быстрый доступ к оценкам позиций в базе при размере базы в несколько гигабайт (несколько десятков гигабайт)? Каким образом, например, организован доступ к данным в 6-ти фигурной шахматной эндшпильной таблице Налимова, размер которой 1,2ТБ!? Кто-нибудь в курсе темы.

[Vovka17]

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