Google
 

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

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

Login





 


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

Кто с нами

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


Новая тема   Ответить
Предыдущая тема Версия для печати Войти и проверить личные сообщения Следующая тема
Автор Сообщение
NS
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 05:27 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Цитата:
Еще раз хочу напомнить, что многофигурные базы сами по себе не помогут лучше играть в шашки. Прога с такой базой просто не будет проигрывать. Но выиграть ей будет очень сложно. Тут нужно нечто большее, чем ЭБ!


Раз уже есть готовый алгоритм для творческой борьбы, когда мы уже находимся в ЭБ - то ЭБ не помешает выигрывать. (например у человека, либо у программ с неполной ЭБ)
То есть программа с Полной ЭБ тоже может играть на победу!

Просто нужно параллельно улучшать чистую силу движка, без ЭБ.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 05:10 PM



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

AlexanderS писал(а):
NS давайте не будем заниматься фигней.

Поспокойнее! А то мы докатимся до уровня шахматных форумов, обсуждающих туалетные скандалы Smile
NS хотел сказать, что все шашечные ЭБ (включая 24-фигурные) никуда не влезут как не увеличивай емкость дисков.
Пока что в очень отдаленной перспективе мы можем поиметь 12-фигурные.

Еще раз хочу напомнить, что многофигурные базы сами по себе не помогут лучше играть в шашки. Прога с такой базой просто не будет проигрывать. Но выиграть ей будет очень сложно. Тут нужно нечто большее, чем ЭБ!
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 03:44 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Цитата:
Вы хотите решить задачу за час?...


Нет, я не хочу решить задачу за час.
Завязался разговор, и я в нем участвую... Smile
Когда хватает памяти - не сжимают ЭБ.
Или сжатые ЭБ вдруг стали демонстрировать преимущество по сравнению с несжатыми?! Very Happy
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Fenix
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 03:00 PM



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

NS писал(а):
...

Чтоб не мучать - в первом случае 947000 Гбайт
Во втором - 7000 Гбайт


Вы кажется думаете, что технологии застряли навсегда на месте?...
Знаете, тогда бы и обезьяна не взяла палку в руки... Sad

То, что кажется нереальным сегодня, покажется несерьезным завтра!
Мой первый компьютер был на 1 Гбайт...
Сейчас 40 Гбайт (прошло 2,5 года как купил), а сегодня можно купить и 300 Гбайт!

Вы хотите решить задачу за час?...
Наберитесь терпения!!!
Шейх Брунея своих детей сделал не в одночасье, а постепенно, по очереди!
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 12:37 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Диски поступят, но речь идёт только о 12-шашечной.
Сокращая объем ЭБ - вы наверно строите её с некоторой достоверностью?
Насчет построения ЭБ - доказана максимальная (лучшая) сложность алгоритмоов построения полных ЭБ, и известны алгоритмы, которые врятли возможно улучшить... Так что если придумывать алгоритмы нечеткого построения ЭБ - то что-то может и можно выдумать...
Но более интересны ЭБ со 100%-ной достоверностью.
Насчет необходимых объемов - пока речь идёт о 64-клетках, давайте просто посчитаем 100-клеточные шашки, или объемы ЭБ в шахматах.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
AlexanderS
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 12:30 PM



Зарегистрирован: Авг 29, 2002
Сообщений: 837
Откуда : Якутск
NS давайте не будем заниматься фигней. Во-первых, завтра терабайтные диски поступят в массовую продажу, поделите на емкость дисков лет 15-20 назад и получите что требуемый вам объем будет в обычной настольной персоналке через пару-другую десятков лет.
Во-вторых, объем реальной ранговой 12-шашечной ЭБ не будет превышать 10 терабайт, что уже сейчас вполне реально, и проблема думается не в размере дисков а в скорости генерации. Если Вы можете написать алгоритм генерации на современных компьютерах за разумное время и не хватает емкости жестких дисков - я Вам их найду Smile
И в третьих, если вы (я) не знаем алгоритма для написания абсолютной шашечной программы это не значит что его не существует в принципе.
 
 Профиль пользователя отправить личное сообщение WWW ICQ 
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 12:13 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Возможности памяти не ограничены? Smile
Я вам напишу формулу необходимой памяти для несжатых безранговых N-шашечных баз, а вы попробуйте туда подставить 12-ть Smile
4^N*32!/(32-N)!/N!/4 Байт
(Делим на четыре - Так как храним в байте четыре позиции)
Или формула для необходимой памяти для 12+12 простых...
32!/12!/12!/8!/4 Байт

Чтоб не мучать - в первом случае 947000 Гбайт
Во втором - 7000 Гбайт
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Fenix
Тема сообщения:   СообщениеОтправлено: Окт 07, 2006 - 06:56 AM



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

NS писал(а):
Скорость света в среде не больше, а меньше Smile
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) -
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать - сразу запустим и будем ждать результата, или будем делать перерывы - не имеет никакого значения. Smile


Если бы была меньше, то моя память не оставила бы следов от такого сообщения! Мне говорили, что БОЛЬШЕ. И говорили вполне авторитетные в науке люди... Надо разобраться...

