x, y, z

Глава 1. Легенда о мудреце и электронные вычислительные машины / Математика на шахматной доске

Гик Е. Я.

Комментарии: 0
<<< |1|2|3|4|5|6|7|8|…|19| >>>

Глава 1. Легенда о мудреце и электронные вычислительные машины

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

Шахматы, как известно, одна из самых древних игр. Английский востоковед Г. Мэррей в своей «Истории шахмат» датирует возникновение игры V в. нашей эры. А совсем недавно в Узбекистане были обнаружены старинные шахматные фигуры, которые археологи относят ко II в. нашей эры. Поскольку шахматы имеют столь древнюю историю, не удивительно, что с ними связаны различные предания и легенды, правдивость которых за давностью времени, невозможно проверить. Вот старинная легенда об изобретателе шахмат.

Когда персидский шах (а в некоторых вариантах легенды - индийский царь) познакомился с шахматами, он был восхищен их остроумием и обилием возможных комбинаций. Узнав, что мудрец, который изобрел игру, является его подданным, шах позвал его, чтобы лично наградить за гениальную выдумку. Властелин пообещал выполнить любую просьбу мудреца и был удивлен его скромностью, когда тот пожелал получить в награду пшеничные зерна. На первое поле шахматной доски - одно зерно, на второе - два, и так далее - на каждое последующее вдвое больше зерен, чем на предыдущее. Персидский шах приказал побыстрее выдать изобретателю шахмат его ничтожную награду. Однако на следующий день придворные математики сообщили своему повелителю, что не в состоянии исполнить желание хитрого мудреца. Оказалось, что для этого не хватит пшеницы, хранящейся не только в амбарах персидского шаха, но и во всех амбарах мира. Мудрец скромно потребовал 1 + 2 + 22 + … + 263 = 264 - 1 зерен. Это фантастически большое число записывается двадцатью цифрами. Подсчет показывает, что амбар для хранения необходимого зерна (высотой 4 и шириной 20 метров) должен простираться от Земли до Солнца. Прямо скажем, связь с математикой здесь весьма условна, однако неожиданная развязка в истории с мудрецом и персидским шахом наглядно иллюстрирует грандиозные математические возможности, скрывающиеся в шахматной игре.

Другую «историческую» связь шахмат и математики представляет собой гипотеза, согласно которой шахматы произошли из магических квадратов. По-видимому, эта гипотеза впервые была высказана в прошлом веке английским математиком Кессоном, опубликовавшим несколько статей под названием «Магические квадраты Каиссы» (по имени шахматной музы Каиссы, героини одноименной поэмы У. Джонса). Позднее ее отстаивал также Н. Рудин2.

Магический (или волшебный) квадрат порядка n представляет собой квадратную таблицу n×n, заполненную всеми целыми числами от 1 до n² и обладающую следующим свойством: сумма чисел каждой строки, каждого столбца и двух главных диагоналей одна и та же. Для магических квадратов порядка 8 (а нас, естественно, интересуют только такие) эта сумма, как легко подсчитать, равна 260. На рис. 1 элементы (числа) магического квадрата расположены прямо на полях шахматной доски.

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

Рассмотрим одну из старинных дебютных табий (начальных расположений фигур) под названием «альмуджаннах». Она получается из современного начального положения при помощи следующих симметричных ходов белых и черных:
1. d2-d3 d7-d6
2. e2-e3 e7-e6
3. b2-b3 b7-b6
4. g2-g3 g7-g6
5. c2-c3 c7-c6
6. f2-f3 f7-f6
7. c3-c4 c6-c5
8. f3-f4 f6-f5
9. Кb1-c3 Кb8-c6
10. Кg1-f3 Кg8-f6
11. Лa1-b1 Лa8-b8
12. Лh1-g1 Лh8-g8
(рис. 1).

 
64
63
3
4
5
6
58
 
57
56
 
55
 
11
 
12
 
13
 
14
 
50
49
 
17
18
46
45
44
43
23
 
24
 
25
 
26
38
 
37
36
 
35
 
31
 
32
 
33
 
34
30
 
29
28
 
27
 
39
 
40
 
41
42
22
21
20
19
47
 
48
16
 
15
 
51
 
52
 
53
 
54
 
10
9
 
