TwiddleLab / Искусственный интеллект / Поиск, игры и планы

Деревья игры

Урок 4 из 11 · 6 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Дерево игры показывает все способы, которыми может пойти игра: позиция наверху (корень), каждый ход это ветка, каждая законченная игра это концовка (лист).
• Число ходов из позиции это коэффициент ветвления. На сколько ходов вглубь идёт дерево, это его глубина.
• Деревья растут быстро: примерно b x b x ... x b, то есть b^d позиций через d ходов.

Начать урок

Как идёт урок

1. Ходит X. Осталось три клетки. Куда должен сходить X?

   Сделай ставку. Нажми на свободную клетку.

2. Вырасти все возможные варианты будущего.

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

3. Раскрась каждую концовку: победа X, победа O или ничья.

   Нажми на концовку, чтобы поменять её цвет. Ищи три в ряд.

   У O уже есть правый верхний и левый нижний углы. Если в ход O центр ещё свободен, O занимает его и выигрывает по этой диагонали. Каждая другая концовка это линия для X.

4. Теперь выбери ход X, читая дерево.

   Выбери ветку, где O никогда не выиграет.

   Если X занимает центр, он перекрывает диагональ O и создаёт сразу две угрозы, внизу посередине и внизу справа. O может закрыть только одну, поэтому обе концовки это победы X. Два других хода оставляют центр для O.

5. Такая картинка называется деревом игры.

   Позиция наверху это корень. Каждый ход это ветка. Законченная игра это лист. Число ходов из позиции это коэффициент ветвления, а число ходов вниз это глубина.

6. Как быстро растут деревья? Найди наименьшее число пустых клеток, при котором игр больше 1000.

   Если пустых клеток n, у X есть n вариантов, потом у O n - 1, потом n - 2... Всего не больше n x (n - 1) x ... x 1 игр. В математике это n! (n факториал).

   6! = 720 и 7! = 5040. Каждая лишняя пустая клетка умножает количество. Для пустой доски 9! = 362 880 это верхняя граница; из-за игр, которые заканчиваются раньше, настоящее число 255 168.

7. В шахматах в обычной позиции около 35 ходов. Сколько позиций на 4 хода вперёд?

   Поставь булавку на шкалу. Каждый шаг вправо в 10 раз больше.

   При коэффициенте ветвления b и глубине d у дерева внизу около b^d позиций. 35^4 это 1,5 миллиона; 35^8 уже больше 2 триллионов.

8. Игра: найди безопасный ход в трёх новых позициях.

   Каждый раз ходит X. Нажми на ход, под которым нет оранжевой концовки. Три жизни.

9. Расставь игры по размеру их деревьев.

   Сколько примерно разных партий можно сыграть? Перетащи каждую игру на шкалу.

   Это примерные размеры деревьев игры: около 10^5 игр для крестиков-ноликов, 10^21 для «Четыре в ряд», 10^123 для шахмат и 10^360 для го. Бот может прочитать все крестики-нолики, но не шахматы и не го. Это следующая задача.

Предыдущий урок: Эвристики: A* находит путь · Следующий урок: Минимакс · Часть курса: Поиск, игры и планы

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.