Слово о Ботвиннике (шахматах и переборных задачах)

← →
IMHO © (2007-07-04 12:37) [0]

Как известно, великий советский шахматист М. Ботвинник после того, как ушел из шахмат, ударился не в политику и создание маршей несогласных, а серьезно задумался над созданием компьютерного шахматного мастера.

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

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

Как по-вашему, возможно ли вообще такое? (создание маленького дерева действительно лучших ходов)
Как мыслит человек? Может, оно тоже использует полный перебор, но просто не знает этого???

← →
Kerk © (2007-07-04 12:38) [1]

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

← →
Slider007 © (2007-07-04 12:43) [2]

Kerk © (04.07.07 12:38) [1]
Мне кажется среднестатистический человек вообще штампами мыслит. Решает ситуации по аналогии с уже возникавшими, набираясь опыта постепенно.

О возможном наличии интуиции у человека на этом форуме можно не спрашивать ? ;-)

← →
IMHO © (2007-07-04 12:44) [3]

> Kerk © (04.07.07 12:38) [1]
>
> Мне кажется среднестатистический человек вообще штампами
> мыслит. Решает ситуации по аналогии с уже возникавшими,
> набираясь опыта постепенно.

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

← →
Alx2 © (2007-07-04 12:45) [4]

>IMHO © (04.07.07 12:37)

Возможно такое.
Весь смысл в оценочной функции. Если она абсолютно точна - перебор достаточно на полхода. Иначе компенсация качества идет увеличением глубины перебора.

← →
IMHO © (2007-07-04 12:54) [5]

> Alx2 © (04.07.07 12:45) [4]
>
> >IMHO © (04.07.07 12:37)
>
> Возможно такое.
> Весь смысл в оценочной функции. Если она абсолютно точна
> - перебор достаточно на полхода.

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

Оценочная функция не влияет на количество ходов, которые смотрятся из позиции.

Вопрос в том, возможно ли не перебирать все ходы, а смотреть только стоящие???

← →
boriskb © (2007-07-04 12:56) [6]

IMHO © (04.07.07 12:37)
Как мыслит человек?

Этого не знает никто.
И хорошо бы не узнал никто и никогда.

Еще 100-200 лет назад люди были здоровее физически. Дальше ходили, больше поднимали, не травили себя достижениями химии.

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

Очередь головы?

Это называется прогрессом

Неразрешимый для меня парадокс.

← →
Alx2 © (2007-07-04 12:59) [7]

>IMHO © (04.07.07 12:54)

Если можно выбрать максимальный элемент из массива не перебирая все элементы - можно :) Например, когда на некоторой позиции достиглось экстремальное значение идеальной оценки - перебор можно останавливать и делать ход. Другое дело сколько в этом массиве элементов. Минимум - количество их из текущей позиции. Он достигается при идеальной оценке.
Но это по модели Адельсона-Вельского, Арлазарова и Донского. Каисса :)
В любом случае, должны иметь множество ходов, чтобы было из чего выбирать.

← →
Плохиш © (2007-07-04 13:09) [8]

> Еще 100-200 лет назад люди были здоровее физически. Дальше
> ходили, больше поднимали, не травили себя достижениями химии.

Да, да и вода была мокрее и небо голубее. Как там на счёт продолжительности жизни?

← →
Брюнетка © (2007-07-04 13:09) [9]

> [6] boriskb © (04.07.07 12:56)
> Еще 100-200 лет назад люди были здоровее физически. Дальше
> ходили, больше поднимали, не травили себя достижениями химии.

Что-то с трудом верится. А как же акселерация и т.п.?

← →
IMHO © (2007-07-04 13:18) [10]

Но всё это полный перебор (и Каисса была на нем построена), пусть с какими-то алгоритмами отсечения, но полный перебор. Интересует возможность рассмотрения только 3-4 ходов, как делает человек.

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

Но человек же не пользуется полным перебором!!! (или пользуется?)

← →
IMHO © (2007-07-04 13:19) [11]

Мой последний постинг для Alx2.

← →
boriskb © (2007-07-04 13:49) [12]

