Урок 29
Использование графов
§ 18. Игровые стратегии

Содержание урока

Выигрышные и проигрышные позиции

Дерево перебора вариантов

Решение без дерева

Исследование игры

Выводы

Вопросы и задания

Решение без дерева

Для того чтобы при заданном значении S определить, какова начальная позиция — выигрышная или проигрышная, не обязательно строить дерево. Составим таблицу, в которой для каждой позиции (для каждого значения S) будем указывать, какая это позиция и на каком ходу завершится игра. Как мы знаем, S = 1 — это проигрышная позиция, Петя проигрывает за один ход. Отмечаем её в таблице как П, где буква «П» означает проигрыш, а индекс «1» — количество ходов (рис. 3.43).

Рис. 3.43

Выигрышными будут все позиции, из которых можно каким-либо ходом получить проигрышную позицию S = 1, т. е. позиции S = 2 и S = 3. Отмечаем их как В, (выигрыш за 1 ход) — рис. 3.44.

Рис. 3.44

Из позиции S = 4 все возможные ходы ведут в выигрышные позиции, поэтому эта позиция — проигрышная (проигрыш за 2 хода) — рис. 3.45.

Рис. 3.45

Рассуждая таким же образом, заполните таблицу до конца.

Следующая страница Исследование игры

Cкачать материалы урока