выигрышная стратегия в шахматах

KuKat32

отчасти к hobby относится, но все-таки вопрос математический
вот клевый разговор с создателями "Каиссы"

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

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

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

Мои собеседники - генеральный директор компании Disco http://www.disco.ru/russian/ Михаил Донской и Александр Битман, математик-программист и мастер спорта по шахматам. Они, одни из авторов знаменитой советской "Каиссы" - первого чемпиона мира среди шахматных компьютерных программ.

Рассказывает Михаил Донской:

Михаил Донской:

Компьютерные шахматы начались с Клода Шенона, который в 1948 году обозначил общую схему, как компьютер мог бы играть в шахматы. И эта схема оказалась настолько удачной, что и по сей день, грубо говоря, нет программы, которая бы играла по другой схеме.

Александр Костинский:

Клод Шенон - создатель теории информации.

Михаил Донской:

Создатель теории информации и человек, делавший историю во многих областях. Первые шахматные программы появились в конце пятидесятых, сначала они были игрушечными. Играли на доске 6х6. Программы, играющие в нормальные шахматы, появились где-то в 1965 году. Первый международный матч шахматных программ был в 67 году, когда программа Института теоретической и экспериментальной физики (группа под руководством Александра Кронрода: Владимир Арлазаров, Георгий Адельсон-Вельский, Александр Битман, Анатолий Усков, Александр Животовский сделали первую программу, предтечу Каиссы) играла с программой Стэнфордского университета, созданной под руководством Джона Маккарти. Кстати, при проведении этого матча возникла проблема:

Александр Костинский:

Джон Маккартни тоже крупный кибернетик?

Михаил Донской:

Да, это автор LISP (язык программирования - А.К.). Это человек, который с Аланом Тьюрингом придумал термин искусственный интеллект. В качестве забавной черты. Можете себе представить на секундочку, что институт делал тогда атомную бомбу. И вот когда из этого института передавали в Америку по телеграфу шахматные ходы, то КГБ вообще-то стоял на ушах. В конце 60-х все шахматные программы делались в крупных физических центрах, и это не удивительно. Все мощные компьютеры стояли там.

Александр Костинский:

Вы говорите об Институте теоретической и экспериментальной физики под руководством Алиханяна?

Михаил Донской:

Алиханова. Было два брата. Один Алиханов, другой Алиханян. Потом история приобрела политическую окраску, когда Адельсон-Вельский и Кронрод подписали письмо в защиту Есенина-Вольпина, и их выгнали из этого института. Адельсона и Арлазарова взяли на работу в ИПУ (Институт проблем управления АН СССР), куда пришел и я, и в ИПУ мы сделали то, что журналист "Комсомольской правды" Хенкин назвал Каиссой. Мы-то работали без названия, без плановой темы, подпольно.

Александр Костинский:

Наверное, все-таки в рамках каких-то научных программ, или просто из интереса к теме?

Михаил Донской:

Нет, это был просто интерес. Рабочее название программы, КВО, придумала Марианна Розенфельд. КВО значит - программа, которая всех обыгрывает. Мне были интересны две вещи. Хакерское программирование в кодах, чтобы программа быстро перебирала позиции и делала ходы. Саша Битман делал всю шахматную начинку, оценочную функцию, дебютную, справочную часть. А потом мой интерес сместился в сторону математики. Мы ввели понятие подобия деревьев. Ввели довольно тяжелую геометрию на шахматных деревьях и достигли очень интересных результатов, что и сказалось потом. В 1974 году Каисса стала первым чемпионом мира среди шахматных программ. И немного в сторону. Удивительная вещь была только у нас. Половина кода Каиссы была программа, которая докладывала, как машина перебирает глубокие варианты. Во время матча с читателями "Комсомольской правды" в 1972 году, который Каисса закончила с довольно почетным счетом 1,5:0,5 очка, наша работа заключалась в том, чтобы читать каждую неделю огромные листинги переборных вариантов, и надо было быть идиотом, чтобы не заметить, что важно отсекать не плохие, а повторяющиеся ходы. И это было нашей философией, приведшей к революции. А потом это подхватили другие, так как алгоритм мы опубликовали. В 74 году вышла книга на русском языке, в 78 она была переведена Springer-Verlag. Наши алгоритмы стали общественным достоянием. И в 80-м году, играя в Австрии на чемпионате мира, мы поняли, что все наши идеи уже знают, все их у себя реализовали:

Александр Битман

