Выигрышная стратегия Информатика 4 класс Брилинская школа

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

Рассмотрим игру к кк камешки с начальной позицией 8 камешков, в которой разрешается брать на каждом ходу 1, 3 или 4 камешка. Изучать позиции игры будем с точки зрения того игрока, чья очередь делать ход. Разместим все возможные позиции игры на числовой линейке: Выигрышные и проигрышные позиции Назовём п пп позицию выигрышной, если из неё есть ход, который оставит противнику проигрышную позицию. Такую позицию будем помечать на линейке к кк красным цветом. Назовём п пп позицию проигрышной, если любой ход из неё, оставляет противнику выигрышную позицию. Такую позицию будем помечать на линейке с сс синим цветом

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

Позиция 5 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 5 к кк красным цветом

Позиция 5 красным цветом Позиция 5 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 5 красным цветом Позиция 6 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 5 к кк красным цветом.

Позиция 6 красным цветом Позиция 6 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 5 красным цветом. Позиция 7 – проигрышная: все ходы, которые можно сделать из этой позиции, оставляют противнику выигрышную позицию 6, 4 или 3. Пометим 7 с сс синим цветом.

Позиция 5 красным цветом Позиция 5 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 5 красным цветом Позиция 6 красным цветом Позиция 6 – выигрышная: сделав ход, можно оставить противнику 2 камешка – проигрышную позицию. Пометим 6 красным цветом. Позиция 7 синим цветом Позиция 7 – проигрышная: все ходы, которые можно сделать из этой позиции, оставляют противнику выигрышную позицию 6, 4 или 3. Пометим 7 синим цветом. Позиция 8 – выигрышная: сделав ход, можно оставить противнику 7 камешков – проигрышную позицию. Пометим 8 к кк красным цветом.

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