Как?
А как сегодня работают над решением задачи под названием РУССКИЕ ШАШКИ, "тундровцы" и Старцев? (Чуть не написал "плюсовцы", но он один...) Накапливают РЕШЕННЫЙ материал "снизу" (база окончаний - и здесь возможности памяти неограничены! - способ (2)), плюс улучшают алгоритм так сказать "пробивки" задачи (способ (1)) с учетом накопленной базы.
И плюс еще накопление миттельшпилей! Это как раз и есть те самые способы (цепочки) пробива задачи от дебюта к базе окончаний.

Здесь нет единовременности решения задачи. Задача решается кусочками. И решение её растянуто во времени настолько, насколько это надо решателю.

Вы же предлагаете (и обсуждаете) решение задачи типа: задал алгоритм и пошел (спать, пить кофе, смотреть футбол...) по своим делам. Такой способ конечно же столкнется с массой затруднений...
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 10:57 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Скорость света в среде не больше, а меньше Smile
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) -
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать - сразу запустим и будем ждать результата, или будем делать перерывы - не имеет никакого значения. Smile
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Fenix
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 10:50 PM



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

Ребята, эка вас занесло!...
Речь не шла о сиюминутном решении поставленной задачи .
Любую задачу (игру) с полной информацией можно решить двумя (а может и более, но двумя точно!) способами!
(1) – создать алгоритм полного решения (так сказать «в один присест» - с одной попытки),
(2) – создать алгоритм НАКОПЛЕНИЯ решения задачи – то есть решать задачу небольшими кусочками, суммируя результаты, и каждый раз проверяя по способу (1) – а не хватит ли копить и не решается ли УЖЕ задачи.

Первый способ, конечно же, требует и программных ухищрений, и оглядки на быстродействие, и оглядки на накопление информации. ИДЕТ МОЗГОВОЙ ШТУРМ! Но и здесь я не уверен, что проблема так уж неразрешима!...
Второй способ – это скорее разновидность первого, где НАКОПЛЕНИЕ ИНФОРМАЦИИ идет постоянно (вспомните БАЗЫ ОКОНЧАНИЙ!). Но самое главное, что этот способ позволяет не оглядываться на «ограничение на размеры ячейки памяти», так как есть неограниченная память компьютера, которую можно наращивать.

И еще. Слышал я, что 300000 – это скорость света только в вакууме, а в веществе она может быть больше…

Да. Еще. Не думаю, что этот разговор offtop...
Матч окончился!
Матч не вызвал интереса чисто шашечного, но породил этот разговор!
Так почему же его надо считать offtop???
 
 Профиль пользователя отправить личное сообщение Послать e-mail  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 05:31 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Тогда можно сказать по другому - поиск хороших ОФ идёт очень медленными Темпами, а в переборных алгоритмах вообще ничего нового практически нет.
Например в Шахматах современная оценочная функция не так уж и сильно продвинулась со времен Каиссы.
А переборные алгоритмы вообще те-же. Все изменения связаны с увеличением быстродействия и доступной памяти, а алгоритмы те-же.

Действительно революционных алгоритмов так и не появилось.

+300 Пунктов на Null Move, + 100 на LMR, +50 на NegaScout (сам метод появился только в результате увеличения доступной памяти под хеш, и принципиального преимущества по сравнению с чистой Альфа-Бетой не дает)
и т.д.

Теория построения ЭБ - такая-же как и была тогда, во времена Каиссы.

В результате оказалось что даже опираясь на знания пятнадцатилетней давности - можно весьма быстро можно написать достаточно сильную (в масштабах России) шахматную программу.
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 05:01 PM



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

Возможен или нет - это науке неизвестно Smile
И каким образом можно доказать его 100%-ную достоверность? Ретроспективным анализом?
Ведь для доказательства альфа-беты не нужен ретроспективный анализ. Для каждого алгоритма свой способ доказательства корректности.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 02:23 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Но возможен ли алгоритм оценки со 100% достоверностью?
И каким образом можно доказать его 100%-ную достоверность?
Ретроспективным анализом? Smile
 
 Профиль пользователя отправить личное сообщение  
Ответить с цитатой Наверх
Kallisto
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 02:08 PM



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

NS писал(а):

То что предельная (наилучшая) сложность ретроспективного анализа - линейная зависимость от количества результативных позиций - доказано...

Так ведь речь не о ретроспективном анализе. А о эвристическом алгоритме, который за пару минут выдает верную оценку позиции с вероятностью более 99,7% (или больше).
Доказать несуществование такого алгоритма невозможно.
 
 Профиль пользователя отправить личное сообщение Послать e-mail WWW  
Ответить с цитатой Наверх
NS
Тема сообщения:   СообщениеОтправлено: Окт 06, 2006 - 12:01 PM



Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
Kallisto писал(а):
NS писал(а):

То шахматы невозможно решить за время жизни вселенной...

Современными алгоритмами на современных машинах. Кто сказал, что нет более эффективного алгоритма, который может все посчитать даже на современных компьютерах?


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