Задание С3 ОПРЕДЕЛЕНИЕ ВЫИГРЫШНОЙ СТРАТЕГИИ ИГРЫ (АНАЛИЗ И ПОСТРОЕНИЕ ДЕРЕВА ИГРЫ)
ПРИМЕР: Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (-3,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (х,у) в одну из трех точек: или в точку с координатами (х+5,у), или в точку с координатами (х,у+4), или в точку с координатами (х+3,у+3). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) больше 12 единиц. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Технология выполнения задания СЗ Существует несколько способов выполнения задания СЗ. Сначала рассмотрим первый способ - методом построения полного дерева игры и определения по нему выигрывающего игрока. Этот метод предполагается составителями данной задачи. С другой стороны, он самый кропотливый и трудоемкий. Построение полного дерева игры - это рассмотрение для каждой позиции игры всех возможных ходов. Затем для получившихся позиций - снова рассмотрение всех возможных ходов. И так до тех пор, пока по всем получившимся "направлениям" мы не достигнем конца игры (в рассмотренном примере - расстояние от точки (0,0) до текущей позиции фишки больше 12 единиц). Если изобразить такое решение графически: от начальной позиции нарисовать три линии - возможные ходы - в следующие позиции, из каждой из них - по три линии в следующие позиции, и т.д., то такое изображение будет напоминать дерево с ветвями-линиями (если, конечно, рисовать начальную позицию в нижней части листа, а линии - вверх). Это и называется "деревом игры", которое упоминается в критериях оценивания.
Обычно дерево рисуют сверху вниз или слева направо. Данное решение выглядит очень трудоемким, потому что для каждой позиции игры нужно указать три возможных варианта следующего хода (в других задачах СЗ -четыре варианта). То есть, рассматривая каждый следующий ход, размер нашего дерева игры увеличивается в три раза. Так как это учебная задача, числа в ней подобраны так, чтобы дерево, все же, имело разумные размеры. Но все равно, выигрыш редко достигается раньше четвертого хода. А это значит, что в дереве на 4-м ходу рассматриваются вариант игры, правда, часто многие из них повторяются. дерево игры обычно строят-рисуют сверху вниз или слева направо. Мы будет изображать его слева направо из-за способа представления данных (в книге). Ведь в дереве будет в результате около 81 позиции на 4-м уровне. Если изображать дерево сверху вниз, ширины страницы при этом не хватит. А вот в высоту 81 строчка вполне поместится.
Сначала рассмотрим все возможные варианты первого хода (их три): Начальное положениеПервый ход 1-го игрока -3,2 2,2 -3,6 0,5 Затем для каждого положения после первого хода рассмотрим все возможные варианты второго хода: Начальное положениеПервый ход 1-го игрокаПервый ход II-го игрока -3,2 2,2 7,2 2,6 5,5 -3,6 2,6 -3,10 0,9 0,5 5,5 0,9 3,8
Что считать критерием остановки. есть два пути - либо для каждой позиции дерева вычислять расстояние до точки (0,0) (проще - квадрат расстояния), по теореме Пифагора. Либо вычислить "граничные" целочисленные координаты, "после которых" игра заканчивается. Проще -первое, быстрее - второе. для простоты, воспользуемся первым способом. Допишем к нашему дереву для каждой позиции квадрат расстояния до точки (0,0): Начальное положение Первый ход I-го игрокаПервый ход II-го игрока -3,2(13) 2,2(8) 7,2 (53) 2,6 (40) 5,5 (50) -3,6(45) 2,6 (40) -3,10(109) 0,9(81) 0,5 (25) 5,5 (50) 0,9(81) 3,8 (100)
Напоминаем, игра заканчивается по достижении расстояния, большего 12-ти. Это значит, что квадрат расстояния должен быть больше 144. Пока что ни одна из рассмотренных позиций не превысила 144, поэтому для каждого получившегося положения снова рассматриваем все три возможных варианта хода:
-3,2
Жирным выделены те позиции фишки, расстояние до которых от точки (0,0) больше 12. То есть, это выигрыш одного из игроков (в данном случае, первого). Ходы из этих позиций дальше можно не рассматривать - игра на этом закончится. Рассмотрим остальные возможные позиции игры (после второго хода второго игрока):
Дерево игры в виде таблицы получилось, как мы и предупреждали, немаленькое, но зато мы получили результат - полное дерево игры. Видно, что в последнем столбце квадрат расстояния (в скобках) всегда больше 144, поэтому дальше игра во всех случаях продолжаться не будет. Мы получили дерево игры, но пока что еще не получили ответа ни на один вопрос, который у нас спрашивают - кто выигрывает, как он при этом должен ходить и почему это так. Ответы на эти вопросы мы получим из анализа дерева игры: Позиции, выделенные жирным шрифтом в таблице - выигрыш. То есть, если игрок в нее перейдет, то он сразу выиграет. Значит, предыдущая позиция (из которой игрок ходил) является для него выигрышной (из этой позиции игрок может пойти так, чтобы выиграть). Обозначим эти позиции подчеркиванием (мы приводим измененную таблицу, при решении, конечно, нужно просто подчеркнуть позиции в имеющейся):
Повторимся - мы обозначили как выигрышные (подчеркнутые) все те позиции, справа от которых есть выигрыш (выделено жирным). То есть, все те позиции, из которых можно одним ходом выиграть. Заметим, что для выделения этих позиций мы "двигаемся по дереву игры" с конца - для каждой конечной "жирной" позиции выделяем ее предшественника как выигрышную позицию. Теперь осуществим следующий шаг - определим проигрышные позиции. Это те позиции, из которых куда бы ни пошел игрок, он обязательно попадет в выигрышную (для соперника) позицию, тем самым его соперник тут же выиграет. Значит, это те позиции, из которых все три хода приводят в выигрышную позицию. То есть, клетки, справа от которых все три клетки подчеркнуты. Таких позиций будет всего 4 во всей таблице - два раза позиция (2,6) и два раза позиция (5,5). Обозначим их жирным курсивом. Чтобы не загромождать наше рассуждение излишней огромной таблицей, мы опустили последний столбец (второй ход II- го игрока), который сейчас уже не важен, так как про все позиции второго хода 1-го игрока мы знаем, какие они:
Теперь можно пометить как выигрышные (за два хода) некоторые из оставшихся позиций. Важно понимать, что и почему мы считаем выигрышными и проигрышными позициями. Проигрышной считается позиция, из которой куда бы ни пошел игрок, его соперник окажется в выигрышной позиции. В отличие от нее, выигрышной считается позиция, из которой существует хотя бы один ход, приводящий к выигрышу. То есть (для позиций, выигрывающих за два хода) ход, который приводит соперника в проигрышную позицию. В данном случае, все три позиции первого хода 1-го игрока являются выигрышными - из каждой из них можно пойти в проигрышную позицию (выделенную жирным курсивом):
Получается, что начальная позиция является проигрышной (куда бы из нее ни пошел, приводишь соперника в выигрышную позицию). Значит, игрок, который ходит первым - проигрывает. Значит, выигрывает второй игрок: Начальное положениеПервый ход 1-го игрока -3,2 (13) 2,2 (8) -3,6 (45) 0,5 (25)
Мы получили ответ на первый вопрос - кто выиграет (второй игрок). Теперь нужно определить, как он должен для этого ходить. Это можно получить из этой же самой таблицы дерева игры. Напомним, на данный момент наша таблица полного дерева игры выглядит так:
Из каждой позиции, выделенной подчеркиванием нужно ходить в позицию, выделенную жирным курсивом (или просто жирным, на последнем ходу). Удалим те позиции, в которых игра заведомо не окажется: выигрывающий игрок не будет во вред себе ходить неправильно (в частности, это соображение привело к удалению целых веток дерева, возникающих при ошибочных первых ходах II-го игрока (таких как 7,2; -3,10; 0,9; 3,8)); ходы проигрывающего игрока нужно привести все, ибо ему терять нечего, и он может ходить как угодно (пытаясь, вероятно, запутать соперника ); в тех случаях, когда выигрывающий игрок имеет несколько вариантов выигрывающего хода, оставим один из них:
Эта таблица (назовем ее "неполное дерево игры") содержит все возможные ходы первого игрока и соответствующие им ответы второго игрока. То есть, полную стратегию выигрыша. Именно эту таблицу ожидают увидеть от нас авторы-разработчики задания, именно она приведена как образец в критериях оценивания. Правда, без указания квадратов расстояния до точки (0,0). Достаточно привести в ответе эту таблицу (с указанием того, что выигрывает второй игрок) - и мы получим наши заслуженные... 2 балла из трех. Как же так, почему только 2!? Потому что мы не привели доказательство правильности нашего решения. То есть, обоснованные умозаключения, из которых можно сделать вывод о правильности решения. Это значит, нам нужно привести такие доводы, из которых будет четко понятно, почему это решение правильное и не забыть написать вывод, который мы делаем из анализа этих доводов.
Самым коротким правильным оформлением ответа, с доказательством правильности, мы считаем именно тот, который приведен в качестве примера оформления в критериях оценивания - в нем неполное дерево игры служит одновременно и указанием стратегии игры и доказательством правильности решения. Приведем его:
Выигрывает второй игрок. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры. 1 ход2 ходЗход4 ход Стартовая позиция 1-й игрок (все варианты хода) II-й игрок (выигрышный ход) 1-й игрок (все варианты хода) II-й игрок (выигрышный ход) -3,2 0,55,5 8,813,8 5,910,9 10,515,5 -3,62,6 5,910,9 2,107,10 7,612,6 2,22,6 5,910,9 2,107,10 7,612,6 Таблица содержит все возможные варианты ходов первого игрока. Из нее видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
Это самая короткая запись ответа и поэтому почти каждая буква в нем очень важна. Рекомендуем вам выучить наизусть приведенные здесь фразы и дословно воспроизвести их на экзамене. Важно также не забыть надписать столбцы, не забыв указать, чей это ход и что это "все варианты хода" проигрывающего игрока и "выигрышный ход" выигрывающего. Если вам не нравится выучивать образцовое решение - можете попытаться описать свой ответ словами. В этом случае не забудьте: 1) четко написать, кто выигрывает; 2) для каждого возможного хода проигрывающего игрока написать, как должен ходить победитель (причем сделать это не только для первого хода, но и для всех остальных ходов тоже); 3) пояснить, что Вы рассмотрели (и привели) все возможные ходы проигрывающего игрока и для каждого случая указали ходы выигрывающего игрока, приводящие к победе. На основании этого Вы делаете вывод, что ваше решение верно и что выигрывает именно этот игрок.