8
7
59
60
61
62
2
 
1
Рис. 1. Альмуджаннах и магический квадрат

Подсчитав сумму чисел, стоящих на восьми полях: d2, d3, e2, e3, d6, d7, e6, e7, участвующих в первых двух ходах, неожиданно мы получим магическое число 260. То же число будет получаться и для каждой последующей пары приведенных ходов. Основываясь на подобного рода примерах (число их можно увеличить), Рудин и строит свою гипотезу о связи магических квадратов с шахматами. А исчезновение всех следов такой связи он объясняет тем, что в ту далекую эпоху суеверий и мистики древние индусы и арабы приписывали числовым сочетаниям магических квадратов таинственные свойства, и поэтому квадраты тщательно скрывались, как и все с ними связанное.

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

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

Программированием шахматной игры на ЭВМ всерьез занимаются многие коллективы математиков, создано большое число различных программ. В 1967 г. состоялся исторический «машинный» матч СССР - США, в котором со счетом 3:1 победила советская программа. В ее создании участвовали математики Г. Адельсон-Вельский, В. Арлазаров, А. Битман, А. Животовский и А. Усков4. В дальнейшем к ним присоединились также математики А. Бараев и М. Донской5. Позднее этой программе было дано романтическое имя «Каисса» (в честь богини шахмат Каиссы). С каждым годом «Каисса» улучшает свою игру. Так, в 1972 г. в матче с читателями «Комсомольской правды» из двух партий одну ей удалось свести вничью. Ниже мы еще расскажем об одном выдающемся успехе «Каиссы». Интересно, что кандидатская диссертация В. Арлазарова (заведующего лабораторией Института проблем управления, в которой рождена «Каисса») так и называется - «Некоторые вопросы программирования шахматной игры»!

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

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

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

Число возможных шахматных позиций хотя и фантастически велико, но конечно. Верхние оценки для него получены в различной литературе. Грубую оценку найти несложно, покажем это. Данное поле доски может быть занято одной из шести фигур белых или черных или может быть свободно. Таким образом, всего для поля имеется 13 возможностей. Поскольку на доске 64 поля, то возможных шахматных позиций не более 1364. Конечно, здесь учтено множество заведомо не существующих позиций, например с числом фигур, большим 32. Можно различным образом уточнять оценку, но сейчас нас интересует лишь сам факт ее существования.

Из конечности числа шахматных позиций следует, что, перебрав все варианты на необходимую глубину, про каждую позицию, в том числе исходную, можно установить, ничейна она или является выигранной для одной из сторон8 (теоретический алгоритм для такого «присуждения» позиций описан, например, Н. Криницким во введениях к упомянутым ниже книгам М. Ботвинника). Впрочем, осуществить такой эксперимент (например, для начальной позиции) практически невозможно. Известно, что если бы все человечество со времен Адама и Евы только тем и занималось, что играло в шахматы, то и тогда бы все позиции (и партии) еще до сих пор не были исчерпаны…

Принципы шахматных программ для ЭВМ впервые были сформулированы в начале 50-х годов известным американским кибернетиком К. Шенноном9. Прежде всего, вводится так называемая оценочная функция, сопоставляющая каждой позиции определенное число (оценку). Можно, например, сложить силы белых и черных фигур (по одной из шкал, указанных в главе 10) и в качестве оценки позиции взять разность между полученными суммами. Просмотрев все варианты на заданную глубину, машина выбирает ход, ведущий к позиции с максимальной оценкой.

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

Основной путь улучшения игры машины заключается в приближении ее к принципам игры шахматиста, который, как известно, рассматривает лишь небольшое число вариантов, уделяя максимум внимания лучшим, с его точки зрения, продолжениям. При этом он часто оценивает позицию из общих соображений, полагаясь на собственный опыт и интуицию. Цель эвристического программирования как раз и состоит в том, чтобы вместо полного перебора вариантов научить машину ограничиваться наиболее перспективными (как в шахматной игре, так и при решении других сложных и важных задач). В этом направлении главным образом и ведутся исследования современных математиков. Так, «Каисса» во многих ситуациях уже отказывается от полного перебора вариантов. Идея сокращения перебора лежит и в основе «метода горизонта», предложенного М. Ботвинником10. Заметим, что любой метод сокращения перебора в шахматных программах, по существу, является методом направленного поиска, широко используемого в прикладной математике.

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

