Информатика. 3–4 класс (часть 3) Демо+методичка

Урок 8. «Выигрышная стратегия. Выигрышные и проигрышные позиции»

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

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

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

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

Для рассмотрения на листе определений выбрана игра камешки, в которой разрешено брать 1, 3 или 4 камешка на каждом ходу. (Такой набор разрешенных ходов не случаен: при более простых разрешенных ходах раскраска числовой линейки получается периодической, и это может привести детей к нежелательным обобщениям.)

Начнем изучение совсем с маленьких начальных позиций. Если камешки уже кончились (позиция 0), то игрок, который только что сделал ход, выиграл. Это значит, что для игрока, которому теперь надо было бы сделать ход, позиция 0 – проигрышная. Он точно не выиграет, потому что его противник уже выиграл!

Если камешков 1, 3 или 4, то тот игрок, чья очередь ходить, может сделать выигрышный ход – просто забрать все камешки. Значит, эти позиции выигрышные в нашей игре.

Если камешков 2, то игрок, чья очередь ходить, может сделать только один ход – взять один камешек. При этом он обязательно проиграет в этой игре: его противник заберет оставшийся камешек и выиграет. Значит, позиция 2 – проигрышная.

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

Назовем позицию, любой разрешенный ход из которой ведет в выигрышную позицию, проигрышной.

Назовем позицию, из которой существует ход, приводящий в проигрышную позицию, выигрышной.

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

Продолжим исследования позиций в игре камешки, следуя данным определениям.

Из позиций 5 и 6 есть ход, в результате которого получается проигрышная позиция 2. Значит, 5 и 6 – выигрышные позиции.

В результате всех ходов из позиции 7 получаются выигрышные позиции, значит, 7 – проигрышная позиция. И т. д.

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

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

Решение задач из учебника

Задача 40. Первое задание данной задачи – продолжение работы, начатой на листе определений. Поэтому ребятам помогут те же рассуждения, которые приведены на с. 27–28 учебника. Начинаем со следующей нераскрашенной позиции – 9. Возможные ходы игры – 1, 3 и 4, значит, из позиции 9 могут получиться позиции 8, 6 и 5. Все они выигрышные, значит позиция 9 проигрышная. Если кто-то из ребят затрудняется, поработайте вместе над позицией 9, используя наводящие вопросы: «Какие ходы может сделать игрок?», «Какие позиции могут получиться из позиции 9 в результате одного хода?», «Какими являются эти позиции (есть ли среди них проигрышные)?», «Какой (выигрышной или проигрышной) является позиция 9?».

Далее ребята продолжают раскрашивать числовую линейку самостоятельно до позиции 15:

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

Наконец, ребята должны составить разумную партию целиком. Мы уже обращали ваше внимание, что разумный ход (оставляющий противнику проигрышную позицию) может сделать лишь игрок, находящийся в выигрышной позиции. Поскольку игру начинает Первый и находится при этом в выигрышной позиции 15, то он может сделать разумный ход: взять 1 камешек и оставить Второму проигрышную позицию 14. Теперь в результате любого хода Второй оставит Первому выигрышную позицию (13, 11, 10). Второй просто не может сделать позицию проигрышной, поэтому он может делать любой ход, например взять 3 камешка. Первый снова должен сделать разумный ход и оставить Второму проигрышную позицию 7 и т. д. Итак, в данном случае разумной партию делает только Первый, все позиции, которые он оставляет Второму, должны быть проигрышными. Например, разумной будет следующая партия:

15 – 14 – 11 – 7 – 3 – 0

Задача 41. Данная задача аналогична задаче 40, и работать с ней ребятам предстоит по той же схеме. Вот раскрашенная числовая линейка:

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

12 – 11 – 9 – 7 – 6 – 5 – 3 – 1 – 0 

Задача 42. Необязательная. Эта задача помечена как необязательная, хотя ее первое задание ничем не сложнее обязательной задачи 40. Вот раскрашенная числовая линейка, которая при этом должна появиться у ребят.

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

Проведя несколько партий в камешки по данным правилам (разрешается брать 1 или 3 камешка), ребята могут убедиться в том, что выигрывает действительно всегда только Первый. Почему? Анализируя раскрашенную линейку, можно заметить, что Первый вынужден играть разумно «в принудительном порядке», т. е. он при любом своем ходе оставляет Второму всегда только проигрышные позиции. Это легко проверить, моделируя различные партии на раскрашенной числовой линейке.