Шайба была нами вброшена, техника у них была более мощной. Им и карты в руки. И дальше все пошло по нарастающей.

Михаил Донской:

В качестве примера. Нам дали месяц, спасибо советской власти, на то, чтобы подготовиться к чемпионату мира в Канаде. Мы месяц проработали на крупном вычислительном центре в Канаде - Canada System Group. И там за месяц мы провели больше экспериментов, попробовали больше вариантов алгоритмов, чем за предыдущие шесть месяцев в Москве. Все-таки это экспериментальная математика. Надо придумать алгоритм, надо его попробовать, надо получить обратную связь. Цикл экспериментов, то, что физикам хорошо понятно, для нас тоже играл большую роль. Я подчеркиваю, не так важно, на каком компьютере играешь в турнире. Очень важно, на каком компьютере проводишь эксперименты. Турнир это - выступление на защите диссертации, но диссертацию еще нужно придумать, написать, доказать все теоремы. Вот эта, экспериментальная часть работы была просто непосильна на тех компьютерах, которые мы имели, и пришлось остановить работу по совершенствованию Каиссы.

Александр Костинский:

Какого успеха добились компьютерные программы в последние двадцать лет?

Михаил Донской:

Людей, которые реально продвигают эту науку, не так много. Один из них - Ганс Берлинер очень яркая личность, профессор университета Карнеги-Меллон в Питсбурге. Он собрал очень мощную группу аспирантов, которые сделали феноменальные алгоритмы, направленные не как наши, на отсечение перебора, а, наоборот, на надежность перебора. На то, в каких позициях надо углубляться дальше, чтобы убедиться, что оценка правильная. Они внесли огромный теоретический вклад и потом, когда защитили диссертации, ушли от Берлинера в IBM и сделали программу Deep Blue. И все сегодняшние разговоры дилетантов о грубом переборе, о том, что решает мощность машины, это просто от незнания. Потому что вклад именно в теорию шахматного программирования этой группы очень велик. Они тоже открыли новое направление. Если мы ушли от общих потуг сокращать плохие ходы к сокращению похожих, одинаковых, то они - от сокращения перебора к углублению перебора в нужных местах. Они сменили парадигму, и это не замедлило сказаться на силе программы. Поэтому мне всегда очень обидно, когда говорят - мощная машина, мощная машина: Мощная машина теперь есть в доступе почти у каждого. Попробуйте сделать такую программу. А о спортивном качестве матча Каспаров - Deep Blue я, мягко говоря, небольшого мнения. Я думаю, что одна сторона играла этот матч как коммерческий, а другая как рекламный. Я не думаю, что результат этого матча означает победу искусственного разума над естественным.

Александр Костинский:

Такое впечатление, что компьютеры уже превратили на каком-то уровне шахматы в крестики-нолики.

Михаил Донской:

Все гораздо хуже. В 98 году в Линаресе как всегда был крупный турнир, а рядом с ним было много побочных. Главным из побочных турниров была "швейцарка" (проведение турнира по швейцарской системе - А.К.), куда допускались все игроки, заплатившие крупный денежный взнос. В основном в турнире играли гроссмейстеры, надеясь выиграть крупный приз. Приз выиграл человек, который до этого был известен силой игры на уровне второго или может быть первого разряда. Всех изумляло, почему в Линаресе в июне, жара, человек все время ходит в галстуке, костюме, очках. Он обыгрывал всех гроссмейстеров.

Александр Костинский:

В 98 году?

Михаил Донской:

В 98 году. За все пять партий, которые он сыграл, он сделал одну ошибку, а именно: вместо слон h2 сыграл слон g2, что злые языки относят к тому, что он не расслышал ход, который был ему передан в наушники в очках. Он не пришел на награждение, потому что к этому моменту все его ходы были повторены программой. Нашли программу, которая повторяла все эти ходы. И это практически является доказательством того, что ему помогала шахматная программа. Играя решающую партию, вместо того, чтобы в один ход взять ферзя, он наоборот пожертвовал ладью для форсированного мата в пять ходов. Это типичная компьютерная игра. Люди так принципиально не играют. А вдруг, просчитался?

Александр Костинский:

Взял ферзя и спокоен.

Михаил Донской:

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

Александр Костинский:

То есть, можно было прямо во время партии пользоваться компьютером?

Михаил Донской:

