Пионер Ботвинника - К истории "незаконченной" программы

http://atimopheyev.narod.ru/AfterPIONEER/info/PIONEER/1.htm
Кто-то интересовался.
Если уже было можно удалить.

 

"Шахматы, как игра, предопределена как ничейная. Это означает, что при абсолютно правильной игре, с точки зрения Бога, любая партия при правильной игре должна закончиться вничью. А то, что у шахматистов бывают победы и поражения всего лишь означает, что в процессе игры были допущены ошибки."

То есть задача шаматной программы - заставить человека сделать ошибку. Снотворное короче, морфий.

 

Гекс, без правила swap-а выигран для начинающей стороны, с правилом swap-а - проигран. Но это не мешает в него играть, так как для доски 10x10 Выигрывающая стратегия неизвестна.
Любая игра двух соперников с полной информацией имеет точный результат (по теореме Церемело)
В шахматы этот результат неизвестен, но скорей всего это ничья.
Любая игра двух соперников имеет предопределенный результат (вес игры), но пока стратегия ведущая к этому результату неизвестна (либо известна, но не реализуема при сегодняшнем уровне развития техники и алгоритмов) - в игру можно играть.

ЗЫ. Бог тут абсолютно не при чем.

 

Значит для повышения вероятности выигрыша нужно делать не универсально хорошо играющую систему, т.е. защищающуюся. А такую, которая подстраивается под стиль противника. Теоретически шахматы игра с полной информацией, а практически выходит не с полной интерпретацией этой информации. Значит любой алгоритм среди равных ходов выбирает какие-то свои. И чем алгоритм сложнее тем больше этих априорных приоритетов.
Для обучения из общеизвестных методов лучшим является марковская цепь со скрытым слоем. Скрытый конечный автомат тут, видимо, соответствует алгоритму противника. Он строится автоматически. А шахматисты ничего нового не придумали?
В терминологии обработки сигналов это еще называется адаптивным рекуррентным фильтром. Лингвистичность метода Штильмана это тоже рекуррентность. Эти данные абстрактны, не указывают сразу "который" делать ход, а скорее "какой", требуются еще вычисления, а они постепенно добавляют предпочтений.

 

Спасибо за ссылки. Это, кажется обо мне позаботились. Тронут. Если не обо мне - все равно спасибо.
Если цитаты скомпилированы более-менее корректно, то вопрос о наследии Патриарха в этой области выглядит закрытым. А жаль.

 

Для обучения из общеизвестных методов лучшим является марковская цепь со скрытым слоем. Скрытый конечный автомат тут, видимо, соответствует алгоритму противника. Он строится автоматически.

Да нет никакого "алгоритма противника" - в прошлый раз ведь объясняли...
Никаких реальных механизмов самоубучения в шахматных программах нет!

 

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

 

Противник не говорит "Я не знаю куда ходить т.к. не могу выбрать ход. Я не успел просчитал их все до мата, и ради объективности не буду давать предпочтение ни какому." и не говорит "Ход может быть лучший, хороший, плохой или худший. Я делаю лучший. Реши сам какой именно по твоим приоритетам или объективно, если просчитал каждую ветвь до мата".
Он делает конкретный ход. Если всего возможных ходов 256 то этот ход есть сообщение размером в 8 бит информации отправленное доске. В этом сообщении часть зависит от позиции, часть от приоритетов. Если она полностью зависит от позиции значит противника действительно нет, нам известны все его ходы. Если не вся то оставшаяся все равно указывает как именно он играет.

Если, допустим, у него совсем плохой компьютер, просчитывает на 1 полуход и он использует дополнительно ГСЧ с 4-битным зерном, то за 16 ходов я даже это зерно узнаю.

Игра без противника это поиск ничьей. А нам нужно выиграть. Поэтому нужно заставить противника сделать ошибку.

 

> Он есть, алгоритм противника. Только мы постулируем, что он тождественно равен нашему

А можно ли, господа программисты, написать программу, которая в зависимости от противника меняет свой почерк. Например, играет этот монстр против Рыбки и подгружает внутри себя Рыбку. Играет против Шреддера - использует для предсказания ходов противника самого Шреддера и.т.д.

 

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

 

Нет, я не про настройки. Вот Заппа на 4 процессорах слабее Рыбки на 2. Отдаем два процессора под полноценную Рыбку и более менее точно можем предсказать как она сыграет. Остальные два процессора пытаются найти изъян в оценках Рыбки. (Вопросы соблюдения авторских прав пока для простоты не рассматриваем).

 

Не, так не получится...

 

Не совсем понимаю почему. Если вам известна стратегия противника, то вы получаете полное преимущество над ним. Во всяком случае ваш ожидаемый выигрыш будет выше, чем в случае, когда вы не имеете представления о стратегии противника.

 

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

 

Единственно что можно сделать - это "посчитать Рыбкой", и сделать лучший ход по её мнению... Лучшей стратегии быть не может.

 

Почему вы такой догматичный? Вас призывают придумать как использоваться дополнительную информацию, а вы сразу "все дураки"! Очевидно, дополнительная информация может дать уточнение, и никак не ухудшит. А может ли улучшить - видимо да.

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

 

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

 

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

 

Почему ровно на один ход? Есть дерево вариантов от Рыбки. Можно, наверное, еще какую-то информацию заставить ее выдавать. Даже мгновенная оценка позиции Рыбкой может быть полезна.

 

Ну хорошо, а если у нас есть не просто ход Рыбки в конкретной позиции а ее оценочная функция? Тогда мы получаем не один ход а все дерево вариантов с двумя оценками: одна наша, а другая - Рыбки (ну или скажем Фрукта, у него ОФ известна). Можно ли это использовать?

 

morkoffkin, без знания оценочной функции дерева вариантов у нас нет (потратив минуту на ход мы будем знать только оценку рыбкой одной позиции а не дерево).

 

Может оно не очень ветвистое, но все же дерево. Если Рыбка выдает, к примеру, 10 линий.

 

В минимаксе мы предполагаем, что противник предполагает... и т.д., что мы оба играем по минимаксу.
То есть он как раз полностью основан на использовании знания стратегии противника. Причем не знания, а предположения, и одного-единственного.

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

 

Кстати очень похоже на "холодную войну". Кажется там она называется spagetti-tactic.
Минимакс это защитный алгоритм, для слабых и мирных. Движется по седловым точкам как вдоль стеночки, осматривается.

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

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

На что минимакс не обращает внимания особенно упорно?

 

Так и на что минимакс не обращает внимания особенно упорно?)

 

Коль пошла такая пьянка - а не поднять ли нам забытую тему? Думаю самый лучший момент!