Теория шахматной доски

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

Одним из создателей методов математического анализа является Леонард Эйлер. Наряду со строгими математическими доказательствами Эйлер использовал эмпирические методы и “правдоподобные” рассуждения. Развитие методов математического анализа в значительной степени проводилось Эйлером с целью решения конкретных математических и прикладных задач. Работы Эйлера внесли большой вклад в разные области математики, в том числе и в комбинаторику. Комбинаторные результаты Леонарда Эйлера, лежащие несколько в стороне от основной массы его работ, позволяют лучше оценить как разносторонность его дарования, так и склонность к использованию аналитических методов.

В работе, представленной к публикации в 1759 г. и опубликованной в 1766 г. , Леонард Эйлер рассмотрел задачи построения обходов шахматной доски (и ее обобщений) шахматным конем, которые являются частными случаями задачи о гамильтоновых путях. Это была первая серьезная математическая статья, посвященная способам построения обходов квадратных и прямоугольных досок ходом шахматного коня; она определила характер дальнейших исследований в этой области “занимательной математики”. Эйлер построил замкнутый обход шахматной доски (доказав тем самым, что обход можно начинать с любой клетки) и указал способы преобразования и построения обходов и привел разнообразные примеры обходов (как замкнутых, так и не замкнутых, в том числе обладающих различными свойствами симметрии). Кроме того, Эйлер рассмотрел задачи об обходе конем досок, имеющих другие размеры и формы. В частности, он: а) отметил, что не существует обходов досок размеров 3 × 3 и 4 × 4 и привел пример обхода конем всех клеток доски 4 × 4, кроме одной угловой клетки; б) заметил, что не существует замкнутых обходов досок с нечетным числом клеток, показал, что любой обход доски размером 5×5 должен начинаться или заканчиваться в угловой клетке, и, соединив обходы досок 5 × 5, построил симметричный обход доски 10 × 10; в) построил (незамкнутые) обходы досок размером 3×4 и 3×7, отметил, что доски размером 3×5 и 3×6 обойти ходом шахматного коня нельзя, и высказал гипотезу о том, что не существует замкнутых обходов досок, у которых хотя бы одна из сторон короче 5 клеток; г) построил примеры обходов досок крестообразной формы.

Гипотеза Эйлера была опровергнута только в 1917 г. , когда Е. Бергхольт в письмах в «The British Chess Magazine» привел примеры замкнутых обходов досок размером 3 × 10 и 3 × 12.

Компьютерные шахматы

Вклад учёных и шахматистов в развитие шахматной математики

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

Задачи о шахматной доске, на которой не все поля принимаются во внимание, для учёных представляют собой алгоритмический интерес к игре, поскольку они определяют поля внимания играющего при принятии решения о ходе, который он намерен сделать. Кроме того, вследствие изменения количества полей и формы шахматной доски появляются новые разновидности игры, например шахматы, предложенные Робертом Фишером. Он в 1996 году представил публике разработанные им случайные шахматы Фишера — вариант шахмат, в которых правила игры обычны, но начальная расстановка фигур случайным образом выбирается из 960 вариантов. Большое количество начальных позиций в этой игре делает бесполезным накопленный шахматной теорией массив глубоко изученных дебютов и «домашних заготовок», что заставляет игрока с первых ходов не играть по заученному шаблону, а всерьёз анализировать позицию.

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

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

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

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

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

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

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

В 1948 году Клод Шеннон публикует работу “Программирование компьютера для игры в шахматы”. Ранее подобных публикаций на эту тему не было, причем созданная Шенноном шахматная программа явилась основой для последующих разработок и первым достижением в области искусственного интеллекта. В 1950 году он изобрел механическую мышь Тесей, которая, будучи управляема магнитом и сложной электрической схемой, скрытой под полом, мог ла найти выход из лабиринта. Он построил машину, “читающую мысли” и играющую в “монетку” — игру, в которой один из играющих пытается угадать, что выбрал другой играющий, “орел” или “решку”. Коллега Шеннона, также работавший в Bell Laboratories, Дэвид Хейджелбарджер построил опытный образец; машина за поминала и анализировала последовательность прошлых выборов оппонента, пытаясь отыскать в них закономерность и на ее основе предсказать следующий выбор.