Компьютер просто стоял на турнирном столике рядом с шахматной доской. После этого матча Карпов получил психологический удар, после которого не поднялся. Я видел видеозапись матча. Если Ананд все время смотрел в компьютер, то Карпов все время смотрел на доску. Карпов играл сам, а Ананд с помощью компьютера. Ананд выиграл этот матч 5:1, без разговоров. Просто без разговоров. Возник вопрос: можно ли вообще блокировать компьютер? Ясно стало, что помощь компьютера даже на уровне ведущих гроссмейстеров - это 700-800 очков Эло.

Александр Костинский:

Это решающее преимущество.

Михаил Донской:

Абсолютно решающее.

Александр Битман

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

Михаил Донской:

Человек может сосредоточиться на стратегии, а компьютер подчистит все огрехи. О зевках нет речи. Если есть какой-то тонкий тактический вариант, он безусловно будет найден.

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

Александр Битман

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

Александр Костинский:

Шахматисты должны играть за очень мелкой металлической сеткой, чтобы до них не доходили электромагнитные волны.

Михаил Донской:

И голые, чтобы нельзя было спрятать компьютер на себе.

Александр Битман

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

Михаил Донской:

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

Александр Костинский:

Уход шахмат, это как уход футбола. Шахматы - часть культуры.

Михаил Донской:

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

Александр Битман

Я хотел бы прокомментировать эту длинную Мишину тираду. Со многим я согласен, но у меня на что-то есть и свои взгляды. То, что сказал Миша про достижения создателей Deep Blue, конечно, справедливо. Но Deep Blue - суперпрограмма, которая изначально предназначалась для борьбы с чемпионом мира. Тем не менее, прогресс в электронной технике позволил создать очень сильные программы, на уровне гроссмейстеров. То, что Ботвинник называл brute force - грубой силой. Эти программы берут за счет глубины расчета и за счет феноменальной скорости. Это, тем не менее, факт, поскольку, кроме Deep Blue, существует масса совсем миниатюрных шахматных программ. Программа Geneus-3 помещается буквально на обычной дискете в 3,5 дюйма. Ее можно подарить, передать, и она запросто бьет гроссмейстеров, по крайней мере, в относительно быстрых партиях, 5, 10, 15 минут на партию. Причем, чем меньше времени, тем меньше шансов у человека. Гроссмейстер проигрывает этой программе на домашнем компьютере, и в ней нет каких-то суперсложных алгоритмов, даже судя по ее объему.

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

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

То, что я сказал, что компьютер не играет как Бог, не совсем верно. Оказалось, что иногда он может играть как Бог. Первые программы такого рода тоже были сделаны под руководством Арлазарова в том же коллективе, который создавал Каиссу. А именно, были получены абсолютно точные оценки всех ходов и вариантов, которые возникают в малофигурных эндшпилях. В той стадии партии, когда фигур остается мало, буквально 4, 5, 6 фигур. Известным математиком Александром Львовичем Брудно, много сделавшим в области шахматного программирования, был разработан специальный алгоритм так называемого ранжирования. Оказалась, что все позиции, возникающие в малофигурных эндшпилях, можно разложить по полочкам и снабдить биркой, что эта позиция выиграна за 45 ходов, эта позиция ничейная и так далее. Компьютер, единожды проведя такой расчет, дальше держит в своей памяти на дисках всю эту базу данных и играет абсолютно оптимально. Мы сделали несколько эндшпилей: ладья с пешкой против ладьи и ферзь с единственной фиксированной пешкой g7 против ферзя. Это была сложная работа благодаря тому, что компьютеры еще не были на том уровне развития, как сейчас. И помню, как машина считала буквально сутками, но зато, единожды посчитав, эти результаты оставались и могли работать на все времена.

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

Михаил Донской:

Машина просто изменила шахматные правила, например, правило пятидесяти ходов (ранее, если в партии в течение 50 ходов не была побита ни одна фигура и не сдвинулась с места ни одна пешка, то фиксировалась ничья - А.К.) было отменено вследствие этих эндшпильных программ.

Александр Битман

Это в частности. Но машина сделала то, чего человек не мог сделать в принципе. Потому что это исключительно сложные вещи. Это то, что может Бог. Так и есть. На сайте Кена Томпсона http://cm.bell-labs.com/who/ken/ (создателя UNIX) есть рубрика - "Игра в шахматы с Богом". Он выложил на сайте образцы своих отранжированных баз, и каждый может туда войти и буквально ход за ходом разыграть эти позиции в абсолютно оптимальном режиме. Он уже все шестифигурные позиции без пешки отранжировал. Причем перебрал самые экзотические сочетания. На этом пути были достигнуты интересные результаты. Оказалось, что эндшпиль ладья с конем против двух коней выигран, и на сайте приводится вариант партии-монстра мат в 262 хода.

