Логические основы
<<  Что такое триггер Основы логики в информатике  >>
Детерминированные игры с полной информацией
Детерминированные игры с полной информацией
Игра с полной информацией
Игра с полной информацией
Игра
Игра
Элемент случайности
Элемент случайности
Стратегия
Стратегия
Возможные ходы
Возможные ходы
Детерминированные настольные игры
Детерминированные настольные игры
Крестики-нолики
Крестики-нолики
Общеизвестный алгоритм
Общеизвестный алгоритм
Крестики
Крестики
Первый ход
Первый ход
Нолики
Нолики
Спички
Спички
Дерево игры
Дерево игры
Простроенная схема
Простроенная схема
Задача
Задача
Ход выигравшего игрока
Ход выигравшего игрока
Поиск в глубины
Поиск в глубины
Игрок
Игрок
При первом ходе
При первом ходе
Выигрышная стратегия
Выигрышная стратегия



Два игрока
Два игрока
Три продолжения
Три продолжения

Выигрышный ход
Выигрышный ход
Презентация «Игры с полной информацией». Размер 328 КБ. Автор: Eugene.

Загрузка...

Игры с полной информацией

содержание презентации «Игры с полной информацией.ppt»
СлайдТекст
1 Детерминированные игры с полной информацией

Детерминированные игры с полной информацией

Детерминированные игры с полной информацией. Выигрышная стратегия в игре.

2 Игра с полной информацией

Игра с полной информацией

Игра с полной информацией — термин, обозначающий логическую игру, в которой для соперников отсутствует элемент неопределённости.

3 Игра

Игра

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

4 Элемент случайности

Элемент случайности

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

5 Стратегия

Стратегия

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

6 Возможные ходы

Возможные ходы

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

7 Детерминированные настольные игры

Детерминированные настольные игры

К играм с полной информацией относятся детерминированные настольные игры (например, шахматы, шашки, крестики-нолики и др.). Для большинства из них алгоритм выигрыша или гарантированной ничьей неизвестен, хотя теоретически он существует. На практике вариантов слишком много, чтобы их можно было построить и проанализировать за приемлемое время.

8 Крестики-нолики

Крестики-нолики

Крестики-нолики. Правила игры Игроки по очереди ставят на свободные клетки поля свои знаки (крестики и нолики соответственно). Первый, выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или диагонали, выигрывает. Первый ход делает игрок, ставящий крестики.

9 Общеизвестный алгоритм

Общеизвестный алгоритм

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

10 Крестики

Крестики

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

11 Первый ход

Первый ход

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

12 Нолики

Нолики

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

13 Спички

Спички

Игра «Спички». Сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички;

14 Дерево игры

Дерево игры

Дерево игры. Выигрывает тот, кто оставит в кучке 1 спичку.

15 Простроенная схема

Простроенная схема

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

16 Задача

Задача

Задача 1.

17 Ход выигравшего игрока

Ход выигравшего игрока

Каким должен быть первый ход выигравшего игрока? Каждый хочет выиграть! Никто не ошибается! Выигрыш зависит только от начального положения и правил игры. Тот, кто получил 25 или больше камней в обоих кучках, проигрывает.

18 Поиск в глубины

Поиск в глубины

«Поиск в глубины». (14,12) 26*. При первом ходе i-ого игрока (7,4) выиграет ii-й – у него есть ход (11,4), который приводит к выигрышу.

19 Игрок

Игрок

При первом ходе (6,4) также выигрывает ii-й игрок, если пойдет (12,4).

20 При первом ходе

При первом ходе

При первом ходе (3,8) также выигрывает ii-й игрок, если пойдет (3,12). (6,20)26*.

21 Выигрышная стратегия

Выигрышная стратегия

Выигрышная стратегия. Выигрывает II-й игрок; своим первым ходом ему нужно свести игру к позиции (11,4), (12,4) или (3,12), а вторым ходом – к одной из позиций (15,8), (16,8), (11,12), (12,12) или (6,16). Для выигрывающего игрока достаточно указать только один выигрышный ход, а для проигравшего нужно рассмотреть все ходы на каждом шаге!

22

23

24

25 Два игрока

Два игрока

Задача 2. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

26 Три продолжения

Три продолжения

из каждой ситуации в этой игре возможно три продолжения по теореме Пифагора расстояние L от точки с координатами (x,y) до начала координат – это или в начальный момент условие не выполнено.

27

28 Выигрышный ход

Выигрышный ход

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

«Игры с полной информацией»
Сайт

5informatika.net

115 тем
5informatika.net > Логические основы > Игры с полной информацией.ppt