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

← →
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]

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

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

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

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

← →
pasha_golub © (2007-07-04 15:42) [29]

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

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

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

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

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

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

← →
IMHO © (2007-07-04 15:50) [31]

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

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

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

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

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

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

← →
IMHO © (2007-07-04 15:56) [32]

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

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

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

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

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

← →
Alx2 © (2007-07-04 16:53) [33]

>IMHO © (04.07.07 13:19)

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

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

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

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

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

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

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

> Alx2 © (04.07.07 16:53) [33]

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

← →
Alx2 © (2007-07-04 17:16) [36]

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

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

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

← →
TUser © (2007-07-04 18:05) [37]

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

← →
IMHO © (2007-07-05 10:48) [38]

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

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

← →
Mystic © (2007-07-05 11:57) [39]

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

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

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

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

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

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

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

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

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

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

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

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

← →
IMHO © (2007-07-05 12:45) [40]

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

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

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

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

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

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

← →
Mystic © (2007-07-05 13:42) [41]

Ну смотри, программа считает на 20 полуходов и рассматривает 300 млн позиций (=3E+8) . В то время как общее число позиций ~ 20^20 ~ 1E+26. А что отбрасывать, это уже хитрости программиста... Некоторые программы просто делают выборочное удлинение, некоторые по материалу, некоторые еще как... Ну и эвристики всякие (хода-убийцы и т. п., pawn rasing, null move ...)

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

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

← →
Mystic © (2007-07-05 13:49) [42]

Сслыки:

http://kasparovchess.crestbook.com/viewtopic.php?id=1050

Тот путь, которым двигался М. М. Ботвинник, на сегодняшний день не имеет последователей. Создание шахматных программ пошло по пути полного перебора. Тот успех, которого добиваются нынешние программы — результат фантастического быстродействия техники и к искусственному интеллекту имеет весьма отдаленное отношение. И хотя 5-кратный чемпион мира был в полушаге от создания подлинного искусственного интеллекта, ему не хватило как раз производительной техники и самой жизни для осуществления своей заветной мечты.
http://64.ru/?/ru/magazine/year=2007&no=1&part=386&article=1491

http://kasparovchess.crestbook.com/viewtopic.php?id=679
http://atimopheyev.narod.ru/AfterPIONEER/info/PIONEER/1.htm

← →
IMHO © (2007-07-05 13:57) [43]

> Mystic © (05.07.07 13:49) [42]
>
> Тот путь, которым двигался М. М. Ботвинник, на сегодняшний
> день не имеет последователей.

А жаль, ибо это было бы ближе к AI, нежели нынешние Фрицы и Рыбки.

← →
Mystic © (2007-07-05 14:01) [44]

Почему? Человек это человек, компьютер это компьютер. Ни один человек не может прикинуться компьютером. Почему мы требуем от компьютера умения прикинуться человеком?

← →
IMHO © (2007-07-05 14:04) [45]

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

← →
Думкин © (2007-07-05 14:12) [46]

> Mystic © (05.07.07 14:01) [44]
> Почему? Человек это человек, компьютер это компьютер.

А это связано с тем, что ты говорил про вычислимость, невычислимоcть?

← →
Mystic © (2007-07-05 14:48) [47]

> А это связано с тем, что ты говорил про вычислимость, невычислимоcть?

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

← →
IMHO © (2007-07-05 14:55) [48]

например?

← →
Alx2 © (2007-07-05 15:07) [49]

>Mystic © (05.07.07 11:57)

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

Неправда ваша. К примеру, TDGammon, JellyFish (и собственный опыт) - после примерно 50000 партий на самообучении, начинается "фигасе!".
К детерминированным играм (zb шахматы) сие самообучение тоже эффективно применимо.

← →
Mystic © (2007-07-05 15:42) [50]

> Вроде человек из команды Ботвинника (Штильман) - сейчас
> довольно известный программист. Не думаю, что программисты
> Ботвинника не умели программировать, просто задача была
> поставлена очень сложная.

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

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

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

> IMHO © (05.07.07 14:55) [48]

Боюсь что буду повторяться, но например понимание того, что есть натуральное число :)

> Alx2 © (05.07.07 15:07) [49]

Я говорил конкретно про TOP шахматных программ. Перечисленные программы мне неведомы. Ну и если программа обыгрывает Вас, то это не значит, что она будет играть на уровне сильных игроков.

← →
Alx2 © (2007-07-05 15:48) [51]

>Mystic © (05.07.07 15:42)

>Я говорил конкретно про TOP шахматных программ.

Сорри. Я ушел в посте на backgammon (короткие нарды).

>Ну и если программа обыгрывает Вас, то это не значит, что она будет
>играть на уровне сильных игроков.

Да, конечно. Спасибо за науку :)
Если вдруг заинтересует - рекомендую посмотреть TD-лямбда алгоритм от Tesauro. И расширения его на детерминированные игры.

← →
mrcat_ (2007-07-05 19:04) [52]

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

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

← →
MsGuns © (2007-07-05 19:25) [53]

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

← →
TUser © (2007-07-05 19:27) [54]

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

← →
MsGuns © (2007-07-05 19:28) [55]

>TUser © (05.07.07 19:27) [54]
>Программы сегодня играют хуже (хороших) человеческих игроков

Ты не в курсе просто.

← →
IMHO © (2007-07-05 20:03) [56]

> TUser © (05.07.07 19:27) [54]
>
> Программы сегодня играют хуже (хороших) человеческих игроков.
>

Зачем говорить о том, чего не знаешь?

2006, Бонн
Крамник - Deep Fritz 2:4

Крамник, между прочим, абсолютный чемпион мира (выиграл и у Каспарова, и у Топалова)

← →
IMHO © (2007-07-05 20:34) [57]

> Mystic © (05.07.07 15:42) [50]
>
> Но в любом случае я бы не выбирал в качестве языка программирования
> FORTRAN :)

А Каисса на чем писалась?

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

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

← →
IMHO © (2007-07-05 21:05) [58]

Книга Бориса Штильмана "Лингвистическая Геометрия: От Перебора к Построению":
http://atimopheyev.narod.ru/LG01pdf_in_HTML/index.html

← →
Mystic © (2007-07-06 10:54) [59]

> на сколько я помню таблицы Налимова максимум на что способны
> - 5 фигур

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

> 2006, Бонн
> Крамник - Deep Fritz 2:4

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

> Крамник, между прочим, абсолютный чемпион мира (выиграл
> и у Каспарова, и у Топалова)

Да, но у Каспарова он выиграл в 2000 году и с тех пор не мог одержать над ним ни одной победы. И от матча уклонялся. Правда и стиль Крамника стиль достаточно антикомпьютерный, Топалову приходилось хуже.

> Кстати, Мистик, как ты думаешь, если построить полное дерево
> игры шахматы, что будет на самых концах? Ничья?

Да, скорее всего ничья. Уже сейчас тяжело получать перевес белыми в некоторых дебютах. После 1. e2-e4, например, в русской партии черные легко переходят в эндшпиль без пешки и делают ничью. Или в испанке контратака Маршалла. После 1. d2-d4 более закрытая игра, больше возможностей вынудить ошибку.

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

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

> Программы сегодня играют хуже (хороших) человеческих игроков.

Рейтинг у программ много выше. Если у Ананда рейтинг 2792, то Rybka 2.3.2 64-bit 4CPU рейтинг 3110.

← →
TUser © (2007-07-06 12:43) [60]

> MsGuns © (05.07.07 19:28) [55]
> IMHO © (05.07.07 20:03) [56]

Вы просто читать не умеете. Написано же "даже если полпроцента". А они (программы) проигрывают примерно в половине (пятьдесят процентов, то есть в сто раз больше) случаев.

← →
mrcat_ (2007-07-06 14:40) [61]

>А они (программы) проигрывают примерно в половине (пятьдесят процентов, то есть в сто раз больше) случаев.

ммм... ссылку на партию можно увидеть? В котором гросс в половине партий выиграл у Rybka2 классическим контролем...

← →
mrcat_ (2007-07-06 14:42) [62]

*ссылку на матч

← →
Mystic © (2007-07-06 14:43) [63]

> А они (программы) проигрывают примерно в половине (пятьдесят
> процентов, то есть в сто раз больше) случаев.

Программы не играют настолько часто с гроссмейстерами официальные поединки. Поэтому последнее поражение программ в официальном поединке было несколько лет назад (вроде в 2004 году Карякин обыграл Deep Junior в Бильбао). Общий результат тогда был +1-6=5 в пользу железа.

Человек получает лучше, но... зевает... Вот, например, Эльвест играл с Rybka и брал фору -- пешку. Выиграл одну партию из восьми. И вот сейчас играет матч с Rybka (программа дает фору по времени + усеченная дебютная книга + отключены эндшпильные базы), первую партию играл хорошо, получил лучше, но... ошибка и поражение :) Крамник ни разу в шести партиях не обыграл Fritz. Hydra вообще не проигрывала человеку, но там темная история, ибо программа некоммерческая, может быть они шулерят (advance)...

Вообще все сказанное тобой больше применимо не к шахматам, а к го, там программы очень слабы.

> Mystic © (06.07.07 14:43) [63]
>
> > А они (программы) проигрывают примерно в половине (пятьдесят
> > процентов, то есть в сто раз больше) случаев.
>
> Программы не играют настолько часто с гроссмейстерами официальные
> поединки.

а после матча в июне 2005 года Адамс - Hydra 0,5:5,5 (то бишь одна ничья в шести партиях) они играть вообще не будут. Или будут, но только за большие деньги.

> Mystic © (06.07.07 10:54) [59]
> > Крамник, между прочим, абсолютный чемпион мира (выиграл
> > и у Каспарова, и у Топалова)
>
> Да, но у Каспарова он выиграл в 2000 году и с тех пор не
> мог одержать над ним ни одной победы. И от матча уклонялся.
>

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

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

Все-таки есть какая-то справедливость (это я насчет Вайнштейна)

Надо отметить, что тот отбор Крамник проиграл (его выиграл Широв).

Насчет разрушил это громкие слова. Фишер ФИДЕ не разрушил, а Каспаров разрушил? Там все прогнило и до настоящего момента в большом упадке. Каспаров и Шорт договорились сами о месте проведения матча на первенство мира (Лондон, Шорт англичанин), сами нашли спонсоров (что неудивительно, первый английский претендент на мировую корону). С какой стати им надо идти на поводу у ФИДЕ и играть матч в Йемене за 20% от того призового фонда, что был бы в Лондоне? В тот момент большинство гроссмейстеров поддержало Каспарова, а Карпов и Тимман разыграли альтернативный титул ФИДЕ. А потом было два параллельных розыгрыша, после которого ФИДЕ перешло на нокауты.

Насчет Алехина, то почему он должен был играть с Капабланкой матч бесплатно? По условиям, которые выдвинул Капабланка в 1922 году, сыграть матч с ним мог лишь тот, кто предоставит призовой фонд $10k. Поэтому Капабланка не сыграл ни одного матча на первенство мира в период с 1921 по 1927 год (никто не преодолел золотой вал). Только Алехину с большим трудом удалось собрать требуемую сумму. Для него это был единственный шанс стать чемпионом (больше бы ему денег никто не дал). От Капабланки он требовал выполнения тех же условий, Капабланка спонсоров не нашел. Да и результаты Капабланки в турнирах после потери звания чемпиона мира были не блестящи -- развеялся миф о непобедимости.

По условиям лондонских соглашений Капабланка в течение года имел право на матч-реванш, но не воспользовался им. В 1928 году он некоторое время добивался изменения условий матча-реванша, пытаясь заручиться в этом поддержкой ФИДЕ, даже не консультируясь с Алехиным. Лишь после того, как было заключено соглашение о матче Алехина с Боголюбовым, Капабланка предложил матч-реванш на условиях лондонского протокола. Сторонники Капабланки утверждали, что именно он добивается матча, а Алехин уклоняется, сторонники Алехина, напротив, говорили, что Капабланка намеренно промедлил с вызовом, боясь проиграть матч-реванш. Так или иначе, личные отношения Капабланки с Алехиным были испорчены, а матч-реванш между ними так никогда и не состоялся.

Хотя мы уже ушли довольно далеко от сабжа.

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

Кроме того, почти все его книги (и 70-х годов, и 80-х годов) заканчивались на одной примерно такой ноте: "Остался всего один шаг до воплощения задуманного..."

Я не верю, что он умышленно дурачил публику. Тогда почему он так писал?

На чем, кстати, написана Каисса?

Еще, Мистик, как ты полагаешь, программа Пионер была все-таки готова? В смысле, в состоянии ли она была сыграть партию на правилам игры (пусть зевала бы, пусть делала бы ошибки, но играла бы партию от начала до конца, как это делала Каисса)?

Ботвинник ее не выносил на суд, и поэтому сложилось мнение "А был ли мальчик?"

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

← →
ArtemESC (2007-07-07 01:18) [70]

Кстатье, а где можно скачать партии гроссмейстеров?

> Еще, Мистик, как ты полагаешь, программа Пионер была все-
> таки готова? В смысле, в состоянии ли она была сыграть партию
> на правилам игры (пусть зевала бы, пусть делала бы ошибки,
> но играла бы партию от начала до конца, как это делала
> Каисса)?

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

> Мистик, ответь на такой вопрос, если возможно.
> Во всех книгах Ботвинник сетует на то, что имеющиеся в его
> распоряжение компьютеры очень слабы и это тормозит развитие
> Пионера. Но ведь по идее его направление не требовало быстродействующих
> компов, у него же не было полного перебора. Или я неправ?

Вести разработку, отладку лучше на более мощном компьютере, ведь так? Более мощный компьютер позволит провести больше экспериментов. К тому же если программа включает мало ходов в дерево, это совсем не означает того, что она ничем не занимается? Может оценивать позицию, искать факторы или еще что... Вот, например, судя по статистике, Rybka рассматривает позиций в 10 раз меньше, чем Toga. Но процессорного времени они сьедают поровну.

> Кроме того, почти все его книги (и 70-х годов, и 80-х годов)
> заканчивались на одной примерно такой ноте: "Остался всего
> один шаг до воплощения задуманного..."

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

Рассмотрим гипотетический вариант. Я разработал общие принципы организации ограниченного перебора. Если подстроить параметры p[i], то программа решает комбинацию из партии Ботвинник-Капабланка. Если их подстроить по другому, то она решает этюд Надареишвили (который не решается). Еще несколько позиций. Вроде самое сложное сделано, остался один шаг: собрать больше позиций, выделить в них факторы, ... Но когда этот шаг сделать, то окажется, что программа все равно играет плохо (зевает или ошибочно определяет параметры для позиции, которой нет в базе, и т. д.).

> На чем, кстати, написана Каисса?

Думаю, что на ассемблере, как большинство шахматных программ того времени. Но не уверен.

> ArtemESC (07.07.07 01:18) [70]

В продаже встречаются диски с программами (Fritz, Schredder, Junior), которе содержат базу партий. В интернете есть online-базы, но скачать все я не находил. Есть платные программы с подпиской на рассылку последних партий.

> Mystic © (07.07.07 11:54) [71]

Получается, Ботвинник стал заложником?
У него было множество идей (шахматы он понимал превосходно, это признают даже его враги), но не мог их формализовать, а потому доверился Штильману, Мирному и прочим, а те его "подвели".

Не лучше ли бы тогда ему просто освоить программирование, чтобы не зависить от Штильмана и прочих?

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

Вообще развитие шахматного программирование тогда шло под влиянием работ Шеннона, и программисты в этом преуспели больше шахматистов.

Кстати, недавно был мемориал Геллера (Одесса). В партии Гельфанд-Широв возникла такая позиция
http://kasparovchess.crestbook.com/scripts/24/grey/alpha/diagol.php?position=8/8/1p3pk1/2b2RPp/4P2K/2Q3PP/p4q2/8%20b%20-%20-%200%2041
Какой ход сделал Широв черными?

Слон на D4 ?

Если ладьей побьет ферзя, то поставим пешкой мат.

Ферзем на F4 он сыграл... мощно!

Нет, на 1... Сd4 есть Фc6.
В партии было 1... Фf4+ 2. gf (2. Л:f4 fgX) Сf2+ 3. Фg3 C:g3+ 4. Кр:g3 a1Ф.
Еще сильнее 1... a1Ф и нельзя 2. Ф:a1 из-за Фf4+!!

Кстати, еще симпатично
1... a1Ф 2. Л:f6+ Ф:f6 3. Ф:f6+ Ф:f6 4. gf Ce3! и мат следующим ходом (5. g4 Сf2X; 5. e5 Сg5X)

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

> Alx2 © (09.07.07 10:11) [81]

Это, конечно, хорошо, но на практике возникают следующие трудности:

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

2. Вычисление силы игры программы для некоего набора параметров процесс долгий, надо сыграть много контрольных игр чтобы понять, насколько изменилась сила игры программы.

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

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

Это не трудности. На данном этапе развития IT это непреодолимые преграды, чтобы брать и вот так в лоб использовать эти методы.

>Mystic © (09.07.07 14:10)

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

> lx2 © (09.07.07 22:48) [86]
>
> >Mystic © (09.07.07 14:10)
>
> И еще: мне кажется, у вас есть что-то вроде попытки открыть
> мне глаза на ту область, где я довольно давно и плотно работаю.
>

Можно ссылочки на ваши проекты?

> IMHO © (10.07.07 09:27) [87]

04990014470 Радионов Алексей Николаевич. Моделирование и нестандартные алгоритмы выбора стратегий в недетерминированных антагонистических играх и родственных задачах: Дис... канд. техн. наук /Ульяновский государственный университет (УлГУ) . - Защищена 1999.10.08. УДК 681. 112 с. - Библиогр.: 64 назв. Построены математическая модель недетерминированной антагонистической игры backgammon и модель соответствующей компьютерной программы. Показано влияние функции риска на тактику игры. Разработаны принципы человеко-машинного подхода, созданы иллюстрирующие его компьютерные программы для следующих двух задач: задачи о поиске последовательности символьных преобразований, упрощающих заданное символьное выражение, и задачи о поиске псевдооптимальной стратегии в детерминированных антагонистических играх с искусственным добавлением недетерминизма.

http://nauka.vprod.ru/2000/sr22_04/0013.htm

Спасибо.

> И еще: мне кажется, у вас есть что-то вроде попытки открыть
> мне глаза на ту область, где я довольно давно и плотно работаю.

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

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

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