Анализ начальной позиции

Неужели про число Шеннона никто не слыхал?

Для шахмат это 10^120 - возможное число партий т.е. объем дерева игры.
Число уникальных позиций - 10^43, впрочем с некоторыми оговорками.

Коротко здесь:

http://en.wikipedia.org/wiki/Shannon_number

Шахматы же, я думаю, могут быть решены не перебирая всех возможных вариантов и не создавая запоминающих устройств в кубический километр объемом. Теория графов здесь, наверно, может помочь. В сущности любая позиция любой настольной игры есть граф. Правда, насколько я знаю, теории графов еще очень далеко до того, чтобы решить шахматы.

Игру «пять в ряд» не могут решить в общем виде, про более сложные случаи и речи не идет.

 

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

 

я че то тоже не въехал че за прорыв может быть в этой теории)

 

Большинство проблем, включая математических, неупорядочены сами по себе, тут дело не в мозгах решающих. Это в большой степени обесценивает попытки их решения (незамысловатым счётом, если тот вообще доступен), несмотря на практическую важность некоторых из них. Мозг ищет теорию, систему, а таких часто не бывает. Разумеется, шахматы далеко не только хаотичны, позиции со стратегиями постоянно возникают по ходу партии, но обычно чреваты множеством случайных исключений-пробоин, которые приходится бездумно считать. Острова упорядоченности в огромном океане всех позиций могут сыграть роль классов, дабы разбить и классифицировать это огромное (10^45 - 10^50) пространство и попытаться решить до конца эндшпильные классы позиций или выйти на них из других (дебютных и мительшпильных) классов :rolleyes:

 

Не надо торопиться делать утверждения про «никогда». Огюст Конт, говорят, всю жизнь утверждал, что из чего состоят звезды мы не знаем и никогда не узнаем. Так и помер твердо уверенным в своей правоте. И вскоре после его смерти спектральный анализ открыли.

Теория графов к стратегическим играм применяется, например в игре Шеннона (Shannon swithcing game) Все остальное мой wild guess.

 

Вау, конечно применяется.
И тригонометрия является основой 3-D игр.
Чем могла, помогла. Но она тоже уже ничем не поможет разработке Quake IX потому что новых синусов и косинусов нету И линейные преобразования пространства тоже не поменяются уже.
Вся теория известна.

Осталась только прикладная часть. И игры все новые и новые создаются...

 

Теория игр хорошо применяется к играм где соперники играют по одним правилам(как игра Ним).
Там есть сильные результаты, например Sprague-Grundy theorem. А шахматы относятся к partisan games,
соперники неравнозначны, один белыми играет, другой чёрными, такие игры жутко сложные. По ним, AFAIK, никаких теорем хороших нет.

 

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

 

Думаю, надо упомянуть:
A. Fraenkel and D. Lichtenstein (1981). Computing a perfect strategy for n×n chess requires time exponential in n. Journal of Combinatorial Theory A, 31(2): 199–214. (DOI)
Конечно, конкретно к нашим, всем привычным шахматам эта статья отношение имеет малое, но... оптимизма не добавляет. Понимать скорее следует так: чтобы решить обычные шахматы, нужно серьёзным образом использовать свойства именно доски 8×8 и именно такой расстановки фигур, к которой мы привыкли. На обобщениях же можно ставить крест.

 

Я бы смотрел все-таки не таблицы Налимова, а на улучшение анализа позиции. Чутье подсказывает, кто конкретный практический 7-8 фигурный эндшпиль можно рассчитать на машине даже на современном железе в разумное время (установить оценку +-, -+ или =, а не посчитать число ходов до мата). А вот построить таблицы Налимова (и их хранить) малореально.

 

Velior

Вы обожествляете шахматы)
это лишь одна из игр, в-принципе намного легче, чем то же ГО

 

Mustitz

Генератор 7-фигурных таблиц уже есть, читайте Машинное Отделение))))

 

А толку? Легким движением руки генератор 7-фигурных таблиц можно превратить в генератор 32-фигурных таблиц. Вопрос в том, есть ли сами таблицы

 

Mustitz

А что бы им не быть?
Не понимаю сути вашего вопроса.
Вы сомневаетесь что они будут построены?
Так люди тоже сомневались что будет открыта тайна атомной энергии.....
Никто также не верил, что в небе будут летать железные птицы)

 

Я не сомневаюсь, что они будут построены. Но на мой взгляд тут располагается та граница, когда провести анализ конкретно взятого окончания будет проще. Например, взять окончание ладья и две пешки против ладьи и пешки. Мне кажется, что установить результат для конкретно взятого окончания гораздо проще, чем строить общую базу. Например, если я могу получить таблицу для конкретного окончания за 15 минут, то если ли смысл тратить 10 лет на построение общей базы?

 

Mustitz

Да построена эта база уже давно!
Для кого проще то?
Прогресс идет вперед, неизвестно какие щас в секретных лабораториях компы разрабатываются, может там уже что то более крутое чем компьютеры вообще есть)
7-фигурная база уже ПОСТРОЕНА.
По-крайней мере KRpp против KRp

 

Опрос составлен некорректно, но полагаю, что результат-ничья. В ближайшие 20 лет точно не просчитают, а там посмотрим...

 

Решить шахматы нельзя ...

 

Почему?

 

Действительно, шахматы - конечная задача со строгими правилами, почему же её не решить?
Был бы комп подходящий.

 

А может кто возмётся решить мой ExtraBall?

 

Kirr, как определяете эти три разные решения? Почему интерес к шахматам должен ослабеть - ведь все равно правильные ходы будут неизвестными, а для их нахождения в некоторой конкретной позиции все равно потребовалось бы много времени? :rolleyes:

 

Насколько мне известно, Ультра-Слабое, Слабое и Строгое решения имеят точный математический смысл, о чём я спрашивал.

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

 

Я так понял речь всё-таки не о шашках, а о чеккерсе?

 

Да, строго - ничья из начальной, симметричной классической позиции. Ув. NS уверяет, что начинают и с позиций после жеребьёвки (вроде шахмат Фишера) и те позиции НЕ могут встретиться в классических шашках (чеккерсах), потому доказательство на жеребьёвку вроде не распространяется.

 

Может правильные ходы будут известны компам, но не гроссам, так как память у последних неважная . Даже компам негде хранить этот громадный (и по большому счёту бессмысленный) объём информации; даже если хранить, придётся долго искать в гигантских базах данных. Машины едут по дорогам, а пешеходы идут по тротуарам и все довольны

 

Решили шашки - звучит как "решили все популярные виды шашек", а в реальности решили один вид, причем его половину (жеребьевка не решена), причем далеко не самый известный и популярный. Ну и решение (как ты и сказал) - второго типа, нечеткое.

 

Да вроде нет, решение весьма четкое - в принципе даёт беспроигрышную игру обоим, только нельзя применять со стандартным контролем времени по причине медлительности.

 

То есть как четкое? Авторы говорят что они отсекали по материалу, и по их мнению решение не совсем четкое, а оно во как

 

И почему его нельзя применять со стандартным контролем? У них-же дерево до ЭБ построено.