Поделюсь математическим результатом, поразившим меня в своё время до глубины души. Заодно затронем олимпиадную математику. Но начнём издалека.
Большинство читателей, наверное, помнят старый формат игры "Форт Боярд" (её перезапускали какое-то нереальное количество раз, может, она и до сих пор идёт). Если команда в течение дня не добывала нужного количества ключей, то ночью игроки спускались в тёмное подземелье, где люди в масках тигров пафосно играли с ними в простенькие игры. Большинство этих игр были не особо интеллектуальными: не утопи стаканчик, кинув туда очередную монетку, и т.п. Однако была игра вполне себе математического характера. Перед двумя игроками лежало 20 палочек. Каждый игрок в свой ход мог убрать со стола 1, 2 или 3 палочки. Проигравшим считался тот, кто вынужден был забрать себе последнюю палочку. Первым ходил игрок без маски (то есть один из главных героев передачи), и, будь это соревнование команд математиков, в этой игре люди-тигры проигрывали бы абсолютно всегда. Но увы.
На примере такой простенькой игры очень удобно смотреть на определённый тип математических игр, к которым относятся и шахматы (просто шахматы обладают намного менее тривиальным набором правил). Давайте научим первого игрока всегда выигрывать в игру с палочками.
В этой простой игре есть всего 21 возможная ситуация или, как принято говорить, позиция на доске. В начале хода игрока перед ним может лежать от 0 до 20 палочек. Разберёмся, что ему стоит делать в каждом конкретном случае.
Если перед игроком лежит 0 палочек и наступил его ход, то нужно праздновать победу, ибо последнюю палочку забрал противник. Математики говорят в таком случае, что 0 - выигрышная позиция.
Если перед игроком лежит одна палочка и наступил его ход, то нужно опечалиться, ибо по правилам игры он проиграл. Говорят, что 1 - проигрышная позиция.
Если перед игроком лежат две, три или четыре палочки, то правила игры уже не подсказывают ему, выиграл он или проиграл. А вот логика - подсказывает. Если он уберёт со стола 1, 2 или 3 палочки соответственно, то его противник окажется в проигрышной позиции с одной палочкой. А поскольку проигрыш противника означает выигрыш самого игрока, то мы можем уверенно констатировать, что 2, 3 и 4 - выигрышные позиции.
Пусть перед игроком лежат 5 палочек и наступил его ход. Рассмотрим варианты его действий. Он может забрать 1 палочку и оставить противнику выигрышную позицию 4. Может забрать 2 палочки и оставить противнику выигрышную позицию 3. Может забрать 3 палочки и оставить противника выигрышную позицию 2. А больше игрок ничего сделать не может. Обратите внимание, что после этого хода противник игрока окажется в выигрышной позиции в любом случае и помешать этому никак нельзя! А значит, 5 - проигрышная позиция. Если противник оставил Вам 5 палочек после своего хода, то дальше можно не играть! Всё равно он уже выиграл.
Едем дальше. Если на столе перед игроком лежит 6, 7 или 8 палочек, то он уже выиграл. Потому что может оставить своему противнику 5 палочек, а это будет означать проигрыш противника и выигрыш самого игрока. Позиции 6, 7 и 8 - выигрышные. Если же перед игроком лежат 9 палочек, то все его возможные ходы приведут к тому, что его противник окажется в выигрыше. А значит, 9 - проигрышная позиция. Если Вам оставили 9 палочек, дальше можно не играть.
Продолжая рассуждения аналогично, легко получить, что проигрышными позициями также являются 13 и 17. Позиция 20, которая является первоначальной позицией на доске, в свою очередь, является выигрышной, потому что взяв три палочки, первый игрок может загнать противника в заведомо проигрышную позицию с 17 палочками. Причём, обратите внимание, это важно: первый игрок может выиграть совершенно вне зависимости от действий второго! Если первый игрок сначала оставит противнику 17 палочек, затем 13, затем 9, затем 5, а затем 1, то второй никак не сможет ему помешать, как бы хорошо он ни играл. Всё что нужно сделать первому: определить, какие позиции являются выигрышными, а какие - проигрышными.
Заметим, кстати, что если бы люди-тигры любили своих игроков чуть меньше, то могли бы играть в эту игру не 20, а 21 палочкой. И тогда первый игрок заведомо находился бы в проигрышной позиции, а тигры могли бы все ключи оставлять себе. Однако ж вот какие они великодушные.
Постойте, скажет внимательный читатель. Одно дело - вытягивать палочки, это детская забава, которая действительно легко просчитывается. И совсем другое - шахматы, игра мудрых, сопровождающая человечество вот уже много лет! Разве можно их сравнивать?
Можно. Отличия между шахматами и игрой в палочки являются количественными, а не качественными.
В шахматах тоже есть позиции фигур на доске. И этих позиций конечное число! Да, безусловно, это число намного больше 21. Но оно всё равно конечное. А значит, теоретически мы можем выписать все эти позиции и для удобства соединить стрелочками те из них, которые переводятся друг в друга одним ходом.
Важное замечание состоит в том, что в понятие "позиция на доске" в случае шахмат включает в себя также пункты "чей ход" и "были ли сделаны рокировки". Но даже эти замечания не меняют того, что позиций конечное число. Просто это число ещё больше, чем могло показаться на первый взгляд.
Как же нам определить, какие из этих позиций являются выигрышными, а какие - нет? Заметим, что некоторая часть возможных в шахматах позиций представляют собой конец игры: кому-то в них поставлен мат или объявляется ничья. Для каждой из этих позиций очевидно, является она выигрышной, проигрышной или позицией ничьи для игрока, которому она досталась в начале хода.
А теперь сделаем вот что: посмотрим на все позиции, соединённые стрелочками с "конечными". При этом очевидно, что некоторые позиции могут переходить сразу в несколько конечных, их мы рассмотрим тоже. А вот позиции, стрелочки из которых ведут куда-то кроме конечных (даже если такая "неконечная" стрелочка всего одна!) пока рассматривать не будем. Какие есть варианты для таких "предпоследних" позиций?
Во-первых, хотя бы одна стрелочка в "предпоследней" позиции может вести в проигрышную конечную. И поскольку проигрыш противника означает выигрыш игрока, такие позиции мы смело объявляем выигрышными.
Во-вторых, стрелочек в "проигрыши" может не быть, однако присутствовать стрелочки в "ничьи". Тогда получается, что заставить противника проиграть игрок не может, но может всё свести в ничью. Такие позиции объявим ничейными.
И, наконец, в-третьих, все стрелочки "предпоследней" позиции могут вести исключительно к выигрышным позициям. В этом случае любой ход игрока приведёт к выигрышу его противника, то есть к проигрышу самого игрока. Такие позиции объявляем проигрышными.
И таким образом, мы разобрались с предпоследними позициями. Переходим к "пред-предпоследним" позициям, стрелочки из которых ведут только в уже подписанные ситуации. По алгоритму выше определяем и для них, какие являются проигрышными, какие выигрышными, а какие ничейными.
Продолжаем этот процесс, пока не переберём все позиции вообще и не дойдём до начальной. Если начальная позиция является выигрышной, то по-хорошему в шахматы должны всегда выигрывать белые. Если начальная позиция ничейная, то любая шахматная партия должна сводиться к ничьей. Если начальная позиция проигрышная, то в любой шахматной партии должны выигрывать чёрные.
Возникает закономерный вопрос: но почему тогда на практике бывает по-разному? Почему гроссмейстеры до сих пор не просчитали все позиции?
Ответ прост: позиций СЛИШКОМ много. Наш маленький человеческий мозг не может работать с такими большими числами. И даже наши супер-компьютеры всё ещё не могут работать с настолько большими числами. Поэтому все эти вычисления можно сделать теоретически, а на практике - пока нет. Пока мы ещё можем играть в шахматы. Хотя - совершенно объективно! - смысла в этом не больше, чем в перекладывании палочек.
