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

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

Страница 3 из 4
  1. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    В Москве в начале января (5-7 числа) должен состояться турнир среди шашечных программ. Моя программа "Каллисто" одна из лучших. И есть большие шансы выиграть этот турнир.
    Но самому мне поехать затруднительно из-за финансовых соображений. Может найдется добрый человек, который согласится быть оператором Каллисто на турнире?
    В прошлый раз (на первом кубке сайта "Шашки в России") оператором был Сергей Кудрявцев (www.sdchess.ru). Можете поинтересоваться у него о впечатлениях.
     
    WildCat, 10 дек 2006
    #71
  2. NS
    Оффлайн

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

    Репутация:
    3
    А сейчас он не может?
     
    NS, 10 дек 2006
    #72
  3. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Он собрался уезжать из Москвы на это время.
     
    WildCat, 10 дек 2006
    #73
  4. NS
    Оффлайн

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

    Репутация:
    3
    А сколько нужно денег на такую поездку?
     
    NS, 10 дек 2006
    #74
  5. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Еще нужно где-то ночь провести. Цены в Москве явно не маленькие.
     
    WildCat, 10 дек 2006
    #75
  6. NS
    Оффлайн

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

    Репутация:
    3
    Гостиница около 1500р. в сутки.
    Поесть - можно рублей на 500.
    Если брать гостиницу на двое суток, то без билетов получается вместе с питанием 4000р. - 150$
    Билет в оба конца (купе) тоже примерно 150$, всего 300$.
     
    NS, 10 дек 2006
    #76
  7. drowsy
    Оффлайн

    drowsy Учаcтник

    Репутация:
    0
    Какой-то странный турнир. В чём смысл ? Если программы сильные, то будут одни ничьи. Ну может пара партий результативных. Вон Васик поехал на чемпионат мира, и не выиграл, всем понятно, что из-за того, что было только 9 туров. Вам это надо ?
     
    drowsy, 10 дек 2006
    #77
  8. NS
    Оффлайн

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

    Репутация:
    3
    Логика железная. А зачем нужны ЧМ среди людей? Всё-равно будут ничьи...
    Какие-то странные матчи и т.д.
     
    NS, 10 дек 2006
    #78
  9. drowsy
    Оффлайн

    drowsy Учаcтник

    Репутация:
    0
    Хм, не знаю как сейчас, а раньше играли матч на первенство мира партий из 30 с чем-то в шашки.
    А сколько они за 3 дня турнира партий сыграют ?
     
    drowsy, 10 дек 2006
    #79
  10. NS
    Оффлайн

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

    Репутация:
    3
    Допустим по 20 партий. Неужели этого мало?
    Никто не ставит целью определить сильнейшего. В рамках одного соревнования это нереально.
    Цель любого чемпионата - определение чемпиона.
     
    NS, 10 дек 2006
    #80
  11. drowsy
    Оффлайн

    drowsy Учаcтник

    Репутация:
    0
    Если цель определить чемпиона — тогда и играть не надо. Просто в рулетку разыграть.

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

    Причём в шашках интервал будет больше, так сильный перекос в пользу ничьей.
     
    drowsy, 10 дек 2006
    #81
  12. NS
    Оффлайн

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

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

    А в том чемпионате - говорили как раз не о чемпионе, а кто сильнее по итогам чемпионата... А об этом говорить глупо, и на 11-ти турах и на 20-ти.
    А с тем что в шашках нужно значительно больше партий для определения сильнейшего - никто с этим и не спорит...
     
    NS, 10 дек 2006
    #82
  13. drowsy
    Оффлайн

    drowsy Учаcтник

    Репутация:
    0
    Так вот я и говорю, зачем Кэту ехать на этот турнир если там монетки будут бросать ?
     
    drowsy, 10 дек 2006
    #83
  14. NS
    Оффлайн

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

    Репутация:
    3
    За призом!!! Какие-бы монетки там не бросали, перевес в силе Kallisto настолько велик, что ниже второго места он встать не может...
     
    NS, 10 дек 2006
    #84
  15. NS
    Оффлайн

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

    Репутация:
    3
    и пообщаться с другими разработчиками...
    Я ни одного разработчика настольных игр вживую еще не видел :)
     
    NS, 10 дек 2006
    #85
  16. drowsy
    Оффлайн

    drowsy Учаcтник

    Репутация:
    0
    Ну может пообщаться. А вот я видел разработчика ... :D
    Только у него с крышей были проблемы большие(старенький уже он был) и программер у него был тоже смешной — написал какой-то немеряно красивый интерфейс к проге, с кучей разных красивых полупрозрачных шахмат(он мне ещё рассказывал, как он их будет улучшать), а движок рокировался через битое поле. Убежал я от этих разработчиков...(они мне ещё рассказывали, что почему-то от них все убегают... лол)
     
    drowsy, 10 дек 2006
    #86
  17. NS
    Оффлайн

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

    Репутация:
    3
    Ну... там вроде большинство будут вменяемые, и далеко не старички :)
     
    NS, 10 дек 2006
    #87
  18. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Господа шашисты, я вот призадумался, и у меня возник вопрос, может быть наивный.

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

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

    Репутация:
    3
    В любой игре хранят лучший ход в Хеше. :)
    У меня и в шашках, и в шахматах хранится не сам ход, а его порядковый номер в неотсортированном списке ходов выдаваемом генератором (порядок в списке есно всегда одинаков)
     
    NS, 18 дек 2006
    #89
  20. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    C хэшом понятно, но вопрос теперь смещается в сторону тех структур, которые выдаёт генератор...
     
    WinPooh, 18 дек 2006
    #90
  21. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    А какой, кстати, в шашках бранчинг-фактор?
     
    WinPooh, 18 дек 2006
    #91
  22. NS
    Оффлайн

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

    Репутация:
    3
    1. Сортирую не сами ходы, а порядковые номера ходов. (так как сам ход занимает достаточно много места)
    2. Для каждого хода храню Тип шашки до хода, Тип шашки после хода, Откуда ход, Куда ход, и список координат снятых шашек соперника вместе с их номиналом. (Эта информация потом используется и в Make и в UnMake)
    Для всего списка ходов храню общее значение типа ходов - Все ходы взятия, либо все ходы не взятия.
     
    NS, 18 дек 2006
    #92
  23. NS
    Оффлайн

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

    Репутация:
    3
    В шашках не работает NullMove, и хуже работает Хеш перекрестных позиций.
    Но в шашках меньше общее количество ходов, и можно более Агрессивно использовать отсечения (LMR/Футилити).
    Вообще получается Бренчинг-фактор чуть лучше чем в Шахматах.
     
    NS, 18 дек 2006
    #93
  24. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Отсечения лучше вообще не использовать. Достаточно просто сокращений.
     
    WildCat, 18 дек 2006
    #94
  25. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Код:
    struct Move {
    int from;
    int to;
    bool promotion;
    int cap_sq[12];   // поля сбитых шашек
    int cap_type[12]; // типы сбитых шашек
};
     
    WildCat, 18 дек 2006
    #95
  26. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    В хеше просто сохраняю откуда и куда.
     
    WildCat, 18 дек 2006
    #96
  27. NS
    Оффлайн

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

    Репутация:
    3
    Я ничего не упеваю оттестировать, но спасибо за совет - попробую отсечения убрать...
    Отсечения не использовать даже при Depth=1? То есть при этой глубине не использовать ни LMR, ни Футилити?
     
    NS, 18 дек 2006
    #97
  28. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    В шашках опасно использовать отсечения. Т.к. любой наш ход может комбинационным путем вести к выигрышу, даже если мы очень сильно отстаем от соперника.
    Но при depth == 1 можно отсекать спокойные ходы (после которых нет взятий или угроз), если мы сильно отстаем. Но большой пользы это не даст.
     
    WildCat, 18 дек 2006
    #98
  29. NS
    Оффлайн

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

    Репутация:
    3
    Понятно, Спасибо.
     
    NS, 18 дек 2006
    #99
  30. NS
    Оффлайн

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

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

    Еще поискать, и наверно найду программу в Гекс :)
    Возможно найдется и старая версия ГО...
     
    NS, 5 янв 2007
    #100
  31. NS
    Оффлайн

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

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

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Эту задачу я бы лучше генетическим алгоритмом делал.
     
    WildCat, 14 янв 2007
    #102
  33. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Ну и как она тебе? Много интересного?
     
    WildCat, 14 янв 2007
    #103
  34. NS
    Оффлайн

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

    Репутация:
    3
    Генетический алгоритм не знает какой параметр менять, а если менять случайный параметр на случайную величину - при достаточном количестве параметров мы не пойдем в нужную сторону...

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

    Но я попробую разные способы.
     
    NS, 14 янв 2007
    #104
  35. NS
    Оффлайн

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

    Репутация:
    3
    В любом случае база результатов копится, и плясать наверно лучше от версии с наибольшим рейтингом по базе, и постоянно в неё добавлять новые версии с другими значениями параметров.
     
    NS, 14 янв 2007
    #105
Страница 3 из 4