2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Программирование баз окончаний русских шашек
Сообщение24.12.2013, 21:45 


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

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

В той нотации, что я привел, используется для сочетаний запись $ 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$$

и т. п.

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


10/11/12
121
Бобруйск
Aritaborian, mustitz, большое спасибо за помощь.

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

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

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


10/11/12
121
Бобруйск
Вот обновленная формула для расчета числа позиций в $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 }$ - число расстановок черных дамок на оставшихся полях доски.

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


10/04/12
704
А зачем все эти формулы? Все равно база строится от младших окончаний к старшему. Плюс при построении очередного окончания используются только младшие окончания. Поэтому, начинаем строить от дамка 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; ....

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

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


10/11/12
121
Бобруйск
Проверил. Формула (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

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

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


10/04/12
704
Да, 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),

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


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

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


19/03/10
8952
mustitz в сообщении #806369 писал(а):
Как собираешься хранить позицию?
 !  mustitz, замечание (повторное) за фамильярность. Читайте Правила форума:
Forum Administration в Правилах форума #27356 писал(а):
1) Нарушением считается:

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

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


10/11/12
121
Бобруйск
mustitz в сообщении #806369 писал(а):
... и 2 варианта очередности.

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

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


10/04/12
704
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, то мы получим один файл.

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

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


10/11/12
121
Бобруйск
Вот я тут на коленках сделал пример нахождения позиции в базе:
Пусть у нас следующее расположение сил:
Изображение
(ход черных)

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-м пункте. (Все перестановки, естественно, посчитаны заранее и хранятся в двумерном массиве)

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


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

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


10/11/12
121
Бобруйск
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-$фигурной базы объединять в один общий файл. В этих подходах нет принципиальной разницы. (Если честно, я больших файлов баз боюсь - не знаю как я с ними уживусь :D . Никогда не работал с большими файлами, и есть некоторые серьёзные вопросы по скорости доступа к данным).
mustitz в сообщении #806772 писал(а):
Расчет несложный, минус в том,что имена файлов не очень понятные для рядового пользователя. Допустим, я играю партию по переписке и мне для анализа нужна база четыре простых на четыре простых. Непонятно, что скачивать в этом случае. Ну и неприятно выбирать имена файлов. В этом смысле таблицы Налимова устроены куда проще: выбрал нужные файлы и загрузил. Так что я все-таки хранил бы полностью один тип окончаний в одном файле. Тем более, что это не сложно реализовать :)

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

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


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

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


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

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

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



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

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


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

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