- В этой теме 57 ответов, 16 участников, последнее обновление 13 лет, 7 месяцев назад сделано
.
-
Сообщения
-
Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Давайте обсудим различные варианты генераторов ходов для шашечной программы! Понятно, что такой генератор будет зависеть от того, как представляется доска в памяти компьютера.Или шашечные программисты затаились, или для них уже нет секретов в этой области.
Вроде бы Тундра генерит порядка 10 млн позиций в секунду, что является рекордом для программ в русские шашки.Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Очень смелое и совершенно некорректное утверждение, поскольку автор явно не берет в расчет массу других факторов. Все это уже обсуждалось многократно и повторять дискуссию здесь не вижу никакого смысла — кому интересно согут все в Интернете легко найти.
Можно ссылочку на те темы, где это обсуждалось, пожалуйста.
А генератор ходов — один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции.
1. Не на этом сайте
2. Скорость перебора (если имеется ввиду кол-во перебранных позицицй в секунду), не является основным фактором, определяющем — а) глубину перебора б) силу программы. При прочих равных условиях, это важно, при прочих неравных условиях — нет.
Как граничный пример — при абсолютно правильной оценочной функции, перебор не нужен вообще, достаточно одного вызова этой функции.С уважением,
Сергей Старцев1. Не на этом сайте
С уважением, Сергей СтарцевСергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой 🙄
1. Не на этом сайте
С уважением, Сергей СтарцевСергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой 🙄
Да, нет я имел ввиду другое (надеюсь http://www.gambler.ru/plus/tavlei и его форум известен, но там немного). Одной ссылкой обойтись не удастся, но хороший результат даст поиск в гугле со словами Alpha-beta и тому подобноее…
С уважением,
Сергей СтарцевPS Александр, кстати, как насчет «неанансированной» информации по ЭБ у других программ?
________________________________________
Пользуюсь только программами серии Plus!PS Александр, кстати, как насчет «неанансированной» информации по ЭБ у других программ?
Да мне самому интересно, вот я пытаюсь «известно кого» спровоцировать. 😳 Но — молчат как партизаны.
________________________________________
Пользуюсь только программами серии Plus!Десять баллов (по 5-ти бальной шкале)
😆 
Да мне самому интересно, вот я пытаюсь «известно кого» спровоцировать. 😳 Но — молчат как партизаны.
Значит ничего и нет
________________________________________
Пользуюсь только программами серии Plus!Десять баллов (по 5-ти бальной шкале)
😆 [/quote]
ВзаимноС уважением,
Сергей Старцев________________________________________
Пользуюсь только программами серии Plus!Можно ссылочку на те темы, где это обсуждалось, пожалуйста.
А генератор ходов — один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции.
Попробую на пальцах пояснить факторы глубины перебора (без упорядочивания по важности):
— скорость, как здесь звучало, «генератора ходов» — кол-во ходов в секунду;
— «отсечения» в переборе;
— оптимизация перебора (сортировка ходов и т.п.) — сюда же хэш-функция (транспозиционная матрица).
Для качества игры играет роль еще несколько факторов:
— оценочная функция;
— библиотека дебютов;
— база окончаний.Сочетание всех этих факторов и определяет качество игры программы. Факторы достаточно сложно взаимосвязаны и их правильное сочетание является весьма нетривиальной задачей.
Так что, лучше уйти от иллюзий, что для хорошей игры достаточно генерить 5 или 15 миллионов позиций в секунду. Как пример, хорошее упорядочивание ходов дает эффект сравнимый с 5-10 ускорением генерации ходов, а реализуется гораздо проще. А вот хорошая оценочная функция ощутимо замедляет (также как и база окончаний) скорость перебора…С уважением,
Сергей Старцев
_________________________________________
Пользуюсь только программами серии Plus!Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Все понимают что это не так 😆
На глубину перебора может влиять только очень медленный генератор (сделать такой не так просто).Считается, что если шахматный генератор будет выдавать все ходы мгновенно (!!!), то скорость программы возрастет максимум на 10%.
Это не более 5 очков рейтинга Эло. Что бы заметить такое усиление нужно проводить матч из более чем 10000 партий.Я не думаю, что в шашках ситуация значительно отличается.
Вообще, существует два основных подхода в реализации генераторов:
— доска представлена в виде массива
— доска представляется битовыми полями (битбордами BitBoard)У каждого подхода свои преимущества и недостатки. Причем, это относится не только к генератору ходов, но и к оценочной функции.
Современные сильнейшие проги используют оба подхода.
Каллисто — массив.
Тундра — битовые поля.Если кому-нибудь интересно могу рассказать об этих подходах более подробно.
Интересно, а на чем должна основываться оценочная функция в поддавках???
Баланс материала, централизация, подвижность. В общем все как и везде
. Тут надо понимать, что компьютер не играет в шашки (поддавки) — он играет в некую модель, реализующую правила шашек (поддавков). Чем точнее модель, тем сильнее играет компьюетр. Но «понимать» эту игру он не будет никогда.Интересно, а на чем должна основываться оценочная функция в поддавках???
Моя прога в поддавки играет очень сильно. По оценкам Левита и нескольких человек сранивавших с Тундрой.
Моя оценочная функция состоит из баланса материала + ценность полей.
Для поддавков придумать что-то большее очень тяжело. Некоторые даже баланс правильно подсчитать не могут
- Для ответа в этой теме необходимо авторизоваться.