| Автор |
Сообщение |
NS |
|
Тема сообщения:
 Отправлено: Окт 07, 2006 - 05:27 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Цитата: Еще раз хочу напомнить, что многофигурные базы сами по себе не помогут лучше играть в шашки. Прога с такой базой просто не будет проигрывать. Но выиграть ей будет очень сложно. Тут нужно нечто большее, чем ЭБ!
Раз уже есть готовый алгоритм для творческой борьбы, когда мы уже находимся в ЭБ - то ЭБ не помешает выигрывать. (например у человека, либо у программ с неполной ЭБ)
То есть программа с Полной ЭБ тоже может играть на победу!
Просто нужно параллельно улучшать чистую силу движка, без ЭБ. |
|
|
| |
|
|
|
 |
|
Kallisto |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 05:10 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
AlexanderS писал(а): NS давайте не будем заниматься фигней.
Поспокойнее! А то мы докатимся до уровня шахматных форумов, обсуждающих туалетные скандалы 
NS хотел сказать, что все шашечные ЭБ (включая 24-фигурные) никуда не влезут как не увеличивай емкость дисков.
Пока что в очень отдаленной перспективе мы можем поиметь 12-фигурные.
Еще раз хочу напомнить, что многофигурные базы сами по себе не помогут лучше играть в шашки. Прога с такой базой просто не будет проигрывать. Но выиграть ей будет очень сложно. Тут нужно нечто большее, чем ЭБ! |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 03:44 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Цитата: Вы хотите решить задачу за час?...
Нет, я не хочу решить задачу за час.
Завязался разговор, и я в нем участвую...
Когда хватает памяти - не сжимают ЭБ.
Или сжатые ЭБ вдруг стали демонстрировать преимущество по сравнению с несжатыми?!  |
|
|
| |
|
|
|
|
|
Fenix |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 03:00 PM
|
|
Зарегистрирован: Сен 01, 2002
Сообщений: 8715
|
|
NS писал(а): ...
Чтоб не мучать - в первом случае 947000 Гбайт
Во втором - 7000 Гбайт
Вы кажется думаете, что технологии застряли навсегда на месте?...
Знаете, тогда бы и обезьяна не взяла палку в руки... 
То, что кажется нереальным сегодня, покажется несерьезным завтра!
Мой первый компьютер был на 1 Гбайт...
Сейчас 40 Гбайт (прошло 2,5 года как купил), а сегодня можно купить и 300 Гбайт!
Вы хотите решить задачу за час?...
Наберитесь терпения!!!
Шейх Брунея своих детей сделал не в одночасье, а постепенно, по очереди! |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 12:37 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Диски поступят, но речь идёт только о 12-шашечной.
Сокращая объем ЭБ - вы наверно строите её с некоторой достоверностью?
Насчет построения ЭБ - доказана максимальная (лучшая) сложность алгоритмоов построения полных ЭБ, и известны алгоритмы, которые врятли возможно улучшить... Так что если придумывать алгоритмы нечеткого построения ЭБ - то что-то может и можно выдумать...
Но более интересны ЭБ со 100%-ной достоверностью.
Насчет необходимых объемов - пока речь идёт о 64-клетках, давайте просто посчитаем 100-клеточные шашки, или объемы ЭБ в шахматах. |
|
|
| |
|
|
|
|
|
AlexanderS |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 12:30 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
NS давайте не будем заниматься фигней. Во-первых, завтра терабайтные диски поступят в массовую продажу, поделите на емкость дисков лет 15-20 назад и получите что требуемый вам объем будет в обычной настольной персоналке через пару-другую десятков лет.
Во-вторых, объем реальной ранговой 12-шашечной ЭБ не будет превышать 10 терабайт, что уже сейчас вполне реально, и проблема думается не в размере дисков а в скорости генерации. Если Вы можете написать алгоритм генерации на современных компьютерах за разумное время и не хватает емкости жестких дисков - я Вам их найду
И в третьих, если вы (я) не знаем алгоритма для написания абсолютной шашечной программы это не значит что его не существует в принципе. |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 12:13 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Возможности памяти не ограничены?
Я вам напишу формулу необходимой памяти для несжатых безранговых N-шашечных баз, а вы попробуйте туда подставить 12-ть
4^N*32!/(32-N)!/N!/4 Байт
(Делим на четыре - Так как храним в байте четыре позиции)
Или формула для необходимой памяти для 12+12 простых...
32!/12!/12!/8!/4 Байт
Чтоб не мучать - в первом случае 947000 Гбайт
Во втором - 7000 Гбайт |
|
|
| |
|
|
|
|
|
Fenix |
|
|
Тема сообщения:
Отправлено: Окт 07, 2006 - 06:56 AM
|
|
Зарегистрирован: Сен 01, 2002
Сообщений: 8715
|
|
NS писал(а): Скорость света в среде не больше, а меньше
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) -
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать - сразу запустим и будем ждать результата, или будем делать перерывы - не имеет никакого значения.
Если бы была меньше, то моя память не оставила бы следов от такого сообщения! Мне говорили, что БОЛЬШЕ. И говорили вполне авторитетные в науке люди... Надо разобраться...
Как?
А как сегодня работают над решением задачи под названием РУССКИЕ ШАШКИ, "тундровцы" и Старцев? (Чуть не написал "плюсовцы", но он один...) Накапливают РЕШЕННЫЙ материал "снизу" (база окончаний - и здесь возможности памяти неограничены! - способ (2)), плюс улучшают алгоритм так сказать "пробивки" задачи (способ (1)) с учетом накопленной базы.
И плюс еще накопление миттельшпилей! Это как раз и есть те самые способы (цепочки) пробива задачи от дебюта к базе окончаний.
Здесь нет единовременности решения задачи. Задача решается кусочками. И решение её растянуто во времени настолько, насколько это надо решателю.
Вы же предлагаете (и обсуждаете) решение задачи типа: задал алгоритм и пошел (спать, пить кофе, смотреть футбол...) по своим делам. Такой способ конечно же столкнется с массой затруднений... |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 06, 2006 - 10:57 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Скорость света в среде не больше, а меньше
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) -
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать - сразу запустим и будем ждать результата, или будем делать перерывы - не имеет никакого значения. |
|
|
| |
|
|
|
|
|
Fenix |
|
|
Тема сообщения:
Отправлено: Окт 06, 2006 - 10:50 PM
|
|
Зарегистрирован: Сен 01, 2002
Сообщений: 8715
|
|
Ребята, эка вас занесло!...
Речь не шла о сиюминутном решении поставленной задачи .
Любую задачу (игру) с полной информацией можно решить двумя (а может и более, но двумя точно!) способами!
(1) – создать алгоритм полного решения (так сказать «в один присест» - с одной попытки),
(2) – создать алгоритм НАКОПЛЕНИЯ решения задачи – то есть решать задачу небольшими кусочками, суммируя результаты, и каждый раз проверяя по способу (1) – а не хватит ли копить и не решается ли УЖЕ задачи.
Первый способ, конечно же, требует и программных ухищрений, и оглядки на быстродействие, и оглядки на накопление информации. ИДЕТ МОЗГОВОЙ ШТУРМ! Но и здесь я не уверен, что проблема так уж неразрешима!...
Второй способ – это скорее разновидность первого, где НАКОПЛЕНИЕ ИНФОРМАЦИИ идет постоянно (вспомните БАЗЫ ОКОНЧАНИЙ!). Но самое главное, что этот способ позволяет не оглядываться на «ограничение на размеры ячейки памяти», так как есть неограниченная память компьютера, которую можно наращивать.
И еще. Слышал я, что 300000 – это скорость света только в вакууме, а в веществе она может быть больше…
Да. Еще. Не думаю, что этот разговор offtop...
Матч окончился!
Матч не вызвал интереса чисто шашечного, но породил этот разговор!
Так почему же его надо считать offtop??? |
|
|
| |
|
|
|
|
|
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
|
|
Возможен или нет - это науке неизвестно
И каким образом можно доказать его 100%-ную достоверность? Ретроспективным анализом?
Ведь для доказательства альфа-беты не нужен ретроспективный анализ. Для каждого алгоритма свой способ доказательства корректности. |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 06, 2006 - 02:23 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Но возможен ли алгоритм оценки со 100% достоверностью?
И каким образом можно доказать его 100%-ную достоверность?
Ретроспективным анализом? |
|
|
| |
|
|
|
|
|
Kallisto |
|
|
Тема сообщения:
Отправлено: Окт 06, 2006 - 02:08 PM
|
|
Зарегистрирован: Авг 18, 2003
Сообщений: 747
|
|
NS писал(а):
То что предельная (наилучшая) сложность ретроспективного анализа - линейная зависимость от количества результативных позиций - доказано...
Так ведь речь не о ретроспективном анализе. А о эвристическом алгоритме, который за пару минут выдает верную оценку позиции с вероятностью более 99,7% (или больше).
Доказать несуществование такого алгоритма невозможно. |
|
|
| |
|
|
|
|
|
NS |
|
|
Тема сообщения:
Отправлено: Окт 06, 2006 - 12:01 PM
|
|
Зарегистрирован: Авг 22, 2006
Сообщений: 671
Откуда : Санкт-Петербург
|
|
Kallisto писал(а): NS писал(а):
То шахматы невозможно решить за время жизни вселенной...
Современными алгоритмами на современных машинах. Кто сказал, что нет более эффективного алгоритма, который может все посчитать даже на современных компьютерах?
То что предельная (наилучшая) сложность ретроспективного анализа - линейная зависимость от количества результативных позиций - доказано... |
|
|
| |
|
|
|
|
|
|
Главная 
FAQ
Поиск
Регистрация
Войти и проверить личные сообщения
Войти 
Под-Форум
Maximize
Поиск по сайту