Примечательным событием в истории шахмат и математики явился первый чемпионат мира по шахматам среди вычислительных машин, состоявшийся в 1974 г. в Стокгольме под эгидой Международной федерации по обработке информации (ИФИП). Этот чемпионат был приурочен к 25-летию работ в области шахматного программирования. И первой чемпионкой мира среди компьютеров стала советская программа «Каисса»! Она оказалась сильнее 12 программ, «приехавших» из США, Канады, Австрии и других стран.

Поскольку наша книга - не учебник шахматной игры, в ней не приводится ни одной «человеческой» партии. Однако думаем, что с одной из партий ЭВМ читатель ознакомится с интересом (хотя «Каисса» играет пока в лучшем случае в силу третьего разряда). Прокомментируем кратко заключительную, решающую победу «Каиссы» на чемпионате мира11.

«Острич» (США) - «Каисса» (СССР)
Дебют ферзевых пешек

1. Кg1-f3 e7-e6
2. d2-d4 Кg8-f6
3. Сc1-g5 d7-d5
4. e2-e3 Сf8-e7
5. Кb1-c3.
Неожиданный для «Каиссы» ход, она готовилась к 5. c4.
5. … Сe7-b4
? Не совсем логично.
6. Сg5:f6 Сb4:c3+
7. b2:c3 Фd8:f6
8. Сf1-d3 c7-c5
9. 0-0 0-0
10. Фd1-d2 Кb8-c6
11. d4:c5 Фf6-e7
12. c3-c4 d5:c4
13. Сd3:c4 Фe7:c5
14. Фd2-d3 Лf8-d8.
Лучше было 14. … b6, заканчивая развитие фигур. Теперь черные начинают испытывать некоторые затруднения.
15. Фd3-e4 b7-b5
16. Сc4-d3 f7-f5
17. Фe4-h4 e6-e5.
Активные ходы пешками не приводят к добру. 18. e3-e4? «Острич» боится вилки, между тем 18. a4! e4 (если 18. … bа или b4, то 19. Сc4+ Крh8 20. Кg5) 19. C:b5 ef 20. С:c6 сразу решало исход борьбы.
18. … f5-f4
19. Лf1-e1 Сc8-b7
? После 19. … h6 позиция черных была вполне надежна, однако зевают не только люди, но и машины!
20. Кf3-g5 h7-h6
21. Кg5-e6 Фc5-b6
22. Кe6:d8 Лa8:d8
23. a2-a4 b5-b4
24. Сd3-c4+ Крg8-h8
25. Лa1-d1 Кc6-d4
26. Лd1-c1
? Выигрывало 26. Фe7 Лc8 27. Сb3, после чего теряется одна из пешек b4 или e5, а взятие конем на b3 или c2 невозможно из-за 28. Лd7. «Каисса» снова выходит сухой из воды.
26. … Сb7-c6
27. c2-c3 b4:c3
28. Лc1:c3 Сc6:a4
29. Фh4-e7 Кd4-c6
30. Фe7-f7 Фb6-c5
31. Лc3-d3 Кc6-d4
32. Сc4-d5.
Здесь «Каисса» могла форсировать ничью изящной комбинацией: 32. … Кe2+! 33. Крf1 Сb5 34. Лd2 Кg3+ 35. Крg1 Кe2+ с вечным шахом. Перестановка ходов снова ставит черных на грань поражения.
32. … Сa4-b5
33. Лd3-h3 Кd4-e2+
34. Крg1-h1 Фc5:f2.
Белые могли объявить форсированный мат: 35. Л:h6+ gh 36. Фf6+ Крh7 37. Фe7+ Крg6 38. Фf7+ Крg5 39. Фg7+ Крh5 40. Сf7+ Крh4 41. Ф:h6+ Крg4 42. Сe6 мат, но, к счастью, машина так далеко не считает…
35. Лe1-d1 Фf2-b6
36. Лd1-b1 Лd8-c8
37. Сd5-e6 Лc8-d8.
Снова «Каисса» упускает возможность нанести эффектный удар: 37. …Сd7!, и белые вынуждены дать вечный шах после 38. Л:h6+.
38. Фf7-g6! Фb6-b7
39. Фg6-f5.
В этот момент «Острич» находился в цейтноте, иначе он наверняка бы нашел простой выигрыш: 39. Л:h6+ gh 40. Ф:h6+ Фh7 41. Фf6+.
39. … Фb7-c7
40. Лh3-h4 Кe2-d4
41. Фf5-h3 Кd4:e6
42. Фh3:e6 Сb5-d3
43. Лb1-g1 Сd3-c4
? Пути электронного мозга неисповедимы, почему не 43. … С:e4?
44. Фe6-f5 Сc4-e2
45. Лg1-a1 a7-a5
46. Фf5-g6 a5-a4!
«Остричу» давно следовало подключить к игре ладью h4, «Каисса» пользуется растерянностью соперника и получает решающий перевес.
47. Лa1-e1 Сe2-c4
48. Лe1-a1 a4-a3!
49. Лa1-b1 Фc7-d6
50. Фg6:d6 Лd8:d6
51. Лh4-h3 a3-a2
52. Лb1-c1 Лd6-d4
53. Лh3-c3 Лd4:e4
54. Лc1-a1 Лe4-d4
55. Лc3:c4.
Жертва отчаяния.
55. … Лd4:c4
56. g2-g3 f4-f3
57. h2-h3 Лc4-c2
, и через десять ходов «Каисса» объявила мат.

