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

Тема в разделе "Машинное отделение", создана пользователем NS, 31 авг 2006.

  1. TopicStarter Overlay

    NS Нефёдов Сергей

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

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    С эндшпилем вопрос решил. :)
  3. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.973
    Симпатии:
    2.181
    Репутация:
    85
    Адрес:
    Москва
    Онлайн
    По поводу компьютерных шашек было интересное интервью Алекса Моисеева, чемпиона мира по чекерсу.
    Полностью его можно прочитать на http://plus.gambler.ru/tavlei/igra/person_4.htm

    Вот несколько цитат.

  4. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А ветку по ссылке прочитал? PlusXXX - чемпион России...
  5. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.973
    Симпатии:
    2.181
    Репутация:
    85
    Адрес:
    Москва
    Онлайн
    Да, название Plus* я конечно слышал - вроде бы, там каждый номер соответствует своему варианту шашек...
    Даже ставил себе на комп когда-то демо-версию, но она на нём не задержалась - при моём отрицательном уровне игры в шашки мне интереснее с Фрицем или Рыбкой в шахматы играть, я там большее число ходов продержусь :)
  6. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Автор программы - чемпиона России, в 2002-ом году не знал для чего существуют Хеш Таблицы :)))
  7. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.973
    Симпатии:
    2.181
    Репутация:
    85
    Адрес:
    Москва
    Онлайн
    Может, в шашках они хуже работают? Поэтому и не слишком популярны...
  8. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А как-же опровергающие ходы? Они везде работают, даже в уголках :)
  9. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Ты на кого булочку крошишь? :)

    На самом деле шашки примерно на том же уровне, что и шахматы.
    Тундра, Дамира, Торнадо - хорошие программы. Каллисто ваще крута непомерно.
  10. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    На том турнире она играла очень серо и выделялась из конкурентов только длинными ничейными вариантами дебютника. Очень молодая Тундра уже была на голову выше всех. Но из-за формулы розыгрыша единственная ошибка стоила звания чемпиона.

    Ты же читал наш диалог с Плюсом на форуме шашек.ком. Неужели не понял что из себя представляет Плюс?
  11. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Когда мы сможем увидеть Скифи?
  12. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Это легко решается правилами "летающих шашек". Там около 150 начальных позиций, которые никак не могут быть получены из начальной, если играть по правилам. Т.е. все нагенерированные годами дебютники теряют всю ценность. Для генерации хорошего дебютника нужно около одного года. Т.е. сделать 150 будет очень сложно :)
  13. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Скажу, на всякий случай, что сила Chinook это еще больший миф, чем Дипблю. То сколько она слила партий несильным людям - это ваще беспредел. ОФ там от балды. Примерно как и в Дипблю.
    Современные чекерсные проги действительно круты. От русских отличаютя большими дебютниками (генерировавшимися годами) плюс очень большие и хорошие ОФ (может быть чекерс проще позволяет формализовать позиционные признаки).

    Чемпион мира по чекерс Александр Моисеев это простой мастер по русским. Просто серьезные люди в чекерс не играют (говорят, что там денег нет).
  14. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Скифи - в первой половине Сентября.
    Я сейчас эксперементирую с ЭБ (всё-таки сделаю безранговые, один бит на оценку (выиграна/не выиграна)) - не так много получается. На пятишашечные (4^5)*32!/27!/5! бит - 25 мегабайт.
  15. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Почему в Каллисто нет простейшей Эндшпильной оценки (Дамочной)?
    Чтоб выиграть у n дамок, на доске должно быть не менее чем n+2 фигур, а если первая сторона заняла большую диагональ - то еще плюс одна фигура...
    И ЭБ у Каллисто - сжатые? Или просто не до конечной позиции ищутся в ЭБ(ограничение по Depth)?
    У меня практически моментальный доступ к ЭБ (не медленней чем оценка), и нет смысла ограничивать глубину использования ЭБ...
  16. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    8.973
    Симпатии:
    2.181
    Репутация:
    85
    Адрес:
    Москва
    Онлайн
    Это что-то вроде шахмат Фишера? Жеребьевка начальной позиции?
  17. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да, примерно тоже самое.
  18. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Сначала движок сделай. Потом уже ЭБ. Ведь до ЭБ еще дотянуть надо. Ты же в шахматах за ЭБ даже и не брался.
  19. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А зачем мне эндшпильная оценка? У меня ЭБ есть.
    ЭБ не сжатые безранговые. ЭБ используются при любой глубине.
  20. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    То шахматы, а в шашках построение ЭБ настолько просто, что слов просто нет...
    В 20 строк кода укладывется... Мне не жалко времени на простейшую процедуру, и на обдумывание структуры представления ЭБ...
  21. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А проигранные?
  22. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Три дамки и шашка против трех дамок могут выиграть?
    Три дамки и две шашки против трех дамок(одна из которых на главной)?
    А программа считает что у неё перевес. А максимально доступны шестифигурные ЭБ...
    Кстати, по поводу ЭБ - зачем разные файлы для разного соотношения материала? Это же не шахматы...
  23. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Ух ты!
    У меня все, что касается ЭБ около 800 строк.
    Сжатые ЭБ еще 350.
  24. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Проигранные не обязательны. Встретилась позиция из ЭБ - если 1 - то выиграли, если 0 - то оценка меньше либо равна нулю. После первого же хода будет понятна точная оценка. Но сэкономили 25 метров на пятифигурных....
  25. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Меня не интересуют позиции с таким соотношением. ЭБ безранговые и чтобы найти лучший ход внутри базы, некоторые таблицы надо отключать на время перебора.

    Мне удобнее хранить в разных файлах. Почему такой странный вопрос? Какая разница как хранить базу? В многофигурных базах приходится даже одну таблицу хранить в нескольких файлах, т.к. они бывают больше 4 Гб.
  26. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Нужен еще один ply, чтобы разрешить ситуацию. Не думаю, что для малофигурных баз это хорошая идея.
  27. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Сжатые ЭБ еще 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)
    С доступом разобрались... Теперь алгоритм генерации. Или не нужен?
  28. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    K4*(K4-1)*(k4-2)*(K4-3)/4!+K3*(k3-1)*(K3-2)/3!+(K2*k2-1)/2!+K1 - смешиваются разные типы шашек. Получиться простая на клетке 0, дамка на 1 - тот же индекс дамка на 0, а простая на 1.

    Код сжатия не используется. Он просто существует сам по себе :)
  29. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Ничего ты не понял - Двухмерный массив
    из 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
  30. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    и позиций с предопределенной оценкой - когда все фигуры одного цвета, но ничто не мешает их исключить из второго индекса
    Интересно как? Ведь будут самые разные неправильные вторые индексы.
    M1 + M2*4 + ...
    если Mi будут только 1 или 0.
  31. TopicStarter Overlay

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Для двух шашек
    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
  32. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Красивая у тебя схема. Но обычные должны быть чуть удобнее.
  33. TopicStarter Overlay

    NS Нефёдов Сергей

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

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

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

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

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

    NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Совсем забыл. Простая шашка не может стоять на последней, так что занимаемый объем можно несколько уменьшить... Завтра над этим подумаю. :)
  35. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Обычный индекс рассчиать не намнго сложнее.
    у тебя можно генератор прервать, чтобы он потерял при
    том не очень много сделанной работы?
    Что есть у меня в ОФ все на сайте описано.
    разница количества шашек с разной четностью - это кто тебе сказал?
    оппозицию имеет смысл считать - я думаю нет, но можешь попробовать (в некоторых классах позиций точно имеет смысл это делать).
    Очень похожи на твои. Но только для разных типов шашек как-бы отдельный индекс.

Поделиться этой страницей