Автор |
Сообщение |
Fenix |
|
Тема сообщения:
Отправлено: Янв 16, 2006 - 12:41 PM
|
|
Зарегистрирован: Сен 01, 2002
Сообщений: 8715
|
|
Интересно, а на чем должна основываться оценочная функция в поддавках??? |
|
|
|
|
|
Kallisto |
|
Тема сообщения: Re: Генератор возможных ходов
Отправлено: Янв 16, 2006 - 09:29 AM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
Arigato писал(а): Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Все понимают что это не так
На глубину перебора может влиять только очень медленный генератор (сделать такой не так просто).
Считается, что если шахматный генератор будет выдавать все ходы мгновенно (!!!), то скорость программы возрастет максимум на 10%.
Это не более 5 очков рейтинга Эло. Что бы заметить такое усиление нужно проводить матч из более чем 10000 партий.
Я не думаю, что в шашках ситуация значительно отличается.
Вообще, существует два основных подхода в реализации генераторов:
- доска представлена в виде массива
- доска представляется битовыми полями (битбордами BitBoard)
У каждого подхода свои преимущества и недостатки. Причем, это относится не только к генератору ходов, но и к оценочной функции.
Современные сильнейшие проги используют оба подхода.
Каллисто - массив.
Тундра - битовые поля.
Если кому-нибудь интересно могу рассказать об этих подходах более подробно. |
|
|
|
|
|
plus600 |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 03:23 PM
|
|
Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
|
|
Aleksej писал(а): Можно ссылочку на те темы, где это обсуждалось, пожалуйста.
А генератор ходов - один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции.
Попробую на пальцах пояснить факторы глубины перебора (без упорядочивания по важности):
- скорость, как здесь звучало, "генератора ходов" - кол-во ходов в секунду;
- "отсечения" в переборе;
- оптимизация перебора (сортировка ходов и т.п.) - сюда же хэш-функция (транспозиционная матрица).
Для качества игры играет роль еще несколько факторов:
- оценочная функция;
- библиотека дебютов;
- база окончаний.
Сочетание всех этих факторов и определяет качество игры программы. Факторы достаточно сложно взаимосвязаны и их правильное сочетание является весьма нетривиальной задачей.
Так что, лучше уйти от иллюзий, что для хорошей игры достаточно генерить 5 или 15 миллионов позиций в секунду. Как пример, хорошее упорядочивание ходов дает эффект сравнимый с 5-10 ускорением генерации ходов, а реализуется гораздо проще. А вот хорошая оценочная функция ощутимо замедляет (также как и база окончаний) скорость перебора...
С уважением,
Сергей Старцев
_________________________________________
Пользуюсь только программами серии Plus! |
|
|
|
|
|
plus600 |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 03:12 PM
|
|
Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
|
|
Alkand писал(а): Да мне самому интересно, вот я пытаюсь "известно кого" спровоцировать. Но - молчат как партизаны.
Значит ничего и нет
plus600 писал(а):
________________________________________
Пользуюсь только программами серии Plus!
Десять баллов (по 5-ти бальной шкале) [/quote]
Взаимно
С уважением,
Сергей Старцев
________________________________________
Пользуюсь только программами серии Plus! |
|
|
|
|
|
Alkand |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 02:52 PM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
plus600 писал(а): PS Александр, кстати, как насчет "неанансированной" информации по ЭБ у других программ?
Да мне самому интересно, вот я пытаюсь "известно кого" спровоцировать. Но - молчат как партизаны.
plus600 писал(а):
________________________________________
Пользуюсь только программами серии Plus!
Десять баллов (по 5-ти бальной шкале) |
_________________ Aurora Borealis - единственный инструментарий для истинных профессионалов
|
|
|
|
|
plus600 |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 01:57 PM
|
|
Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
|
|
Alkand писал(а): plus600 писал(а): 1. Не на этом сайте
С уважением, Сергей Старцев
Сергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой
Да, нет я имел ввиду другое (надеюсь www.gambler.ru/plus/tavlei и его форум известен, но там немного). Одной ссылкой обойтись не удастся, но хороший результат даст поиск в гугле со словами Alpha-beta и тому подобноее...
С уважением,
Сергей Старцев
PS Александр, кстати, как насчет "неанансированной" информации по ЭБ у других программ?
________________________________________
Пользуюсь только программами серии Plus! |
|
|
|
|
|
Alkand |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 12:16 PM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
plus600 писал(а): 1. Не на этом сайте
С уважением, Сергей Старцев
Сергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой |
_________________ Aurora Borealis - единственный инструментарий для истинных профессионалов
|
|
|
|
|
plus600 |
|
Тема сообщения:
Отправлено: Сен 30, 2005 - 11:07 AM
|
|
Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
|
|
1. Не на этом сайте
2. Скорость перебора (если имеется ввиду кол-во перебранных позицицй в секунду), не является основным фактором, определяющем - а) глубину перебора б) силу программы. При прочих равных условиях, это важно, при прочих неравных условиях - нет.
Как граничный пример - при абсолютно правильной оценочной функции, перебор не нужен вообще, достаточно одного вызова этой функции.
С уважением,
Сергей Старцев |
|
|
|
|
|
Aleksej |
|
Тема сообщения:
Отправлено: Сен 29, 2005 - 08:22 PM
|
|
Зарегистрирован: Июль 22, 2004
Сообщений: 22
|
|
Можно ссылочку на те темы, где это обсуждалось, пожалуйста.
А генератор ходов - один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции. |
|
|
|
|
|
plus600 |
|
Тема сообщения: Re: Генератор возможных ходов
Отправлено: Сен 25, 2005 - 12:06 PM
|
|
Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
|
|
Arigato писал(а): Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Очень смелое и совершенно некорректное утверждение, поскольку автор явно не берет в расчет массу других факторов. Все это уже обсуждалось многократно и повторять дискуссию здесь не вижу никакого смысла - кому интересно согут все в Интернете легко найти. |
|
|
|
|
|
Alkand |
|
Тема сообщения:
Отправлено: Сен 25, 2005 - 11:51 AM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
Или шашечные программисты затаились, или для них уже нет секретов в этой области.
Вроде бы Тундра генерит порядка 10 млн позиций в секунду, что является рекордом для программ в русские шашки. |
_________________ Aurora Borealis - единственный инструментарий для истинных профессионалов
|
|
|
|
|
Arigato |
|
Тема сообщения:
Отправлено: Сен 25, 2005 - 09:52 AM
|
|
Зарегистрирован: Сен 17, 2005
Сообщений: 6
|
|
|
|
|
Arigato |
|
Тема сообщения: Генератор возможных ходов
Отправлено: Сен 17, 2005 - 03:48 PM
|
|
Зарегистрирован: Сен 17, 2005
Сообщений: 6
|
|
Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Давайте обсудим различные варианты генераторов ходов для шашечной программы! Понятно, что такой генератор будет зависеть от того, как представляется доска в памяти компьютера. |
|
|
|
|
|
|