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

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

Страница 3 из 4

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

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

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    А сейчас он не может?
    NS, 9 дек 2006
    #72

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

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

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

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

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

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

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

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

  7. drowsy Учаcтник

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

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

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

  9. drowsy Учаcтник

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

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

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

  11. drowsy Учаcтник

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

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

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

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

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

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

  13. drowsy Учаcтник

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

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

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

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

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

  16. drowsy Учаcтник

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

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

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

  18. WinPooh В.М.

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

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

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

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

  20. WinPooh В.М.

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

  21. WinPooh В.М.

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

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

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

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

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

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

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

  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]; // типы сбитых шашек
};
    WildCat, 18 дек 2006
    #95

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Но я попробую разные способы.
    NS, 13 янв 2007
    #104
  35. TopicStarter Overlay

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

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

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