В истории шахмат с именем Ботвинник связана целая эпоха. Он первым утвердил приоритет советской шахматной школы в мировых шахматах. Его игру отличали глубокие стратегические замыслы, неожиданные тактические удары, постоянное стремление к инициативе, к созданию цельных партий. Он первым уделил особое внимание вопросам тренировки шахматистов, создал свой метод подготовки к соревнованиям. Внёс ценный вклад в теорию многочисленных начал, разработал ряд оригинальных дебютных систем (например, Ботвинника вариант в ферзевом гамбите). Обогатил теорию эндшпиля (особенно ладейных окончаний) ценными анализами. В области шахматной композиций идеи этюдов Ботвинник заимствовал из практических партий. После 1963 г. Ботвинник начал им работу по составлению шахматной программы для ЭВМ. В 1966 г. появились его первые статьи на эту тему, а два года спустя в издательстве «Наука» вышла книга «Алгоритм игры в шахматы». Алгоритм игры в шахматы, разработанный Ботвинником, как предполагается, моделирует мышление шахматиста.

1. 2. 2 Суперкомпьютер и его роль

Следующим шагом было создание компьютеров специально для шахмат, позволяющих совершать большое количество операций в секунду. Первый такой компьютер был создан в лаборатории Белл Кеном Томпсоном, он производил 180000 операций в секунду (обычные компьютеры – лишь 5000) и просчитывал позицию на 8-9 полуходов, что соответствовало уровню мастера. Этот компьютер победил Всемирном шахматном турнире компьютеров, и во многих других турнирах в начале 80-х, но уступил новому гораздо более мощному Cray X_MPs. Компьютер Томпсона был усовершенствован, но так и не смог победить лидера. Далее появились Chip Test и Deep Thought, способные считать 500 000 операций в секунду. DT сыграл две партии с действующим чемпионом мира Каспаровым и проиграл обе, зато одержал победу над несколькими гроссмейстерами.

Этой разработкой заинтересовались представители IBM, и работа продолжилась – был создан знаменитый Deep Blue, победивший на турнире компьютеров, и выигравший у сильнейшей шахматистки мира – Юдит Полгар. Одновременно проводился блицтурнир с участием программы Fritz, поделившей первое место с Каспаровым, и уступившей ему лишь в дополнительном матче.

В 1996 году состоялся первый матч Deep Blue с Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-ти процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста со счетом 3. 5:2. 5. В то время компьютер не умел оценивать позицию и строить игру на основании этой оценки. Рост силы игры достигался исключительно за счет увеличения мощности компьютера. Даже алгоритм перебора все еще использовался "брутфорс", то есть перебирались все варианты, но очень быстро.

Суперкомпьютер – вещь штучная, рядовому пользователю недоступная. Дальнейшее развитие было связано с улучшением алгоритмов и снижением требований к аппаратной части, тем более, что и персональные компьютеры все это время не стояли на месте. В матче с Крамником играл Deep Fritz на двухпроцессорном сервере Compaq ProLiant DL760 на процессорах Xeon и RAM 2-16Гб. Такой компьютер, конечно, рядовому пользователю еще недоступен, но все же он выпускается серийно. Матч закончился вничью со счетом 4:4.

В 2003 году состоялся еще один матч Каспарова против компьютера – с Deep Junior, работавшем на 4х-процессорной системе с процессорами Pentium IV 1. 9 ГГц и 3 Гб оперативной памяти. Junior – первая программа, демонстрирующая "человечную" игру, и способная пойти на жертву ради инициативы. Матч закончился вничью. В следующем матче Каспаров играл на виртуальной трехмерной доске в 3D-очках, делая ходы при помощи голосовых команд. Этот матч также закончился вничью.

Было бы странно не использовать накопленный людьми опыт. Создание дебютных баз позволило вообще не считать позицию первые 20-25 ходов, а пользоваться готовыми наработками. Но и опыт компьютеров также пригодился: начиная с 1980-х годов Кен Томпсон стал создавать базу 4-х и 5-ти фигурных эндшпильных окончаний. Теперь компьютеру не надо считать по новой – можно использовать существующие наработки. Эндшпильные базы постоянно дорабатываются и пополняются, в ход пошли уже 6-7-фигурные эндшпили.

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

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

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