Плохиш © (04.07.07 13:09) [8]
Плохиш ©
Брюнетка © (04.07.07 13:09) [9]
Брюнетка ©

Медицина и санитария.
Не путайте.
Это другое

← →
БарЛог © (2007-07-04 14:25) [13]

> Вопрос в том, возможно ли не перебирать все ходы, а смотреть только стоящие???
Можно, если сначала перебрать все (заранее) и выбрать стОящие. ИМХО.

← →
Vlad Oshin © (2007-07-04 14:28) [14]

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

человек также думает, все-таки, имхо.
Уж любой ход всегда можно(нужно) смотреть!

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

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

← →
Думкин © (2007-07-04 14:36) [15]

> Плохиш © (04.07.07 13:09) [8]

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

> IMHO © (04.07.07 13:18) [10]
> Но человек же не пользуется полным перебором!!! (или пользуется?
> )

А кто его знает? Вполне допустим неконтролируемый процесс, благо у нас их валом. Ибо если бы контролировал, то Ботвинник и не мучался бы. Или божественное озарение?

← →
mrcat_ (2007-07-04 14:42) [16]

А что такое "лучший ход" ? Лучший по сравнению с чем?
Если ты делаешь ход, то опираешься на опыт полученный ранее (аналог хеша)...

← →
Думкин © (2007-07-04 14:45) [17]

Насколько помню, человек смотрит дальше 4-5, Каспаров вроде о 6 и более говорил.

← →
Плохиш © (2007-07-04 15:10) [18]

> boriskb © (04.07.07 13:49) [12]
> Плохиш © (04.07.07 13:09) [8]
> Плохиш ©
> Брюнетка © (04.07.07 13:09) [9]
> Брюнетка ©
>
> Медицина и санитария.
> Не путайте.

Да мы не путаем, а всё в комплексе рассматриваем. Фильму тут недавно посмотрел, "Парфюмер" называется, очень показательно в плане мокроты и цвета травки.

← →
IMHO © (2007-07-04 15:11) [19]

> mrcat_ (04.07.07 14:42) [16]
>
> А что такое "лучший ход" ? Лучший по сравнению с чем?

Лучший - это и есть лучший. Или нужно уже и такие вещи объяснять?

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

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

Короче, вряд ли кто сможет написать точную оценочную функцию.
Да и не нужно.

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

← →
Плохиш © (2007-07-04 15:12) [20]

> Думкин © (04.07.07 14:36) [15]
> > Плохиш © (04.07.07 13:09) [8]
>
> Это хорошо.
> Но помирают то как сейчас? Те здоровые, что продолжительность
> увеличили?
> Под капельницей, годами не видя белого света. Или еще как,
> на таком же уровне.

По всякому помирают. Видел достаточно 80-90 летних старичков местных, так они ещё и меня могут пережить...

← →
Плохиш © (2007-07-04 15:14) [21]

> Под капельницей, годами не видя белого света. Или еще как,
> на таком же уровне.

А про такие случаи очень любят журналюги трендеть, рейтинг повышают своим жёлтым листкам.

← →
Думкин © (2007-07-04 15:17) [22]

> Плохиш © (04.07.07 15:12) [20]

Дык. И тогда такие же бывали. По слухам моя пра-пра бабкак за сотню прожила и не мало. Но... и че?

> Плохиш © (04.07.07 15:14) [21]

Почему же? Вы в больнице последний раз когда были?

← →
IMHO © (2007-07-04 15:18) [23]

> Думкин © (04.07.07 14:45) [17]
>
> Насколько помню, человек смотрит дальше 4-5, Каспаров вроде
> о 6 и более говорил.

Нет, я о другом. Как далеко смотрит человек, зависит от позиции. Если вариант форсированный, то можно и на 10-15 ходов смотреть вперед. Есть очень сложные позиции со множеством ответвлений, там дальше 4-5 никто не увидит.

Я говорю о количестве ходов на одном уровне, а не вглубь. В среднем из позиции есть около 40 ходов, машина смотрит их ПОЧТИ ВСЕ, а человек берет от силы 3-4 хода.

← →
boriskb © (2007-07-04 15:19) [24]

> так они ещё и меня могут пережить...

И я про тоже :)

