Сигнал и шум. Почему одни прогнозы сбываются, а другие - нет
Шрифт:
После второго хода каждой стороны количество возможных вариантов вырастает до 71 852; после третьего – до 9 132 484. Количество вариантов действий во всей шахматной партии, сыгранной до конца, настолько велико, что даже рассчитать его – немалая проблема, однако некоторые математики оценивают его в 10 10^50 степени. Это – астрономически огромные числа: как писал Диего Расскин-Гутман, «количество возможных вариантов шахматной партии превышает количество атомов во Вселенной» {623} .
623
Garry Kasparov, «The Chess Master and the Computer», New York Review of Books, February 11, 2010. http://www.nybooks.com/articles/archives/2010/feb/11/the-chess-master-and-the-computer/.
Может показаться, что в начале игры, когда все фигуры еще стоят на доске, а количество возможностей безгранично, компьютеры находятся на пике своих величайших возможностей. На сайте IBM перед матчем с Каспаровым было размещено хвастливое
«А Гарри Каспаров, к сожалению, может рассчитать всего около трех положений в секунду», – ехидно писалось в статье {624} . Были ли у Каспарова хоть какие-то шансы?
624
«Frequently Asked Questions: Deep Blue»; IBM Research via Internet Archive WayBack Machine beta. http://web.archive.org/web/20071028124110/http://www.research.ibm.com/deepblue/meet/html/d%20.3.3a.shtml#difficult.
Однако шахматным компьютерам многие годы не удавались удачные дебюты. Хотя количество возможностей и максимально, в этот момент цели выглядят наименее ясными. При наличии 10 в 10 10^50 ветвей на дереве игры [115] расчет 3 или 200 млн операций в секунду будет одинаково бесплодным, если только вы не направляете свою силу в одном, четко определенном направлении.
И компьютеры, и люди должны разбить шахматную партию на три промежуточные цели: допустим, захват пешки оппонента или шах королю. В середине игры, когда фигуры начинают прямое противостояние и угрожают друг другу, возникает огромное количество подобных стратегических целей. Достижение их требует разработки определенной тактики, и правильное прогнозирование может оказать самое сильное влияние на оставшуюся часть игры. Цели первых шагов сравнительно абстрактны. Компьютерам приходится сражаться с абстрактными и открытыми проблемами, а люди формулируют эвристические правила, такие как «контроль центра доски» и «сохранение нужной организации пешек», и формулируют неограниченное количество творческих способов по их исполнению.
115
Дерево игры (game tree) – способ описания игры с помощью графа «дерево», последовательно по ходам фиксирующего, какой информацией располагают игроки перед каждым ходом, какие варианты они могут выбирать.
Более того, поскольку первые ходы более привычны для игроков, чем позиции, с которыми они могут столкнуться позже, люди могут полагаться на многолетний опыт, позволяющий выбрать лучшие ходы. Хотя теоретически белые могут выбрать для начала игры 20 ходов, более чем 98 % серьезных шахматных партий начинаются с одного из четырех лучших {625} .
Проблема людей в том, что компьютерные программы могут систематизировать это знание путем изучения статистики. Шахматные базы данных содержат результаты сотен тысяч партий, и с помощью этих данных вполне можно сделать целый ряд глубоких выводов и прогнозов. Программисты IBM изучали, насколько часто разыгрывалась каждая последовательность первых ходов и насколько сильными были игроки, их разыгрывавшие. Они считали, насколько часто каждая серия шагов приводит к победам, поражениям и ничьим для сторон {626} . Эвристика компьютера, необходимая для анализа этой статистики, позволяла, в принципе, достаточно эффективно противостоять человеческой интуиции и опыту, а то и переигрывать их. «Каспаров играет не против компьютера, а против духов гроссмейстеров прошлого», – говорилось на сайте IBM при описании баз данных Deep Blue {627} .
625
Chess Opening Explorer, chessgames.com. http://www.chessgames.com/perl/explorer.
626
Murray Campbell, A. Joseph Hoane Jr., and Feng-hsiung Hsu, «Deep Blue», sjeng.org, August 1, 2001. http://sjeng.org/ftp/deepblue.pdf.
627
IBM Research, «Frequently Asked Questions: Deep Blue».
Таким образом, цель Каспарова в первой из шести игр матча против Deep Blue в 1997 г. состояла в том, чтобы извлечь программу из «страны баз данных» и заставить ее работать в условиях нулевой видимости». Он начал партию с довольно распространенного первого хода, переместив коня на клетку доски, известную игрокам под названием f3. Deep Blue ответил продвижением вперед слона, поставившего коня Каспарова под угрозу, – вне всякого сомнения, потому что его базы данных показали, что этот ход исторически снижал возможность выигрыша белых с 56 до 51 % [116] .
116
В этой книге выражением «процент выигрыша» обозначается количество очков, которые получает каждая сторона из возможного общего – одно очко дается за выигрыш партии, а половина – за ничью. Если вы играете 10 игр, выигрывая пять, сводя к ничьей три и проигрывая две, то ваш выигрыш составляет 65 %. – Прим. авт.
Однако эти базы данных строились вокруг предположения о том, что Каспаров должен был ответить на это тем же, что делают почти все другие игроки в такой ситуации {628} , то есть отодвинуть коня назад. Вместо этого он
Ход Каспарова, хотя и осмысленный со стратегической точки зрения, позволил добиться и еще одной цели. Он сделал всего три хода, а Deep Blue – всего два, однако позиция, к которой они пришли (рис. 9.2), ранее возникала в профессиональных соревнованиях всего один раз {630} из сотен тысяч игр, имеющихся в базе данных Deep Blue.
628
«1, Nf3 d5, 2. g3 Bg4» Chess Opening Explorer, chessgames.com. http://www.chessgames.com/perl/explorer?node=1959282&move=3&moves=Nf3.d5.g3.Bg4&nodes=74.77705.124843.1959282.
629
Обмен слона на коня в начале игры, который собирался сделать Deep Blue, может быть не особенно хорошим ходом, поскольку слоны более ценны в ситуациях, когда у игрока есть оба слона. Если у вас остается лишь один слон, то ваш оппонент может довольно безнаказанно ходить только по половине клеток, на которые этот оставшийся слон не может физически зайти. Иными словами, лучше иметь одного коня и двух слонов, чем двух коней и одного слона.
630
Position Search, chessgames.com. http://www.chessgames.com/perl/chess.pl?node=1967201.
Рис. 9.2. Расположение фигур после третьего хода Каспарова в первой партии
Даже когда разыгрываются популярные шахматные ходы, количество возможных ответвлений на дереве настолько велико, что базы данных становятся бесполезными примерно после 10–15 ходов. В любой достаточно длинной шахматной партии со временем вполне может возникнуть ситуации, с которой никогда не сталкивался никто из шахматистов в истории человечества. Однако Каспаров смог «отключить» базу данных после всего лишь трех ходов. Как мы постоянно видим в этой книге, исключительно статистические подходы к прогнозированию оказываются в лучшем случае неэффективными при отсутствии достаточной выборки данных для работы. Deep Blue пришлось «думать» за себя.
Дилемма шахматиста: ширина против глубины
Середина шахматной партии (обычно называемая миттельшпиль) потенциально позволяет использовать сильные стороны компьютера. Когда у фигур есть возможность сдвинуться в центр доски, то в среднем существует около 40 возможных ходов вместо 20 {631} . Это может показаться не особенно большой разницей, однако из-за того, что древо возможностей разрастается в геометрической прогрессии, количество возможных вариантов ходов быстро увеличивается. Предположим, например, что вы хотите рассчитать всего три следующих хода (точнее, по три хода ваших и вашего противника, то есть всего шесть ходов). В начале партии значение этой функции рассчитывается примерно как 20 в шестой степени – то есть существует 64 млн позиций, и это уже гигантское число. Однако в середине игры вам уже нужно рассчитать 40 в 50-й степени комбинаций, или 4,1 млрд возможностей. Deep Blue мог бы рассчитать все эти положения всего за 20 секунд. А Каспарову для этого потребовалось бы буквально 43 года, даже без перерывов на еду, сон или туалет.
631
Adriaan D. de Groot, Thought and Choice in Chess (Amsterdam, Holland: Amsterdam University Press, Amsterdam Academic Archive, 2008).
Великие игроки типа Каспарова не обманывают себя и не верят в то, что им под силу рассчитать все эти варианты. Именно это и отличает лучших игроков от любителей. В своем знаменитом исследовании шахматистов голландский психолог Адриаан де Гроот обнаружил, что любители при столкновении с шахматной проблемой часто начинают напряженно искать идеальный ход и в итоге не могут сделать ни одного {632} .
Мастера игры в шахматы, напротив, ищут хороший ход – и, по возможности, лучший ход в любой позиции, – однако они скорее прогнозируют, как этот ход изменит их положение, а не пытаются оценить любую возможность. Было бы «чистой фантазией», писал американский гроссмейстер Рейбен Файн {633} , предполагать, что люди-шахматисты заранее рассчитывают каждую позицию перед тем, как сделать 20 или 30 шагов.
632
Adriaan D. de Groot, Thought and Choice in Chess (Amsterdam, Holland: Amsterdam University Press, Amsterdam Academic Archive, 2008).
633
Shannon, «Programming a Computer for Playing Chess».
Но сказать, что «идеальное – враг хорошего», просто. Если вы хотите серьезно освоить такой вид искусства как шахматы, то порой вам нужно шагнуть за пределы простой эвристики. Тем не менее мы все равно неспособны создавать идеальные решения, когда нам поступает больше информации, чем мы можем обработать в ограниченный промежуток времени. Признавая свое несовершенство, мы обретаем свободу, что позволяет нам находить лучшие решения и в шахматах, и в других областях, вовлекающих прогнозирование.