Александр Костинский:

И это точно посчитано.

Александр Битман

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

Все шахматы устроены таким образом. Их можно отранжировать, поднимаясь снизу вверх.

Михаил Донской:

Каждые 20 лет по одной фигуре добавлять. Когда-нибудь дойдут до 32-х.

Александр Битман

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

Михаил Донской:

Точно - крестики-нолики.

Александр Битман

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

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

Михаил Донской:

А я хотел бы вернуться к философии. Заодно упомянем фамилию, которую в этом контексте нельзя не упомянуть. Вообще в искусственном интеллекте с самого начала были два течения. Если есть сложная задача, которую мы признаем задачей искусственного интеллекта (вначале это были шахматы, распознавание образов, сейчас это распознавание речи или еще что-то), то есть два философских подхода. Один - решить задачу и черт с ним как, а второй подход - попытаться понять, как ее делает человек и повторить алгоритм решения человека. Можно сказать, компьютероморфный и антропоморфный подходы. Мы, конечно, шли по первому пути. Главное, чтобы программа играла в шахматы. А как, черт с ним. Яркий образец другого подхода к шахматам - это Михаил Моисеевич Ботвинник.

Александр Костинский:

Чемпион мира.

Михаил Донской:

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

Александр Костинский:

Программа Ботвинника называлась "Пионер"?

Михаил Донской:

Да это была программа "Пионер".

Александр Битман

Некоторые считают, что была создана такая программа "Пионер", которая была в этой области чуть ли не пионером. Тем не менее, хорошо известно, что эта программа не сыграла ни одной шахматной партии, хотя, насколько я помню, разрабатывалась больше 20 лет. Так как она не могла продемонстрировать каких-то успехов, при всем уважении к Михаилу Моисеевичу, он, конечно, человек великий, но мне казалось, что эти годы он потратил как-то не совсем плодотворно. Жалко, что он преждевременно ушел из шахмат и занялся областью, которая была далека от него. Он был специалистом в электротехнике. В какой-то момент он попал в ловушку. Ему показалось, что он может передать свои знания машине, как он их чувствует.

Александр Костинский:

Считается, что Гете называл шахматы пробным камнем интеллекта. Он ошибся. Большие шахматы уходят, и место интеллектуальной спортивной игры освобождается. Многие специалисты говорят о том, что начинается новая эпоха. Эпоха еще более древней игры - го. В Корее ее называют "бадук", в Китае - "вейчи". Любопытно, что в отличие от шахмат, попытки написать сильную компьютерную программу для Го пока не увенчались успехом. Об этом говорит Александр Битман

Александр Битман

Возраст игры го оценивается примерно в 4-5 тысяч лет. Считается, что она зародилась в Китае. Потом в средние века она просочилась в Японию, и там ее стали культивировать в буддийских монастырях. Го считалось лучшим способом для воспитания интеллектуальных способностей детей. Научиться играть в го очень легко, легче, чем в шахматы, но трудно научиться играть хорошо. В го есть игроки, которые могут дать другому игроку крупную фору вроде ферзя в шахматах и выиграть, а ему более сильный игрок может дать в свою очередь такую же фору, и тоже выиграет. В шахматах такое представить невозможно. В Японии есть свои шахматы, которые называются "сёги". Существует такая пословица. В го играют боги, в сёги - герои, в рендзю - простые смертные. Игра в го - многоплановая, многостадийная как будто играются несколько шахматных партий. Борьба полыхает по всей доске, происходят жуткие катаклизмы. Когда человек приходит в себя после закончившейся партии он, не знает на какой планете он находится и в каком времени. Настолько все захватывающе и эмоционально.

Александр Костинский:

Что происходит с программированием Го?

Александр Битман

История программирования Го столь же длинная, как и у шахмат. Помню, когда Миша Донской ездил в свое время на конгрессы по искусственному интеллекту, он привозил оттуда толстый талмуд, в котором наряду с шахматным программированием обсуждались и проблемы го-программ. Нельзя сказать, что этим совсем не занимались. Просто создание качественной программы для го требует больших усилий, начиная с гораздо большей размерности и кончая тем, что там трудно формализовать чисто специфические понятия го, которые формулируются в терминах узнавания, похожести. Кроме того, в го - более тонкая, изощренная логика, которая подчас не раскладывается на рациональные элементы. Го ближе к искусству. Недаром в Японии эту игру называют: го - искусство гармонии. Поэтому, когда шахматы в некотором смысле исчерпали себя в качестве модели искусственного интеллекта, то вполне не грех научным организациям и коллективам программистов более плотно заняться проблемой сильной го-программы. Потому что те программы, которые существуют сейчас, их силу можно оценить примерно так, сравнивая с шахматами. Они играют в силу 4-5 шахматного разряда. Работы по созданию программ для игры в Го возможно дадут новый импульс теории создания искусственного интеллекта.