← →
IMHO © (2007-07-04 15:23) [25]

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

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

← →
Думкин © (2007-07-04 15:27) [26]

> IMHO © (04.07.07 15:18) [23]

Я понимаю. Но вряд ли ответ тут найден будет, ибо сам пониаешь - Ботвинникк время не зря потратил, а однако.
Человек ведь на многое оприрается, в том числе и на хешированный подсознательный опыт. И на.. везение что ли на том же уровне обоснованное.
Главное в феномене человеке мне кажется, это именно неосознанноваемость им многих его поступков. Во время сильнейшего стресса, мозг дает стоп-сигнал и вгоняет человека в обморок - а ну как зависнет и станет шизофреником? А человек на обмороки смотрит мило. Ничего такого.
Вот эта неосознанность и есть интересное, что ты и Ботвинник и хочете узнать. Но это мое ни на грамм нас не приблизило к ответу. :)
Но я думаю, вряд ли стоит говорить о 4-5 ходах. Разве что о явно мыслимых и потому застрвших в воспоминании. Ведь разбор партии всегда есть и всегда рассматривают комбинации и возможные ходы, и не далее ряда ходов и всем все понятно - а дальше, значит где то что-то в скобки берут. Как и люди в тех 4-5 ходах.

← →
Плохиш © (2007-07-04 15:35) [27]

> Думкин © (04.07.07 15:17) [22]
> > Плохиш © (04.07.07 15:12) [20]
>
> Дык. И тогда такие же бывали. По слухам

Знаешь, я свой пост не "по слухам" писал.

> Вы в больнице последний раз когда были?

1. Можно на "ты" :-)
2. У меня знакомые и в больницах работают и в домах для престарелых.
3. Говорю на основании того, что наблюдаю в районе моего теперешнего места жительства.

← →
Думкин © (2007-07-04 15:41) [28]

Ведь у людей паттернов много.

Был мальчик Сэми Решевский, которые чуть ли не с пеленок давал сеансы одновременной игры. Откуда у него был опыт???

Кто его знает, но явно ряд паттернов или засел или быстро развился. Или ...

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

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

Это имеет смысл, или будет нечто монструозное?

> Плохиш © (04.07.07 15:35) [27]

Так я это слухом для чужих называю. Для меня это не слух.

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

> Думкин © (04.07.07 15:41) [28]
>
>
> Вот какой ход в шахматах первый?

Какой первый ход считается сильнейшим, имеешь в виду?

Насчет первого хода сильные разногласия. Раузер (который погиб во время ВОВ и считался очень перспективным шахматистом) говорил: "1. e2-e4, и белые выигрывают!"

Кто-то считает лучшим 1. d2-d4

И даже 1. c2-c4 играют, как ты пишешь.

Интересно мнение Мистика по данному вопросу, он же писал переборную игровую программу.

> pasha_golub © (04.07.07 15:42) [29]
>
> Извините, может оффтоп. Но у меня сегодня такая идея в голове
> промелькнула. А что если на основе шахмат сделать такую
> себе стратежку пошаговую. То есть, например, у кажой фигуры
> будет сила атаки, коэфициент защиты и оставшееся здоровье.
> Атакует, например, пешка, ферзя, но убить за один ход не
> может, а только повредить. Потом можно добавить, что за
> пропуск хода фигура набирает какое-то кол-во здоровья. И
> т.п.

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

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

Ботвинник разбивал доску на участки: зона нападения, зона защиты. То есть не перебор, а человеческие паттерны.
Это все в его книгах, очень интересно.

Но можно ли формализовать этот алгоритм, да так, чтобы он играл в силу гроссмейстера?

>IMHO © (04.07.07 13:19)

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

> IMHO © (04.07.07 15:56) [32]

То есть паттерны. Человек эти паттерны иногда, если приучен и мозг позволяет, видит. А вот сказать - не может.