Еще проще можно объяснить исход игры, используя четность-нечетность позиций. Действительно, при начальной позиции 11 (нечетное число) все возможные позиции после хода Первого – четные числа (ведь разрешается брать только 1 или 3 камешка!). А после хода Второго остаются всегда только нечетные числа. Поэтому позиция 0 может получиться только после хода Первого (ноль – четное число), а после хода Второго она получиться не может.

Задача 43. Необязательная. Если кто-то из ребят затрудняется с решением, попробуйте с помощью вопросов навести его на мысли о связи длины ползунка (четности-нечетности числа его звеньев) и выигрыша определенного игрока (см. комментарии к задачам 27, 28, 37). Посоветуйте ребятам сначала работать в черновике (на запасных полях 4×3 с листа вырезания), а уже потом нарисовать соответствующие позиции в рабочей тетради. Лучше, если ходы Первого и Второго ребята будут, как обычно, раскрашивать двумя разными цветами, так им проще будет увидеть победителя, а вам проверить правильность ответа.

Задача 44. Необязательная. Скорее всего, дети воспользуются методом проб и ошибок или методом перебора. Проще всего узнать первую команду в первой конструкции повторения, ведь вправо – единственная команда, которую может выполнить Робик из начального положения, не выходя за пределы закрашенной фигуры. Вторую команду можно определить перебором. Действительно, команду вниз Робик выполнить не может (тогда он выйдет за пределы поля), вправо – может, но тогда Робик не повторит команды внутреннего цикла даже дважды. Остаются две возможные команды – влево и вверх, которые надо рассмотреть подробнее. Выбрав команду вверх, мы подбираем число повторений – здесь возможны два варианта – 2 и 3. Сравнивая на каждом этапе результат выполнения конструкции с клетками, закрашенными в задании, дети постепенно находят правильный ответ. Закончить решение задачи, конечно, необходимо проверкой – выполнением написанной программы на соответствующем поле (можно использовать поля с листа вырезания).

Ответ:

Задача 45. Данная задача – обобщенный и сокращенный вариант задач 40 и 41, уже не содержащий подсказок. Вот раскрашенная числовая линейка:

Здесь не указано, кто должен победить в разумной партии. Учащийся должен понять это сам, анализируя выигрышные и проигрышные позиции на числовой линейке. В данном случае начальная позиция 15 – выигрышная, поэтому разумность партии зависит от Первого, который должен в результате каждого своего хода оставлять Второму проигрышную позицию. Ходы Второго могут быть любыми. Если задачи 40 и 41 ребята решили легко, данную задачу можно использовать для промежуточного контроля. Здесь можно проверить, научились ли ребята раскрашивать числовую линейку и понимают ли они отличие разумной партии от других. Ниже приведена одна из возможных разумных партий.

15 – 12 – 9 – 8 – 6 – 4 – 2 – 0

Задача 46. В ходе решения этой задачи ребята повторяют понятие уровни дерева. Однако наиболее сложным здесь оказывается обеспечить истинность утверждения в рамке, ведь бусины из мешков A, B, C, D можно просто нарисовать сразу на соответствующих уровнях.

Как же соединить эти бусины в дерево, чтобы в нем не было двух одинаковых путей? В данной задаче ситуация осложняется тем, что на каждом уровне есть по несколько одинаковых бусин. В ходе проб и ошибок ребята могут заметить, что никакая бусина третьего уровня не может иметь 2 (или более) следующих, поскольку в этом случае в дереве сразу появятся одинаковые пути, ведь все бусины четвертого уровня одинаковые. Следовательно, каждая бусина третьего уровня должна иметь не более одной следующей. Из этого следует, что ровно одна бусина третьего уровня является листом. Лучше сделать листом желтую круглую бусину, чтобы уменьшить число одинаковых бусин, которые будут входить в пути длины 4. Соединим оставшиеся бусины третьего и четвертого уровней. Теперь у нас появились два одинаковых конца пути (желтая круглая – зеленая круглая). Учитывая то, что первые бусины этих путей будут также одинаковые (потому что все бусины первого уровня одинаковые), мы можем поправить дело только за счет бусин второго уровня – взять в эти пути разные бусины второго уровня (красную квадратную и синюю треугольную). Правильный ответ в этой задаче не единственный, мы приводим лишь один вариант дерева Х.