Чем отличается игра компьютера? В первую очередь, надежностью. Программа строго следует алгоритму и неспособна на авантюры. Логика игры не соответствует человеческой, например, в одной из партий компьютер предпочел мат в пять ходов с жертвой ладьи взятию ферзя в один ход, хотя большинство шахматистов выбрали бы второй вариант – ведь с лишним ферзем сложно не выиграть. Компьютер опирается на базы, поэтому найденная дебютная новинка или просто нестандартный, пусть и слабый, ход – это шанс в борьбе с ним. В 5-6, и частично в 7-фигурном эндшпиле программа заведомо будет играть идеально, без ошибок. А вот при большем количестве фигур возможности живого игрока возрастают.

При переборе позиций на некоторую глубину, компьютер их оценивает, и в конечном итоге выбирает вариант, в котором получит преимущество. Как производится оценка? По формальным факторам, выраженным в условных пешках. Оценивается непосредственно наличие фигур, их активность, расположение пешек: изолированные, сдвоенные, проходные, отсталые, контроль полей в центре и вблизи короля и т. д. Чем точнее модель оценки позиции, тем лучше программа владеет позиционной игрой, но поскольку модель жестко задана, то именно здесь компьютер легче всего "подловить" – например, программа неуверенно ведет себя в закрытых позициях. Ну и главное "оружие" человека – это нестандартность мышления. "Антикомпьютерные шахматы" повысили шансы гроссмейстеров в игре с искусственным интеллектом. Но выявление слабостей немедленно привело к работе по их устранению.

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

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

1. 3 Вывод

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

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

Глава 2. Шахматные головоломки

2. 1 Решение задач путём логических умозаключений

2. 1. 1 Награда за игру в шахматы

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

Когда индийский царь впервые познакомился с шахматами, он восхитился их своеобразием и обилием красивых комбинаций, Узнав, что замечательную игру изобрёл его подданный, царь призвал к себе мудреца, желая лично наградить за выдумку. Властелин обещал выполнить любую его просьбу и был удивлён, что тот желал получить в награду лишь некоторое количество пшеничных зёрен. На первое поле он попросил выложить одно зерно, на второе – два и так далее: на каждое последующее поле нужно было класть больше зёрен, чем на предыдущее. Царь распорядился быстрее выдать изобретателю его ничтожную награду. Однако на следующий день придворные повелители сообщили своему повелителю, что для выполнения его приказа не хватит пшеницы, хранившейся только в амбарах всего царства, но и во всех амбарах мира. Мудрец скромно потребовал зерно (18446744073709551615 зерно). Это число записывается двадцатью цифрами и фантастически велико.

2. 1. 2 Доказательство теоремы Пифагора

Шахматный король гроссмейстер Михаил Таль однажды признался, что в детстве был потрясён доказательством теоремы, которую нерадивые школьники произносят так: «Пифагоровы штаны на все стороны равны».

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

2. 1. 3 Головоломка с домино

Удастся ли плотно покрыть костями домино размеров 2х1 доску 8х8 квадратов, из которой вырезаны противоположные угловые квадраты?

Можно было бы заняться алгебраическими рассуждениями, но шахматное решение и проще, и изящнее. Окрасим урезанный квадрата черными и белыми цветами, превратив его в шахматную доску без угловых полей a1 и h8. При искомом покрытии доски каждая кость домино занимает одно белое и одно чёрное поле, и, значит, весь набор костей (31 штука) покрывает одинаковое число белых и чёрных полей. Но на урезанной доске чёрных полей на два меньше, чем белых (вырезанные поля чёрные), и, следовательно, необходимого покрытия доски не существует.

Итак, раскраска доски не только помогает шахматисту ориентироваться на ней во время игры, но и позволяет решать необычные математические головоломки. «Красиво, ничего не скажешь!» - воскликнул чемпион мира по шахматам Гарри Каспаров, когда познакомился с решением задачи.

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

2. 1. 4 Ничья

Рассмотрим знаменитый этюд Рети 1921 г. , где свойство доски проявляется особенно эффективно. На первый взгляд, задание невыполнимо: догнать чёрную пешку белым королём не представляется возможным (1. Крh7 h4 2. Крh6 h3 и т.  д. ); чёрный же король может легко задержать белую пешку, если та двинется вперёд.

Однако белый король совершает весьма неожиданный и парадоксальный манёвр:

1. Крg7! h4

