Программирование шашек. Эндшпиль в русских шашках.

Открываю эту тему на шахматном форуме, чтоб не издеваться над уважаемыми программистами на шашечном.
http://plus.gambler.ru/phpbb/viewtopic.php?mode=viewtopic&topic=12&forum=2&start=0
Они действительно пишут на таком уровне?
И вопрос по поводу эншпиля.
Выигрывают ли три дамки против простой и дамки (в общем случае, простая сразу не проводится)
И сколько требуется дамок чтоб выиграть против двух дамок?

 

С эндшпилем вопрос решил.

 

А ветку по ссылке прочитал? PlusXXX - чемпион России...

 

Автор программы - чемпиона России, в 2002-ом году не знал для чего существуют Хеш Таблицы ))

 

А как-же опровергающие ходы? Они везде работают, даже в уголках

 

Скифи - в первой половине Сентября.
Я сейчас эксперементирую с ЭБ (всё-таки сделаю безранговые, один бит на оценку (выиграна/не выиграна)) - не так много получается. На пятишашечные (4^5)*32!/27!/5! бит - 25 мегабайт.

 

Почему в Каллисто нет простейшей Эндшпильной оценки (Дамочной)?
Чтоб выиграть у n дамок, на доске должно быть не менее чем n+2 фигур, а если первая сторона заняла большую диагональ - то еще плюс одна фигура...
И ЭБ у Каллисто - сжатые? Или просто не до конечной позиции ищутся в ЭБ(ограничение по Depth)?
У меня практически моментальный доступ к ЭБ (не медленней чем оценка), и нет смысла ограничивать глубину использования ЭБ...

 

Да, примерно тоже самое.

 

То шахматы, а в шашках построение ЭБ настолько просто, что слов просто нет...
В 20 строк кода укладывется... Мне не жалко времени на простейшую процедуру, и на обдумывание структуры представления ЭБ...

 

Три дамки и шашка против трех дамок могут выиграть?
Три дамки и две шашки против трех дамок(одна из которых на главной)?
А программа считает что у неё перевес. А максимально доступны шестифигурные ЭБ...
Кстати, по поводу ЭБ - зачем разные файлы для разного соотношения материала? Это же не шахматы...

 

Проигранные не обязательны. Встретилась позиция из ЭБ - если 1 - то выиграли, если 0 - то оценка меньше либо равна нулю. После первого же хода будет понятна точная оценка. Но сэкономили 25 метров на пятифигурных....

 

Сжатые ЭБ еще 350.
Если безранговые, то судя по объему пятифигурные не сжаты...
???
Откуда?
Сортируем шашки на полях...
Кi - координата i-той шашки
Ki<k(i+1);
Чтоб найти позицию в массиве формула (например для четырехшашечной)
K4*(K4-1)*(k4-2)*(K4-3)/4!+K3*(k3-1)*(K3-2)/3!+(K2*k2-1)/2!+K1 (координаты нумеруются с нуля)
Далее по материалу - Mi - материал i-той шашки (0-белаяшашка,1-белая дамка,2-черная шашка, 3- черная дамка) получаем вторую координату.
Позиции храним с ходом белых, для хода черных просто инвентируем....
M1+M2*4+M3*(4^2)+M4*(4^3)
Доступ к битовому массиву совсем прост.. (Адрес - Div 8, бит Mod 8)
С доступом разобрались... Теперь алгоритм генерации. Или не нужен?

 

Ничего ты не понял - Двухмерный массив
из K1,K2,K3,K4 (это числа от 0 до 31) формируется первый индекс.
Из значений на этих полях (шашек) ( Формируется второй индекс)

Для примера - Белые шашка c3, e3 Черная шашка f2 и дамка g3
c3(K=10 M=0) e3(К=12,M=0) f2(7,2)g3(13,3)
Сортируем (13,3)(12,0)(10.0)(7,2)
K4=13 M4=3
K3=12 M4=0
K2=10 M4=0
K1=7 M4=2
Первый индекс 715+220+45+7
Второй 3+0*4+0*16+7*64....
С чем он пересечется? Абсолютно уникальный индекс, и ничего лишнего (не считая диагональной симметрии в дамочных позициях, и позиций с предопределенной оценкой - когда все фигуры одного цвета, но ничто не мешает их исключить из второго индекса)
Написать проверку? С перебором всех четырех-фигурных позиций(Для примера)?

Насчет сжатия - просто пять позиций в байте вместо четырех?

0, дамка на 1 - тот же индекс дамка на 0, а простая на 1.
Первый индекс естественно одинаковый (он фиксирует занятые поля, без привязки к типу шашек их занимающих), а второй разный!!!
В первом случае K1=1,M1=1 K2=0,M2=0
Во втором K1=1,M1=0, K2=0,M2=1

 

Для двух шашек
0,0 0
0,1 1
0,2 2
0,3 3
1,0 4
1,1 5
1,2 6
1,3 7
2,0 8
2,1 9
2,2 10
2,3 11
3,0 12
3,1 13
3,2 14
3,3 15
Всего 16 вариантов, из них 8 (0,1,4,5,10,11,14,15) Позиции где все шашки одного цвета -удаляем, остальные Сдвигаем, и делаем преобразование (Таблицу соответствий)
0,2 2 0
0,3 3 1
1,2 6 2
1,3 7 3
2,0 8 4
2,1 9 5
3,0 12 6
3,1 13 7

 

НЕ должны! У меня Явно не хранится ничего лишнего, очень быстро расчитывается индекс в массиве
Есно значения типа х*(х-1)/2, x*(x-1)*(x-2)/6 и т.д. - должны рассчитываться заранее, и храниться в таблице. Значение индекса по позиции - получается в один проход (бежим по позиции в порядке уменьшения номеров полей) - можно доп. информацию не хранить. (нужно только общее количество шашек)
Сжатие - на пять позиций в байте тоже осуществляется легко (Это если храним полную оценку (+,-,=) Хотя не уверен, что в случае хранения оценки выиграно/нет сильно уменьшится сила игры - хотя экономится не так много, наверно первую версию (ЭБ4) Сделаю полную, возможно даже ранговую.

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

И моё представление так-же можно легко разбить по Типам позиций (но это нужно только если библиотеки полностью не влезают в память)

Насчет оценки - я так понял основное - по координате, решетчатость (разница количества шашек с разной четностью), сбалансированность флангов (разница количества шашек). Оппозицию имеет смысл считать?

ЗЫ. А какие обычные способы расчета адреса в массиве (ЭБ)?

 

Совсем забыл. Простая шашка не может стоять на последней, так что занимаемый объем можно несколько уменьшить... Завтра над этим подумаю.