Google
 

Сайт Андрея Иванова

Андрей Иванов - все секреты шашек и шашистов

Login





 


 Забыли пароль?
 или новый пользователь? Зарегистрируйся!

Кто с нами

Пользователей:  На сайте
Пользователей:  Пользователей: 0
Гостей:  Гостей: 4
Всего:  Всего: 4
Пользователей:  Зарегистрированные
No members connected


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
Fenix
Тема сообщения:   СообщениеОтправлено: Янв 16, 2006 - 12:41 PM



Зарегистрирован: Сен 01, 2002
Сообщений: 8715

Интересно, а на чем должна основываться оценочная функция в поддавках???
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
Kallisto
Тема сообщения: Re: Генератор возможных ходов  СообщениеОтправлено: Янв 16, 2006 - 09:29 AM



Зарегистрирован: Авг 18, 2003
Сообщений: 747

Arigato писал(а):
Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.


Все понимают что это не так Laughing
На глубину перебора может влиять только очень медленный генератор (сделать такой не так просто).

Считается, что если шахматный генератор будет выдавать все ходы мгновенно (!!!), то скорость программы возрастет максимум на 10%.
Это не более 5 очков рейтинга Эло. Что бы заметить такое усиление нужно проводить матч из более чем 10000 партий.

Я не думаю, что в шашках ситуация значительно отличается.

Вообще, существует два основных подхода в реализации генераторов:
- доска представлена в виде массива
- доска представляется битовыми полями (битбордами BitBoard)

У каждого подхода свои преимущества и недостатки. Причем, это относится не только к генератору ходов, но и к оценочной функции.


Современные сильнейшие проги используют оба подхода.
Каллисто - массив.
Тундра - битовые поля.


Если кому-нибудь интересно могу рассказать об этих подходах более подробно.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 03:23 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
Aleksej писал(а):
Можно ссылочку на те темы, где это обсуждалось, пожалуйста.

А генератор ходов - один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции.

Попробую на пальцах пояснить факторы глубины перебора (без упорядочивания по важности):
- скорость, как здесь звучало, "генератора ходов" - кол-во ходов в секунду;
- "отсечения" в переборе;
- оптимизация перебора (сортировка ходов и т.п.) - сюда же хэш-функция (транспозиционная матрица).
Для качества игры играет роль еще несколько факторов:
- оценочная функция;
- библиотека дебютов;
- база окончаний.

Сочетание всех этих факторов и определяет качество игры программы. Факторы достаточно сложно взаимосвязаны и их правильное сочетание является весьма нетривиальной задачей.
Так что, лучше уйти от иллюзий, что для хорошей игры достаточно генерить 5 или 15 миллионов позиций в секунду. Как пример, хорошее упорядочивание ходов дает эффект сравнимый с 5-10 ускорением генерации ходов, а реализуется гораздо проще. А вот хорошая оценочная функция ощутимо замедляет (также как и база окончаний) скорость перебора...

С уважением,
Сергей Старцев
_________________________________________
Пользуюсь только программами серии Plus!
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 03:12 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
Alkand писал(а):
Да мне самому интересно, вот я пытаюсь "известно кого" спровоцировать. Embarassed Но - молчат как партизаны.

Значит ничего и нет Cool
plus600 писал(а):

________________________________________
Пользуюсь только программами серии Plus!

Десять баллов (по 5-ти бальной шкале) Very Happy Laughing Smile[/quote]
Взаимно Razz

С уважением,
Сергей Старцев

________________________________________
Пользуюсь только программами серии Plus!
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 02:52 PM



Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
plus600 писал(а):
PS Александр, кстати, как насчет "неанансированной" информации по ЭБ у других программ?

Да мне самому интересно, вот я пытаюсь "известно кого" спровоцировать. Embarassed Но - молчат как партизаны.
plus600 писал(а):

________________________________________
Пользуюсь только программами серии Plus!

Десять баллов (по 5-ти бальной шкале) Very Happy Laughing Smile