Задача 47.  Здесь при построении каждой цепочки требуется соблюдение двух условий: ползунок должен проходить через заданный отрезок, выиграть должен определенный игрок. Первое условие соблюсти достаточно легко – надо просто пристраивать ходы к заданному отрезку. Что касается второго условия, здесь могут помочь некоторые соображения, касающиеся связи между выигрышем определенного игрока и четностью-нечетностью числа звеньев ползунка. Ясно, что если число звеньев ползунка четное, то выиграет Второй, если нечетное – Первый. Кроме того, число звеньев ползунка связано с числом точек на поле, через которое он прошел: ползунок из нечетного числа звеньев проходит через четное число точек и наоборот. Таким образом, чтобы выиграл Второй, нужно, чтобы ползунок прошел через все 9 точек поля, а чтобы победу одержал Первый – через 8 или 6 (других вариантов на данном поле не может быть). Если кто-то из ребят будет строить ползунок наугад и запутается, натолкните его на подобные соображения. Ниже мы приводим два примера цепочки К и один пример Л.

Задача 48. Необязательная. Во второй части курса («Информатике 3 – 4») с такими задачами ребята уже встречались. Сложности здесь могут быть связаны с логической структурой условия. В частности, дети должны понимать, что любое слово из мешка должно находиться в словарике, но в словарике есть и «лишние» слова, которые для решения не пригодятся. Каждая заготовка в мешке определяет слово, которое должно быть в нее помещено, однозначно. Например, в словарике есть лишь одно слово из четырех букв (ГУСЬ), именно его нужно вписать в заготовку из четырех окон в мешке. То же относится и к другим словам, в том числе, содержащим дефис. Так в словарике есть лишь 2 слова, составленные из двух слов через дефис, в первом из которых четыре буквы, а во втором – шесть. При этом лишь одно из этих слов заканчивается на букву «к». Поэтому заготовка для первого слова в мешке определяет его однозначно (ОРЁЛ-КАРЛИК).

Компьютерный урок «Выигрышная стратегия. Выигрышные и проигрышные позиции», задачи 43 – 49

Задача 43. Закрепление изученного материала. Эта задача аналогична задачам 40‒42 из учебника. Анализируя позиции игры, ребята раскрашивают числовую линейку:

Затем, используя раскрашенную линейку, отвечают на вопросы. 

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

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

Задача 44. Сначала ребята раскрашивают числовую полоску:

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

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

Кто  выиграл  в  твоей  партии?  Ответ: ПЕРВЫЙ.

Каким  цветом  раскрашена  клетка  15  на  числовой  полоске?  Ответ: КРАСНЫМ.

Задача 45. Решений здесь довольно много. Из второго утверждения ясно, что в дереве должно быть 3 уровня. В первом и третьем утверждениях задана форма бусин первого и второго уровней. В остальном дерево может быть построено произвольно.

Задача 46. Сначала ребята раскрашивают числовую полоску:

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

Вопросы даны для проверки решения – ответы у всех должны получиться одинаковыми.

Каким  цветом  раскрашена  клетка  13  на  числовой  полоске?  Ответ: КРАСНЫМ.

Кто  выиграл  в  твоей  партии?  Ответ: ПЕРВЫЙ.

Задача 47. В партии должен выиграть Первый, значит, в построенной ломаной должно быть нечетное число отрезков - на 1 красный отрезок должно быть больше.

Вот один из вариантов решения:

Задача 48. Решение подобной задачи на компьютере позволяет относительно быстро сделать перебор всех клеток поля, но лучше все-таки этот перебор немного сократить, проанализировав данную программу. Внимательно изучив конструкцию повторения, можно понять, что в результате выполнения её команд 1 раз Робик передвигается на одну «ступеньку» вниз‒влево и перед этим заходит на клетки одного ряда внизу и одного ряда слева:

Так как Робику нужно выполнить 4 таких перемещения, логично начинать перебор с клеток, находящихся ближе к верхнему правому углу поля. И тогда решение находится довольно быстро:

Задача 49. Достаточно сложная задача. Рассуждать можно так. В таблице указано, что меньше всего синих шариков – их 4. Значит, в мешок можно положить не более 4 связок, в которых содержится синий шарик. В одной из таких связок находится также голубой и зеленый шарики - положим 4 такие связки в мешок. По таблице видно, что голубых и зелёных шариков должно быть по 5 штук. В библиотеке есть связка, в которой имеются голубой и зелёный шарики вместе с желтым, – попробуем положить в мешок и эту связку. Далее из таблицы мы понимаем, что в мешке должно быть по 6 красных и фиолетовых шариков, и в библиотеке имеется связка из красного, фиолетового и желтого шариков. Попробуем взять шесть таких связок и проверить выполнение условия по таблице. Оказывается, что задача решена.