В свое время «отец кибернетики» Н. Винер довольно пессимистически оценивал шахматные шерспективы ЭВМ. Надо признать, что и сегодня машины еще не в состоянии всерьез конкурировать с шахматными мастерами (приведенная партия лишний раз убеждает нас в этом). И если настоящий шахматный матч между гроссмейстером и машиной когда-нибудь и состоится, то это дело далекого будущего. В некоторых же вопросах машина уже сегодня может оказать помощь шахматистам. Известно, например, что в наш век научно-технической революции актуальной является проблема переработки и хранения информации, объем которой угрожающе растет. Этш проблема достаточно остро ощущается и в шахматах - тем более, что число крупных турниров с каждым годом увеличивается. Гроссмейстеры и мастера уже просто фшзически не успевают проанализировать все интересующие их партии и дебютные варианты. Создание информационно-поисковой системы на базе ЭВМ могло бы значительно облегчить эту работу, особенно при подготовке к ответственным соревнованиям.

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



2. Я. Рудин. От магического квадрата к шахматам. М., «Просвещение», 1969.

3. Точнее было бы говорить об «игре программ», а не об «игре машин» (на одной машине могут играть друг с другом две программы!); мы пользуемся обоими общепринятыми выражениями.

4. Основные идеи программы авторы изложили в фундаментальной работе «О программировании игры вычислительных машин в шахматы» («Успехи матем. наук», 1970, 25, № 2).

5. Некоторые результаты, полученные создателями «Каиссы» в последние годы, содержатся в сборнике «Проблемы кибернетики (М., «Наука», 1974, вып. 29). В частности, в статье М. Донского «О программе, играющей в шахматы» изложены новые идеи шахматного программирования.

6. Специальная статья на эту тему «Шахматы и теория игр» опубликована К. Винкельбауэром в «Probl. kybernetiky» (Praha, 1965).

7. Частично соображения В. Гурария содержатся в статье «Наука и шахматы» («Шахматы», 1973, № 22, 24; 1974, № 4).

8. Строгое доказательство этого факта впервые было дано Э. Цермело в 1911 г. (см.: Э. Цермело. «О применении теории множеств к теории шахматной игры». - В сб.: «Матричные игры». М., Физматгиз, 1961).

9. К. Шеннон. Работы по теории информации и кибернетике. М., ИЛ, 1963.

10. М. Ботвинник. Алгоритм игры в шахматы. М., «Наука», 1968; М. Ботвинник. О кибернетической цели игры. М., «Советское радио», 1975.

11. Подробно о чемпионате рассказывается в статьях М. Донского «Чемпионат мира среди шахматных программ» («Квант», № 12, 1974) и В. Хенкина «"Каисса" - чемпион мира» («Наука и жизнь», № 1, 1975).

<<< |1|2|3|4|5|6|7|8|…|19| >>>
Комментарии: 0