2. Крf6 Крb6 (после 2h3 3. Крe7 h2 4. c7 Крb7 5. Крd7 пешки становятся ферзями одновременно

3. Крe5! Теперь после 3Кр:c6 4. Крf4 белый король попадает в квадрат пешки и задерживает её, а если 3h3, то после

4. Крd6 вновь пешки одновременно проходят в ферзи, в обоих случаях — ничья. Король догнал пешку на пороге её превращения. Невероятное стало очевидным.

Понятно, что с «точки зрения» белого короля, сумма катетов прямоугольного треугольника, изображённого на рис. 5, равна гипотенузе! Этот этюд произвёл сильное впечатление на современников, а осуществлённый в нём манёвр короля получил название «манёвр Рети» и затем неоднократно применялся другими авторами. В своё время вызвал настоящую сенсацию в шахматном мире. По чистоте формы и лаконичности материала превзойти этот геометрический шедевр невозможно.

2. 1. 5 Конь Аттилы

На доске находятся две фигуры – белый конь и чёрный король. Некоторые поля объявляются «горящими». Конь должен пройти до неприятельского короля, подвергнуть его и вернуться в исходное положение. Ему запрещено занимать как «горящие» поля, так и поля, уже пройденный им однажды.

«Трава не растёт, там где не ступил мой конь!» - похвалялся вождь гуннов Аттила, когда хотел сказать, что его полчища уничтожают всё живое на своём пути. На рис. 6 конь Аттилы расположен на g4, а неприятельский король – на b3. Горящие поля выделены.

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

Методы решения подобных задач, называемыми лабиринтами, хорошо известны в теории графов. Впрочем, для коня Аттилы искомый путь нетрудно найти и непосредственно. Он содержит 18 ходов: Kg4-f6-e8-f7-e6-f8-g6-e7-c6-a5:b3-d2-b1-a3-b5-d6-f7-h6-g4. Для достижения цели коню пришлось побывать на 18 полях из 35, не сожженных в начале сражения.

2. 1. 6 Задача о ферзях-часовых

В книгах по занимательной математике встречается множество задач о маршрутах шахматных фигур – не только коня, но и слона, ладьи, короля, ферзя. Например, доказано, что ферзь может обойти всю доску за 15 ходов. если при этом разрешить ферзю пробегать мимо полей дважды, то один ход можно сэкономить. Итак, кратчайший маршрут ферзя состоит из 14 ходов.

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

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

Оказывается, 5 ферзей вполне справляются со всей шахматной «тюрьмой». Кроме того, доказано, что 8 ладей, или 8 слонов, или 9 королей, или 12 коне также способны контролировать все свободные поля доски. Интересно, что на досках произвольного размера nxn решение найдено далеко не во всех случаях.

2. 1. 7 Старинная головоломка

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

Эту головоломку придумал итальянец Гуарини еще в XVI в. Она нередко встречается в книгах по занимательной математике. В углах доски размером 3х3 стоят два белых и два чёрных коня. Требуется поменять местами белых и чёрных коней за наименьшее число ходов.

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

Теперь задача решается почти автоматически. Выбрав одно из направлений движения по кругу, будем переставлять коней до тех пор, пока они не поменяются местами. Чтобы переместить коней на доске, нужно заменить пуговицы соответствующими полями. Нетрудно убедиться, что перемещение состоит из 16 перемещений коней (восьми белых и восьми чёрных), причём кони противоположного цвета могут ходить по очереди. Если дополнительно потребовать, чтобы кони разного цвета не угрожали друг другу (очередность ходов в этом случае позволяется нарушать), то необходимо только следить за тем, чтобы белые и чёрный кони не оказались соседями в клубке. Если круговое движение (против часовой стрелки ) начинает белый конь a1. То решение будет такое: Ka1-b3, Ka3-c2, Kc3-b1-a3, Kc1-a2-c3, Kb3-c1-a2, Kc2-a1-b3, Ka3-c2-a1, Kc3-b1-a3, Ka2-c3, Kb3-c1.

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

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

В заключение приведём ещё одну задачу о перестановке фигур, придуманную гроссмейстером Сэмом Лойдом.

Требуется за наименьшее число ходов переставить четырёх белых коней с ферзёвого фланга на королевский (с вертикалей a, b, c, d на е, f, g и h), а трёх чёрных –с королевского на ферзёвый (с вертикалей f, g, h на a, b и c). Короче говоря, кони должны поменяться флангами – «берегами реки Дунай». Соблюдать очередность ходов не нужно, но коням запрещено отступать (белым – влево, чёрным - вправо). Кроме того, на каждой вертикали может находиться только один конь.

Эту головоломку Лойд считал одной из самых трудных и весьма гордился тем, что мало кому из друзей удавалось перебросить коней «через Дунай» (вертикаль e). Цель достигается за 19 ходов, причём при переводе на язык теории графов задание становится совсем простым.

Задача может быть решена и при помощи «метода пуговиц и нитей». Поскольку безразлично, на какую половину доски, верхнюю или нижнюю, попадают кони, в решении достаточно указать только вертикали доски. Итак, кони отправляются в плавание: de, fd, gf, eg, ce, bc, db, fd, hf, gh, eg, ce, ac, ba, db, fd, ef, ce, dc. Река Дунай покорена!

2. 2 Решение задач компьютером

2. 2. 1 Задача о восьми ферзях

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

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

А вот одна необычная игра, которая имеет прямое отношение к той же задаче. Двое игроков по очереди ставят ферзей на вертикали a, b, c и т. д. , приём ферзи не должны нападать друг на друга. Проигрывает тот, кто не в состоянии сделать очередной ход – на доске уже стоят 8 ферзей и нельзя поставить нового ферзя без нарушения указанного условия.

На рис. в белые выиграли: все поля вертикали f под контролем ферзей, и у чёрных нет хода. А положении на рис. г победа на стороне чёрных: на вертикали e нет ни одного поля для белого ферзя.

Есть и другой вариант той же игры: тот, кто делает последний ход, выигрывает столько очков, сколько ещё осталось на доске свободных вертикалей. Тогда в первом примере белые выиграли три очка, а во втором чёрные – четыре очка.

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

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

2. 2. 2 Путешествие коня по шахматной доске (1)

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

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

Ещё с середины XIX в. известно правило Варнсдорфа: чтобы конь обошёл доску, при каждом ходе его следует становить на поле, с которого он может сделать наименьшее число «прыжков» на еще не пройденные им поля. Если таких вариантов полей несколько, то выбирают любое из них.

Более 150 лет правило Варнсдорфа считают безукоризненным. Однако машинный эксперимент, проведены уже в наше время, показал: произвольное применение второй части правила иногда заводит коня в тупик. Последовательно нумеруя поля, посещаемые конём, мы видим, что, начав маршрут с поля b7, он сделал 55 ходов, добрался до b8, а далее двинуться не может. Согласно правилу Варнсдорфа, конь вынужден был пойти с d7 на b8 (номер 56), поскольку именно на b8 он обладает наименьшими возможностями для перемещений: из число равно 0. В результате часть полей – a8, b6, c7, d5, e8, f4, h5 – осталась непройденной.

Конечно, компьютер в данном случае не опроверг правило Варнсдорфа, а лишь уточнил его. Просто показалось, что второй частью правила нужно пользоваться аккуратнее. С поля b4 конь мог пойти на a6 и d5, но такой же выбор был у него и на поле f4 – на d5 и h5. Последний ход и надо было предпочесть. Тогда конь легко завершал искомый маршрут: сначала посещал все ранее не пройденные поля: Kf4-h5-f6-e8-c7-a8-b6-d5, а затем поля 52-56 прежнего маршрута: Kd5-b4-a6-b8-d7-c5. В итоге на доске не оставалось ни одного поля, на котором не побывал конь, причём ровно по одному разу.

2. 2. 3 Путешествие коня по шахматной доске (2)

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

Не у каждого хватит терпения возится с этой головоломкой. Другое дело – машина. Именно она и нашла рекордный путь, состоящий из 35 ходов. Любой следующий ход ведёт к самопересечению графика.

Заключение

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

Шахматы являются многофункциональной игрой. Прежде всего, эта игра развивает логическое мышление. Благодаря шахматам человек может необычным способом решать множество полезных задач, а также продумывать последовательность ходов для получения лучшего результата игры. Множество учёных, такие как Эйлер, Гуарини, Гаусс, а также шахматисты Рети и Лойд нашли интересные решения различных головоломок.

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

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

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