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

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

  1. TopicStarter Overlay

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

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

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

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

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

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

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

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

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

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


    у тебя можно генератор прервать, чтобы он потерял при
    том не очень много сделанной работы?


    Да, легко - просто записывается полностью весь массив (не просчитанным позициям изначально присваивается оценка "результат неизвестен")
    Это на первом этапе - когда два бита на позицию...
  7. TopicStarter Overlay

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

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

    Если в этом цикле не изменили оценку ни одной позиции - то все неопределенные оценки меняем на ничью и построение завершено, иначе начинаем новый цикл.

    Это самые простой способ, и есно далеко не самый быстрый. Массив оценок можно сохранять в любой момент (после завершения второго шага)
  8. WildCat Коршунов Игорь

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

    Пока результат тестового матча +5 -4 =59 в пользу стандартной версии.
  9. TopicStarter Overlay

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

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

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

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

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

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

    Код:
    int LatticeArray[45] = {0,0,0,0,0,
            0,    0,    0,    0,
         0,    4,    4,    4,        0,
           -4,   -4,   -4,    0,
         0,    4,    4,    4,        0,
           -4,   -4,   -4,    0,
         0,    4,    4,    4,        0,
           -4,   -4,   -4,    0,
         0,    0,    0,    0,        0,0,0,0,0
    };
    
    
    // здесь вычисляется разница на основе массива
    ...
    
        // решетчатость
        w_lattice = abs(w_lattice);
        if (w_lattice) score -= w_lattice - 2;
        b_lattice = abs(b_lattice);
        if (b_lattice) score += b_lattice - 2;
  13. TopicStarter Overlay

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

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    +28 -21 =445

    Учитывается решетчатость только простых. "-2" это если разница 1, то штраф 2; если 2, то 6; 3 - 10; 4 - 14. и т.д.
    т.е. разница в 1 почти не штрафуется.

    Попробую сделать решетчатость по-своему, а то этот способ мне сразу показался странным.
  15. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Прикольное это дело - шашки программить :). С одной стороны намного проще, так как нет матовых угроз и резать можно почти все что проигрывает материал, а с другой.... Проблема в том, что написать толковую оценочную в шашках еще сложнее, чем в шахматах. В шахматах за многие века игры хоть как, но формализовали статические признаки позиции. В шашках же смех : даже в учебниках дают примеры связки, тут же оговаривая, что кто кого связывает - вопрос всегда интересный и без ста грамм и некоторого опыта игры фиг разберешь :). Так как я в шашки не играю вообще, то энтузиазм к разработке этой проги у меня поубавился, хотя того же чемпиона России Plus600 моя программа с полпинка рвала вне зависимости от размерности как его, так и моих эндшпильных баз.
  16. TopicStarter Overlay

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Твоя - это "совместная" Дамира?
    Она сейчас без твоего участия развивается?
    У меня такая-же проблема - я сам в шашки не играю, хотя читал много всего и по русским и международным - но очень давно, и книг не осталось.
    Наверно накуплю литературы и буду изучать. Надеюсь что хоть что-то с оценкой получится... Хотя перекос по флангам и так смогу написать :)
  17. TopicStarter Overlay

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

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

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Да - Дамира. Я тоже считаю, что в шашках надо уходить от стандартных человеческих оценок (они все равно часто содеражт ошибки ) и учитывать исключительно подвижность шашек (как варианты: непроигрывающие материал ходы и возможности разменов, кои в русских шашках большой показатель качества позиции).
  19. WildCat Коршунов Игорь

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

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

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

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Протоколы Дамира не поддерживает - пока напарник категорически против.
    В матче по переписке идет нормальная компьютерная борьба: это человек ПЫТАЕТСЯ выиграть, компьютерная же программа либо выигрывает либо нет :). Видимо в возникших позициях конкретный глубокий счет показывает переход в ничейный табличный эндшпиль. Дамире в этом случае по барабану какой именно из ничейных ходов выбирать (она может даже в позиции с материальным перевесом отдать кучу материала и бодро заявить "А теперь уж точно ничья") :).
  22. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Видимо ты просто не в курсе дел. Кстати, не знаешь, куда Осипов пропал?
  23. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Не знаю! Мы давненько толком не общались.
  24. TopicStarter Overlay

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

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

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Книга - "Шашки - это интересно" Б. Герцензон, А Наперников Издательство "Детская литература"Все описанные в книге позиционные признаки можно формализовать и использовать в программе.
    Например Связь Флангов - это наличие шашек в центре (вертикали d,e + "основной центр" поля c5,d4,e5,f4)
    и т.д. - в качестве основного признака так-же указаны возможности ходов и разменов.
    Связка - большое количество проигрывающих ходов, запирание - отсутствие ходов (+ так-же наличие проигрывающих) и т.д.
  26. WildCat Коршунов Игорь

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

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

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

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

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

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

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

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

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

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

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

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

    Баланс флангов - Двухшашечные комбинации - две шашки на одном фланге "-" Две шашки на разных флангах "+"
    Причем мы с этим сами не должны заморачиваться, пущай программа решает уравнение, выискивает признаки, и считает их веса.
    Для начала просто берем ВСЕ двухшашечные комбинации (даже в разных углах доски), и комбинации шашки с пустым полем.
    А потом уже будем исключать. В шашках всего 4 типа шашек, и всего 32 поля. :)
  34. WildCat Коршунов Игорь

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

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

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

    Баланс - По базе двухшашечных комбинаций. Две шашки на одном фланге (двухшашечная комбинация) -1, Две шашки на разных +1.
    5 на одном фланге, 5 на другом 25-10-10=+5
    6 на одном 4 на другом 24-15-6=+3
    7 на одном 3 на другом 21-21-3=-3

    Мы не должны придумывать признаки и искать - программа методом наименьших квадратов сама найдет признаки и их веса так чтоб оценка была приближенна к реальной, полученной в результате перебора (а в результате перебора мы получаем более точную оценку, так как если у программы есть плюс не учтенный в ОФ, она переведет его в понятный ей признак)

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