По оценкам некоторых американских специалистов не ранее, чем через 20-30 лет будут созданы программы, которые смогут реально служить спарринг-партнером человеку и в этом направлении будет какой-то реальный прогресс.


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

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

mtk79

Нет, не правильно.
Число фигурок и клеток конечно и относительно невелико, соответственно, число шахматных фраз тоже конечно (если кооперативно не делать их бесконечными) и уж по-любому их перебор доступен современным компъютерам. Поскольку мы не видим в партиях одних и тех же ходов — то и стратегию еще не придумали, а в силу доступности перебора, ее и нет.
А вот то, что бог (упомянутый Вами) есть или нет — действительно пока никто не доказал (и даже толком не определил)

spiritmc

> Поскольку мы не видим в партиях одних и тех же ходов
Ну да? Не видим.
---
...Я работаю антинаучным аферистом...

mtk79

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

spiritmc

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

Focz

Число фигурок и клеток конечно и относительно невелико, соответственно, число шахматных фраз тоже конечно (если кооперативно не делать их бесконечными) и уж по-любому их перебор доступен современным компъютерам.
Хмм. 32 фигуры, даже считая что все белые и все черные фигуры одинаковые, можно разместить на доске 64!/(32!*16!*16!) способами, что больше чем 10^28. Я не думаю, что современные компьютеры способны столько перебрать.

Lokomotiv59

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

Focz

Ну разумеется перебор доступен всем современным компьютерам! У тебя вот современный компьютер? Может тогда, в целях принесения пользы человечеству, извержения вулканов заодно рассчитывать будешь?
Если честно, не понял. Я имел ввиду, что 10^28 позиций современный компъютер не сможет перебрать за разумное время. Например, если производительность системы 200 терафлоп и на каждую позицию она тратит 1 флоп (на самом деле больше то столько позиций она переберет за 1.5млн лет.

kachokslava

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

vitamin8808


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

да

seregaohota

Крамник собирается играть с шахматным компьютером. И я не слышал, чтобы это Каисса была.
Говорит, что это вероятно последняя возможность для человека выиграть у компьютера. В шашки я слышал чел давным давно компьютеру проигрывает.
Наверное за белых выигрыш. 60% на 40% в турнирной практике результативные партии заканчиваются в пользу белых где-то я слышал.
Есть анекдот, как чел садится играть с компом за белых, ходит e2-e4, компьютер в ответ долго думает, а потом сдаётся.
Про правило 50 ходов: в окончании король+ферзь+пешка против король+ферзь выигрыш достигается манёврами, при которых пешка не двигается с места больше 50 ходов. Правда человек против компьютера такие окончания проигрывает вчистую.

vitamin8808

в шашках ууже многие дебюты просчитаны до ничьей. В настоящее время никто с программой chinook не может соревноваться, а на их сайте можно прочитать, какие уже дебюты просчитаны полностью, а какие нет.
http://en.wikipedia.org/wiki/Chinook_%28draughts_player%29
http://www.cs.ualberta.ca/~chinook/

vitamin8808

прога, с которой он играет, далеко не самая сильная. Есть Rybka которая этого Фрица дерёт в одни ворота, разница в рейтинге пунктов 200 почти.

seregaohota

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

stat52349

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

Lokomotiv59

Откуда взялось 10^28 ? Число _позиций_ можно оценить как 10^28. А количество ходов можно оцыенить грубо как 50*(32+16*7). Значит, кол-во партий не превосходит 10^201600

Focz

Откуда взялось 10^28 ? Число _позиций_ можно оценить как 10^28. А количество ходов можно оцыенить грубо как 50*(32+16*7). Значит, кол-во партий не превосходит 10^201600
10^28 - оценка числа позиций снизу. Ты оцениваешь число партий сверху. Где противоречие?

zuzaka

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

andreyyy

в) либо есть стратегия для ничьей.
для белых или для черных, или для тех и других?

zuzaka

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

ARTi

