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

← →
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)...

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

← →
IMHO © (2007-07-06 16:19) [64]

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

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

← →
IMHO © (2007-07-06 17:37) [65]

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

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

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

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

← →
Mystic © (2007-07-06 18:38) [66]

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

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

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

← →
IMHO © (2007-07-06 19:22) [67]

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

← →
IMHO © (2007-07-06 19:41) [68]

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

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

Кроме того, почти все его книги (и 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)

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