Я вот в школе учкомом заведовал, как очкарик и как теперь выяснилось ботаник, :)
вот я задачу, что про трубу, что про лодки всегда вижу в отношениях, а потом уравнениях квадратных. С одной стороны паттерны. И тут же погоняло- зубрила, зубрила.
А хрена вам. Я чувствую это. Вначале. И увидев такую задчу уже в первом классе мог сказать ответ. Как тот Гаусс, который отвалил челюсть своей учительнице. Так он и показал потом, что отвалил он ее ей не по божественному наущению, и чисто по воле своего так сказать мозга. И много моног раз, давая выкладки и про свой 17-угольник построенный циркулем и линейкой.
Так вот - многие не видят в задаче про лодку отношений и уравнений. Не видят. Это факт.
И еще во многом также. Кто преподавал - те все мои в этом вопросе.

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

>Думкин © (04.07.07 17:13)

>Но именно так и хотел сказать.

Согласен с твоими постами. Кстати, тут тоже кластеризация-паттерн: "у дураков мысли сходятся" :))

Ботвинник только думает, что он знает, как он думает. (с) шутка участников того проекта.

> Alx2 © (04.07.07 16:53) [33]
>
> >IMHO © (04.07.07 13:19)
>
> Извини, не могу ответить. Есть только досужие домыслы (если
> правильно понял вопрос). К примеру - какой-то самообучающий
> алгоритм долго-долго строит классы позиций и граф переходов
> от одного класса к другому. Дерево игры при этом неявно
> разбивается кустами-классами. Получается что-то наподобие
> хэшей для классов позиций. Для каждого класса имеется набор
> характерных представителей, для которых известно связанное
> с ним небольшое множество псевдооптимальных ходов, коими
> и ограничиваемся при переборе. Но, повторюсь, это домыслы
> только. Правда, похожие с паттернами, которые упоминал Думкин.
>

То есть не переборный вариант, а обучаемый (и постоянно обучающийся), так ведь? Но кто возьмется за обучение? Связка программист + шахматист (который еще по совместительству и опытный тренер)?

> Как известно, великий советский шахматист М. Ботвинник после
> того, как ушел из шахмат, ударился не в политику и создание
> маршей несогласных, а серьезно задумался над созданием компьютерного
> шахматного мастера.

Собственно говоря и Каспаров не забросил полностью шахматы, вот недавно вышла его книга "Дебютная революция 70-х".

> Как по-вашему, возможно ли вообще такое? (создание маленького
> дерева действительно лучших ходов)
> Как мыслит человек? Может, оно тоже использует полный перебор,
> но просто не знает этого???

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

По поводу Ботвийника, то его Пионер так никогда и не заиграл. Сам Ботвийник не был программистом, а его команда была не лучшего образца. Начнем с того, что выбор языка Fortran не лучший на то время для эффективной реализации. Было очень много подгонки. И его методы не прижились в шахматном программировании. Те же оптимизация при генерации ходов (bitboard, 0x88) гораздо более востребована.

А что касается человека, то как он мыслит никто не знает. Можно лишь делать предположения о том, что он использует (знания, память, опыт, счет вариантов). Человек запоминает рисунок позиции, планы, эмоции (выиграл у сильного человека -- субъективная оценка дебютного варианта улучшатся), и т. п.

> А что такое "лучший ход" ? Лучший по сравнению с чем?

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

> То есть не переборный вариант, а обучаемый (и постоянно обучающийся), так ведь?

Обучение практически не улучшает силу игры программ, и мало где реализовано (вроде есть у Shredder).

> Связка программист + шахматист (который еще по совместительству
> и опытный тренер)?

Сильнейшая на сегодня программа (Rybka) реализована программистом, по совместительству междунароным мастером.

> Mystic © (05.07.07 11:57) [39]
> Начнем с того, что на сегодня ни одна программа не выполняет
> полного перебора.

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

То, что отсекается часть ходов по методу Бруно (альфа-бета отсечение), - верю, но то, что вообще часть ходов даже не анализируется?

Просвяти, плиз.

Клод Шеннон предложил 2 модели: полный перебор и частичный перебор (включаются в рассмотрение не все, а только небольшое число разумных с ее точки зрения ходов)

Уверен, что второй метод, о котором мечтал Ботвинник, еще нигде не реализован (и чтобы программа играла на этой основе в силу гросса)

Слово о Ботвиннике (шахматах и переборных задачах) Найти похожие ветки