шахматы Фишера, придуманные, соответственно, Фишером
там есть еще одно правило - на последней горизонтали ладьи должны стоять по разные стороны от короля

andreyyy

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

zuzaka

не любую, а ту, в которой белые не попытаются выиграть
впрочем, я в этом не разбираюсь

Zoltan

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

andreyyy

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

chel_1992

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

seregaohota

В том, что игрок начальную раскладку выбирает сам и их на произвольные поля может ставить, а не только в углы.
Крамник просмотрел мат в 1 ход в матче против программы Фриц. Сказал, такого не было за всю его карьеру. Не видать ему миллиона баксов, только 500 тысяч. А может он на тотализаторе миллионов 10 поставил на свой проигрыш?
Как в анекдоте. Играю со своим компом в карты на деньги. На 2й апгрейд себе уже гад зарабатывает.
Чтобы комп нельзя было отличить от человека при игре в шахматы надо ему тоже зевки заложить в программу.

chel_1992

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

CokpaT

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

chel_1992

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

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

Nitochka

Слоны не могут стоять на клетках одного цвета

chel_1992

единственное условие - нельзя однопольных слонов делать.

чукча не читатель?

narkom

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

chel_1992

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

seregaohota

Не всё. Например, поставь обоих королей под бой и чтобы все соседние клетки были тоже атакованы.
Белые: Л a1,Л a2, Kр h1
Чёрные: Л g8,Л h8, Kр a8
Как такое в реальной партии могло получиться? Какой был последний ход? И чей?

chel_1992

ну все-таки это маленько не тот пример.
вряд ли короля можно ставить под бой.

a101

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

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

narkom

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

narkom

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

ARTi

здесь был написан бред по причине того, что я неправильно понял пост, на который отвечал

narkom

а я тут ответил, на твой пост Стер дабы не цитировать.

narkom

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

ARTi

речь плавно с выигрышной стратегии перекинулась на шахматы фишера
правила игры в шахматы фишера такие же, как в обычных, только начальная расстановка другая:
1) пешки стоят на своих местах, фигуры белые стоят на первой горизонтали, черные - на восьмой;
2) начальная позичия симметрична;
3) слоны не могут быть одноцветные;
4) ладьи стоят по разные стороны от короля;
5) там еще есть особое правило рокировки, но это неважно
(начальных расстановок, удовлетворяющих данным требованиям, около 960, так что если уж в обычных шахматах докопаются до выигрышных стратегий (в чем я сомневаюсь то здесь интерес останется )
PS гыгы

narkom

да я понял в чем суть шахмат Фишера, просто часть народу, в начале, включая меня поняли правила слегка по другому. Вот и правила Фишера порадили дисскуссию о несуществующей игре .

CokpaT

да я понял в чем суть шахмат Фишера, просто часть народу, в начале, включая меня поняли правила слегка по другому. Вот и правила Фишера порадили дисскуссию о несуществующей игре .
Да, про шахматы Фишера я тоже поняла.
Тогда я переформулирую свой вопрос, он не связан напрямую с Фишером.
Возмем произвольную расстановку фигур (без пешек такую, что слоны стоят на разноцветных клетках и кони тоже на разноцветных клетках (*). Может ли такая расстановка с какой-нибудь расстановкой пешек появиться в процессе игры?
Т.е. верно ли, что для любой "(*)-корректной" расстановки фигур найдется такая расстановка пешек (не обязательно всех 16 штук что такая позиция реально достигается?
upd прочитала тред более внимательно
К условию (*) добавим еще какие-нибудь требования вроде "не должно быть обоих королей под боем" или "ни один король" или даже вообще "ни одна фигура".

chel_1992

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

zuzaka

я пишу об обычных шахватах

chel_1992

отвечали после тебя, но не тебе. не обратила внимания, ясно

ARTi

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

narkom

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

chel_1992

доска бесконечная

chel_1992

я только такое смогла придумать

ARTi

пять баллов

chel_1992

двойной шах - это последнее, что может в голову придти
давай еще че-нить

chel_1992

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

ESCALADE

Доску нужно повернуть на 90 градусов по часовой стрелке?

a101



Доску нужно повернуть на 90 градусов по часовой стрелке?
Похоже. У меня тоже (?) без поворота ничего не получается

chel_1992

мне даже интересно стало, как получается, если доску на 90 градусов повернуть?
вообще говоря нет, не надо.

chel_1992

туплю, конечно надо
Оставить комментарий
Имя или ник:
Комментарий: