Урок 11. Комментарий для учителя к уроку «Дерево игры»

Уроки 11. «Дерево игры»

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

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

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

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

Задача 63. Очень важно, чтобы с этой задачей справились все ребята. Не жалейте на нее времени, тем более что учащиеся здесь встретятся с некоторыми новыми моментами, на которые нужно обратить внимание.

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

Если вы видите, что кто-то из учеников не знает, с чего начать, можно помочь ему следующими вопросами: «Какие ходы может сделать Первый из начальной позиции?», «Какие позиции при этом могут получиться?», «Какие ходы может сделать Второй из возможных позиций второго уровня (4 и 5)?», «Какие позиции могут при этом получиться?» и т. д. Если вы видите, что учащийся не отвечает на эти вопросы, возможно, стоит вместе разобраться, как построено дерево G на с. 39. Чтобы при построении дерева не запутаться, перебирая возможные позиции, лучше располагать все вершины, следующие за некоторой вершиной, в определенном порядке, например, сверху вниз по убыванию числа камешков в позициях.

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

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

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

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

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

Ответ:

Задача 64. Как и задача 63, данная задача является очень важной, ведь это первое задание на построение ветки дерева игры. Для облегчения технической работы мы поместили заготовки всех необходимых полей, на которые скопированы все значки из корневой позиции. Ребятам остается только дорисовать позиции, но вначале им придется решить ряд вопросов.

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

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

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

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

Ответ:

Задача 65. Необязательная. Здесь ребятам нужно написать программу, которая приводит Робика в определенную клетку поля и при этом заставляет его обходить стены. Если вы хотите немного усложнить задание, попросите ребят написать такую программу С, которая уместится в окне. Самая короткая программа С имеет длину 18. Действительно, чтобы привести Робика из левого нижнего угла в правый верхний на том же поле без стен, потребуется самое меньшее 14 команд (ведь нужно пройти 6 клеток вверх и 8 вправо). Здесь же нам приходится как минимум в двух местах обходить стену, т. е. идти влево или вниз (а потом возвращаться). Программ С минимальной длины много, приведем одну из них.

 

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

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

Придется изобретать какой-то свой способ. Предлагаем здесь два способа рассуждений.

Первый способ. Рассмотрим сначала второе утверждение. В мешке ровно две квадратные бусины и ровно две красные бусины. В цепочке должны стоять две «слипшиеся» пары красная – квадратная. Есть всего два варианта таких пар:

либо

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

Остались две круглые синие. Как им найти место? Одну синюю круглую можно поставить перед парой, а вторую уже поставить будет некуда. Поставим круглую синюю:

Тогда через одну после нее нужно поставить еще одну синюю – не получается, не хватает еще синих.

Рассмотрим второй вариант «спаривания» красных и квадратных. После пары «красная круглая – зеленая квадратная» нужно поставить (треугольную или круглую) синюю бусину. Поставим треугольную: 

Оставшиеся две круглые синие поставить будет некуда. Поставим круглую: 

Тогда через одну после нее должна стоять еще одна круглая. Есть два варианта следующих двух бусин: либо вторая пара, либо две оставшиеся синие:

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

Второй способ. Систематический перебор по последней бусине цепочки Щ. Последняя бусина не может быть круглой, иначе первое утверждение не будет иметь смысла, и не может быть красной, иначе на все квадратные бусины красных просто не хватит. Поэтому на последнем месте цепочки Щ могут стоять: синяя квадратная бусина, зеленая квадратная бусина или синяя треугольная бусина. Теперь рассмотрим каждый случай.

Пусть последняя бусина цепочки – зеленая квадратная, тогда перед ней – красная треугольная (красная круглая здесь стоять не может, иначе первое утверждение потеряет смысл): 

Осталось пять бусин и пять свободных мест, снова начинаем пробовать различные варианты. При этом быстро выясняется, что круглые бусины не могут стоять на четвертом и пятом местах, иначе становится ложным первое утверждение. Значит, три круглые бусины должны стоять на первых трех местах. Но тут приходим к противоречию. Если красная бусина первая или вторая в этой тройке, то за ней обязательно должна идти квадратная (что не получается), если же красная бусина последняя, то она вторая после круглой, а вторая после круглой должна быть синей. Делаем вывод: последняя бусина цепочки Щ – не зеленая квадратная. Аналогично приходим к противоречию, если последняя бусина – синяя треугольная.

Пусть последняя бусина цепочки – синяя квадратная. Тогда перед ней стоит красная треугольная (см. выше). 

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

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

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

Задача 67. Повторяем понятия перед каждой бусиной/после каждой бусины. В ответе должно получиться слово КАРТОШКА.

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

Ответ:

Задача 69. В ходе решения подобных задач устанавливается связь между веткой дерева игры и отдельными партиями игры. Для начала ребятам необходимо понять, как связано дерево Н с цепочкой Q. Должны выполняться два условия: окончание цепочки Q – это путь дерева Н и число отрезков в заключительной позиции пути дерева Н должно соответствовать заданной длине цепочки Q. Ребята к настоящему моменту должны понимать, если в цепочке 9 бусин, значит, в партии сделано 8 ходов. Теперь ясно, что заключительными позициями партий с цепочкой Q могут быть лишь листья третьего уровня дерева Н.

Последнее изменение: Tuesday, 19 September 2023, 00:35