_________________
Aurora Borealis - единственный инструментарий для истинных профессионалов Smile
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 01:57 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
Alkand писал(а):
plus600 писал(а):
1. Не на этом сайте
С уважением, Сергей Старцев

Сергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой Rolling Eyes

Да, нет я имел ввиду другое (надеюсь www.gambler.ru/plus/tavlei и его форум известен, но там немного). Одной ссылкой обойтись не удастся, но хороший результат даст поиск в гугле со словами Alpha-beta и тому подобноее...

С уважением,
Сергей Старцев

PS Александр, кстати, как насчет "неанансированной" информации по ЭБ у других программ?
________________________________________
Пользуюсь только программами серии Plus!
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 12:16 PM



Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
plus600 писал(а):
1. Не на этом сайте
С уважением, Сергей Старцев

Сергей, я так понимаю, что это на вашем сайте. Так дайте человеку ссылку. Это же не реклама. Я же не зверь какой Rolling Eyes

_________________
Aurora Borealis - единственный инструментарий для истинных профессионалов Smile
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
plus600
Тема сообщения:   СообщениеОтправлено: Сен 30, 2005 - 11:07 AM



Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
1. Не на этом сайте
2. Скорость перебора (если имеется ввиду кол-во перебранных позицицй в секунду), не является основным фактором, определяющем - а) глубину перебора б) силу программы. При прочих равных условиях, это важно, при прочих неравных условиях - нет.
Как граничный пример - при абсолютно правильной оценочной функции, перебор не нужен вообще, достаточно одного вызова этой функции.

С уважением,
Сергей Старцев
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Aleksej
Тема сообщения:   СообщениеОтправлено: Сен 29, 2005 - 08:22 PM



Зарегистрирован: Июль 22, 2004
Сообщений: 22

Можно ссылочку на те темы, где это обсуждалось, пожалуйста.

А генератор ходов - один из основных факторов, влияющих на скорость перебора. Ведь на каждой итерации приходится строить новый список ходов для новой композиции.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
plus600
Тема сообщения: Re: Генератор возможных ходов  СообщениеОтправлено: Сен 25, 2005 - 12:06 PM



Зарегистрирован: Дек 24, 2002
Сообщений: 1329
Откуда : Москва
Arigato писал(а):
Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.

Очень смелое и совершенно некорректное утверждение, поскольку автор явно не берет в расчет массу других факторов. Все это уже обсуждалось многократно и повторять дискуссию здесь не вижу никакого смысла - кому интересно согут все в Интернете легко найти.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
Alkand
Тема сообщения:   СообщениеОтправлено: Сен 25, 2005 - 11:51 AM



Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
Или шашечные программисты затаились, или для них уже нет секретов в этой области. Razz
Вроде бы Тундра генерит порядка 10 млн позиций в секунду, что является рекордом для программ в русские шашки.

_________________
Aurora Borealis - единственный инструментарий для истинных профессионалов Smile
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
Arigato
Тема сообщения:   СообщениеОтправлено: Сен 25, 2005 - 09:52 AM



Зарегистрирован: Сен 17, 2005
Сообщений: 6

Что, ни кого не интересуют шашечные алгоритмы?

_________________
http://hacsoft.h14.ru/phpBB2 - форум по информационной безопасности!
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Arigato
Тема сообщения: Генератор возможных ходов  СообщениеОтправлено: Сен 17, 2005 - 03:48 PM



Зарегистрирован: Сен 17, 2005
Сообщений: 6

Все, наверное, понимают, что быстрый генератор ходов позволит произвести перебор на максимальную глубину.
Давайте обсудим различные варианты генераторов ходов для шашечной программы! Понятно, что такой генератор будет зависеть от того, как представляется доска в памяти компьютера.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Показать:     
Перейти к:  
Время в формате GMT + 3
Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
PNphpBB2 © 2003-2007 
 
Page created in 0.6951699256897 seconds.