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

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

  1. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    В Москве в начале января (5-7 числа) должен состояться турнир среди шашечных программ. Моя программа "Каллисто" одна из лучших. И есть большие шансы выиграть этот турнир.
    Но самому мне поехать затруднительно из-за финансовых соображений. Может найдется добрый человек, который согласится быть оператором Каллисто на турнире?
    В прошлый раз (на первом кубке сайта "Шашки в России") оператором был Сергей Кудрявцев (www.sdchess.ru). Можете поинтересоваться у него о впечатлениях.
  2. TopicStarter Overlay

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

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

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

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

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

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

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Гостиница около 1500р. в сутки.
    Поесть - можно рублей на 500.
    Если брать гостиницу на двое суток, то без билетов получается вместе с питанием 4000р. - 150$
    Билет в оба конца (купе) тоже примерно 150$, всего 300$.
  7. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Какой-то странный турнир. В чём смысл ? Если программы сильные, то будут одни ничьи. Ну может пара партий результативных. Вон Васик поехал на чемпионат мира, и не выиграл, всем понятно, что из-за того, что было только 9 туров. Вам это надо ?
  8. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Логика железная. А зачем нужны ЧМ среди людей? Всё-равно будут ничьи...
    Какие-то странные матчи и т.д.
  9. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Хм, не знаю как сейчас, а раньше играли матч на первенство мира партий из 30 с чем-то в шашки.
    А сколько они за 3 дня турнира партий сыграют ?
  10. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Допустим по 20 партий. Неужели этого мало?
    Никто не ставит целью определить сильнейшего. В рамках одного соревнования это нереально.
    Цель любого чемпионата - определение чемпиона.
  11. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Если цель определить чемпиона — тогда и играть не надо. Просто в рулетку разыграть.

    А так спорьте с самим собой :

    Причём в шашках интервал будет больше, так сильный перекос в пользу ничьей.
  12. TopicStarter Overlay

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

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

    А в том чемпионате - говорили как раз не о чемпионе, а кто сильнее по итогам чемпионата... А об этом говорить глупо, и на 11-ти турах и на 20-ти.
    А с тем что в шашках нужно значительно больше партий для определения сильнейшего - никто с этим и не спорит...
  13. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Так вот я и говорю, зачем Кэту ехать на этот турнир если там монетки будут бросать ?
  14. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    За призом!!! Какие-бы монетки там не бросали, перевес в силе Kallisto настолько велик, что ниже второго места он встать не может...
  15. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    и пообщаться с другими разработчиками...
    Я ни одного разработчика настольных игр вживую еще не видел :)
  16. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Ну может пообщаться. А вот я видел разработчика ... :D
    Только у него с крышей были проблемы большие(старенький уже он был) и программер у него был тоже смешной — написал какой-то немеряно красивый интерфейс к проге, с кучей разных красивых полупрозрачных шахмат(он мне ещё рассказывал, как он их будет улучшать), а движок рокировался через битое поле. Убежал я от этих разработчиков...(они мне ещё рассказывали, что почему-то от них все убегают... лол)
  17. TopicStarter Overlay

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

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.234
    Симпатии:
    2.535
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    Господа шашисты, я вот призадумался, и у меня возник вопрос, может быть наивный.

    А как вы представляете в шашках ход? Координат двух полей, как в шахматах, явно мало - из-за возможных взятий по хитрым траекториям, которые могут ветвиться (и которые надо полностью сохранять, в некоторых вариантах правил - чтобы выбирать наибольшее). Значит, требуются того или иного рода списки - но тогда возникает другой вопрос, как их записывать в хэш, где каждый слот имеет фиксированный размер? Хранить в хэше указатель на какой-то элемент отдельного контейнера с ходами? Или в шашках лучший ход в хэше вообще не хранят?
  19. TopicStarter Overlay

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

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

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.234
    Симпатии:
    2.535
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    C хэшом понятно, но вопрос теперь смещается в сторону тех структур, которые выдаёт генератор...
  21. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.234
    Симпатии:
    2.535
    Репутация:
    90
    Адрес:
    Москва
    Оффлайн
    А какой, кстати, в шашках бранчинг-фактор?
  22. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    1. Сортирую не сами ходы, а порядковые номера ходов. (так как сам ход занимает достаточно много места)
    2. Для каждого хода храню Тип шашки до хода, Тип шашки после хода, Откуда ход, Куда ход, и список координат снятых шашек соперника вместе с их номиналом. (Эта информация потом используется и в Make и в UnMake)
    Для всего списка ходов храню общее значение типа ходов - Все ходы взятия, либо все ходы не взятия.
  23. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В шашках не работает NullMove, и хуже работает Хеш перекрестных позиций.
    Но в шашках меньше общее количество ходов, и можно более Агрессивно использовать отсечения (LMR/Футилити).
    Вообще получается Бренчинг-фактор чуть лучше чем в Шахматах.
  24. WildCat Коршунов Игорь

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Код:
    struct Move {
        int from;
        int to;
        bool promotion;
        int cap_sq[12];   // поля сбитых шашек
        int cap_type[12]; // типы сбитых шашек
    };
  26. WildCat Коршунов Игорь

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

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

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

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

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Понятно, Спасибо.
  30. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Вот это прикол :)
    Я нашел свою старую шашечную программу (под 1С) вместе с GUI (менеджером)
    Написана была в 2002-ом году, не мог её найти несколько лет (хотя была выложена в инете, но сайт на котором была выложена закрылся...)

    Еще поискать, и наверно найду программу в Гекс :)
    Возможно найдется и старая версия ГО...
  31. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Еще один метод подгонки ОФ - сейчас начну опробывать.
    Допустим оценка по координате.
    32 параметра для простой, 32 для дамки.
    Всего 64 параметра.
    Метод наискорейшего градиентного спуска.
    Считаем градиент. 65 версий версий программы, круговой турнир. Один круг 2080 партий.
    На каждом шаге 2 круга, 4000 партий с суперкоротким контролем.
    Если 10 секунд на партию - 10 часов на шаг, поле каждого шага получаем направление спуска.
    С полученным направлением спуска формирум несколько версий с разным шагом и находим среди версий наисильнейшую. (наискорейший спуск)
    И опять переходим к расчету градиента...
  32. WildCat Коршунов Игорь

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

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

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

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

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

    Но я попробую разные способы.
  35. TopicStarter Overlay

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

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

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