Каспаров. Шахматы как модель жизни.

Вспомнил, где я читал про количество позиций в шахматах. Чтобы быть точным, приведу цитату полностью. Возможно, я не совсем правильно понял автора:
" Для шахмат среднее количество возможных перемещений из одной позиции примерно равно 40. Это значит, что, считая на глубину 4, мы должны перебрать 40х40х40х40 = 2560 тыс. позиций, на глубину 5 - 10240 тыс. и т.д. Если мы будем продолжать дальше, то получим число, превышающее количество атомов во Вселенной....." Е.Корнилов "Программирование шахмат и других логических игр" стр. 42.

Это он про MiniMax.

 

!

 

думаю, что для того уровня Солвед, что в гомоку - этого достаточно.
Никто не сможет выиграть у программы.
10ЭБ это уже очень круто, а еще и с миллиардом готовых оценок (например для встречающихся в партиях позиций с 11-16 шашками) вполне достаточно.

Еще есть такой ньюанс - ведь нам не надо выигрывать, нам нужна ничья. И ничейным (по ЭБ, или из базы позициям) мы можем возвращать матовую оценку за сторону которой играем. Это здорово сократит перебор.
Пожно попробовать такую фигню на Скифи или Каллисто (Для начала просто изменить оценку ничейных по ЭБ позиций, и позиций с материалом недостаточным для победы), возможно и с 6ЭБ после этого не выиграть.

Кстати - не проверял, из классической позиции по 15 минут между Скифи и Каллисто есть какая-либо результативность (с 6ЭБ)? Нужен миттельшпильный самообуч? Или и так только ничьи?

 

Много. Кроме рандомности в движках можно немного варьировать контроль. Пожно попробовать стравливать две версии Скифи и несколько версий Каллисто. И это ведь всего 6ЭБ с десяткой будет совсем другой расклад.

У меня из начальной позиции пробивает до 6ЭБ, с десяткой уже будет достаточно много сидеть в ЭБ.

 

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

Итак, берем современную дебютную книгу. Количество вариантов в ней, а стало быть и позиций в конце – несколько МИЛЛИОНОВ. Но это – ВСЕХ вариантов. Мы можем выбирать из этой книги только свои любимые варианты, и этим сократить общее число ВСТРЕЧАЮЩИХСЯ позиций. Соотношение примерно такое же, как при сопоставлении объема полного перебора в дереве и альфа-бета алгоритма. Т.е. из общего числа берем корешок квадратный. Получаем уже несколько ТЫСЯЧ разных позиций на выходе из дебюта.

Дальше – если мы начинаем из этих дебютных позиций строить дерево вариантов ВПЕРЕД, то мы утонем. Но если мы поставим цели – прийти из каждой такой позиции к одной из типовых позиций миттельшпиля (оценка которых нам известна), то мы можем изменить способ поиска. Не ВПЕРЕД, а НАЗАД – от целевых позиций к одной из исходных. Это называется ретро-анализом.

Самая большая загадка в этом – что же имел в виду Каспаров, говоря о небольшом количестве типовых позиций миттельшпиля? Есть у кого-нибудь возможность спросить его об этом?

 

!

 

1. При наличии хеша не имеет разницы вперед мы идем или назад.
2. Ретроанализ возвожен только при наличии оценки всех возможных позиций, а не типовых миттельшпильных позиций.
3. Нет у нас точной оценки ни одной типовой миттельшпильной позиций, за исключением позиций где выигрывается очень много материала, ставится мат, либо у заведомо слабейшей стороны есть вечный шах.

 

!

 

Про миттельшпильный самообуч.

Что он дает в шахматах, мы вероятно скоро узнаем. У буржуев это называется "persistent hash", и реализуется в Рыбке 3. Будем надеяться, что она все-таки выйдет, и тогда посмотрим.

 

Наличие хеша позволяет решить одну конкретную позицию из множства быстрее чем ретроанализ, так как ретроанализ решает множество позиций.

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

 

Он есть в Хиарксе, весьма мощный самообуч в Шреддере. На практике он очень полезен адвансерам. Либо при наигрывании тысяч партий одним дебютом против одного и того-же соперника.

 

!

 

Что будет быстрее - не знаю. Возможно, что и вперед. Но главное - наличие этих самых целевых точек. Когда они есть, перебор можно значительно сократить и сделать его не таким безграничным. Если их нет - перебираем все подряд и тонем в необозримом океане вариантов.

 

Мне кажется, что во фразу "гроссмейстер стремится к позиции" вкладывается несколько другой смысл. Например, есть некоторый классический образец разыгрывание некоторой типовой позиции. Соответственно человек стремясь играть по известным образцам при оценке позиции пользуется своим знанием. Т. е. стремится к позиции, где известные ему позиционные ориентиры будут ярче выражены.

 

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

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

 

Какой в этом смысл? Уже есть шахматы Фишера, 960. Компьютерам хвататет трудности обычных шахмат. Никто не будет тратить драгоценное вычислительное время на "шахматы" с выдуманными правилами, даже люди не будут играть в такие игры

 

Напротив, начальная позиция симметрична и поэтому число непроигрывающих вариантов обозримо. Недаром существует каталог ограниченного набора дебютов - если сыграешь что-то другое, быстро проигрываешь. Чем дальше отходишь от начальной позиции, тем быстрее число вроде непроигрывающих позиций увеличивается и выбор становится сложнее.

 

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

 

А что нам мешает придумать?

Я тут спросил у Гугла - что такое "миттельшпильный самообуч"? Он мне выдал только посты от NS. Стало быть, NS это придумал. А до него это понятие было неизвестно.

 

На самом деле интересно проверить на компьютерах типичные по Каспарову мительшпильные позиции. В смысле, сам Гарри или комп, играющий по рекомендациям Гарри, будут страраться добиться тех целевых стратегических ориентиров, которые мерещатся Гарри Как и ув. NS, я боюсь, что результаты будут плачевными...

 

!

 

!

 

А Вы сомневаетесь, что конечный результат есть, то бишь лишь одно из тройки 1,х,2 верно?

 

!

 

а "Position Learning" Гугл тоже не знает?

 

NS, даже если так, то все же выглядит неплохо. А если и вправду не играют, как поведал WildCat, то может быть получили теоретический результат, которому следовать пока еще нельзя в условиях времевых ограничений на турнирные партии :rolleyes:

 

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

При этом сложность этих двух игр примерно одинакова.

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

 

Ну, вряд ли был "известен уже сто лет" во всю строгость, оставалось обсчитать еще кое-что из-за принципиальной случайности множества вариантов, по-видимому. А играют с жеребьевки трех ходов из-за практических соображений, чтобы игра оставалась непредсказуемой и интересной, а то комп рвал (практически!) всех и вся в классике.

 

Хайдук, это у Вас чувство юмора такое? Какой комп? Вы знаете когда первый комп появился, и когда появилась первая программа в чеккерс???
http://en.wikipedia.org/wiki/English_draughts
Жеребьевка двух ходов появилась в 1900-ом году, трех в 1934-ом.

 

Ладно, NS, если захочу, я могу быть точным, но в нашем случае игра не стоит свеч . Важно то, что комп сильнее лучших игроков, с жеребьевкой или без жеребьевки. Я доверяю Вам в том, что с жеребьевкой комп Шэффера все еще может проиграть (компу или игроку), а вот без жеребьевки он уже проиграть не может, если хватит времени следовать найденому исчерпывающему алгоритму. Проиграть может лишь соперник, если НЕ следует тому же алгоритму.