Прежде чем ИИ сделает ход, он должен отыскать его в стоге сена из ста пятидесяти тысяч слов, а затем вовремя прекратить поиски.
Написано и отредактировано на английском языке. Эта русская версия создана машинным переводом; там, где важна точность, авторитетным остаётся английский оригинал. Читать оригинал на английском →
Дайте человеку полный набор фишек WordChess и скажите: «сыграй хорошее слово», и он сузит задачу, даже не заметив этого. У компьютера такой интуиции нет. На доске 25×25, имея собственный полный набор из ста фишек, он может попытаться выложить почти любое из 148 941 слова словаря, и каждое слово можно поставить в тысячи допустимых позиций и направлений. Хуже того, размещение допустимо, только если каждая новая буква, которую оно добавляет, образует настоящее слово и там, где пересекается с уже выложенным. Умножьте слова на размещения, учтите это ограничение пересечений, и получится пространство поиска, которое ни один игрок, кремниевый или нет, не сможет перечислить и ранжировать целиком.
Именно поэтому серьёзные движки словесных игр, в том числе Quackle, эталонная реализация с открытым кодом, никогда не перебирают словарь «в лоб». 4 Структура GADDAG, предложенная Стивеном Гордоном в 1994 году, а до неё DAWG позволяют программе наращивать слова от фишек, уже лежащих на доске, и проверять пересечения по ходу дела, так что недопустимые ветви отсекаются рано, а не оцениваются и отбрасываются потом. 1 Задача не в том, чтобы «перечислить все слова». Задача в том, чтобы «порождать только те ходы, которые в принципе могут быть допустимы, и делать это быстро».
Даже экономный генератор выдаёт больше ходов-кандидатов, чем можно глубоко оценить, поэтому вторая проблема — время. Maven Брайана Шеппарда, первая программа, превзошедшая сильнейших игроков-людей, столкнулась именно с этим и решила задачу в два этапа: быстрая эвристика грубо упорядочивает сырые ходы по качеству, и лишь короткий список самых многообещающих изучается тщательно — игру многократно проигрывают вперёд, чтобы увидеть, какой кандидат на деле показывает себя лучше всех. 2 В других играх та же идея известна под другими именами — rollout («прокат») в нардах и playout («разыгрывание») в программах для го; в Maven она называется симуляцией.
WordChess работает в том же духе, но при более жёстком ограничении: на каждый ход отводится фиксированный бюджет времени поиска. Когда бюджет исчерпан, ИИ выбирает лучшее слово из найденных к этому моменту. Это не компромисс, о котором жалеют инженеры, — в этом и состоит весь замысел. Игрок, который думает бесконечно, — не более сильный соперник, а лишь более медленный. Часы заставляют машину делать то, что люди делают инстинктивно: довольствоваться ходом, который явно хорош, а не доказуемо лучший.
Знать словарь — лёгкая часть. Знать, когда прекратить в нём поиск, — трудная.
Ленивый способ сделать игровой ИИ проще — сделать его глупым наугад, чтобы он проморгал ход, который явно видел. Игроки это замечают и возмущаются. Геймдизайнера Сида Мейера часто вспоминают в связи с тем, что он убрал из Civilization возможности заключать союзы, потому что компьютер мог пользоваться ими почти так же хорошо, как игрок; это, по словам Мейера, приведённым в одном обзоре проектирования ИИ-соперников, «оставляло бы у игроков ощущение, что они не могут победить, потому что компьютер жульничает». 3 Сложность, которая воспринимается как нечестность, отравляет игру, и поэтому научная литература о динамической подстройке сложности занимается настройкой того, на что ИИ способен, а не того, что ему позволено видеть. 5
WordChess настраивает четыре уровня по осям, понятным человеку, и никогда не подсовывает ИИ скрытую информацию. Уровни различаются тем, сколько времени им отведено на поиск, насколько глубоко в редкую часть словаря простирается их словарный запас и какие диапазоны длины слов они предпочитают. Лёгкий соперник играет правдоподобно слабые слова — настоящие, разумные, короткие, а не мусор. Гроссмейстер владеет тем же полным малоизвестным лексиконом, что и сложный уровень, и располагает наибольшим временем, чтобы его разрабатывать. Игрок проигрывает тому, что выглядит как более богатый словарный запас и более острое чтение доски, потому что именно этим оно и является.
| Уровень | Охват словаря | Бюджет поиска | Предпочтительная длина слов |
|---|---|---|---|
| Лёгкий | Только общеупотребительные | Самый короткий | Короткие |
| Обычный | Общеупотребительные + средние + половина редких | Короткий | Смешанные |
| Сложный | Полный | Долгий | Длиннее |
| Гроссмейстер | Полный | Самый долгий | Без ограничений |
Калькулятор каждый раз даёт один и тот же ответ; соперник вас удивляет. WordChess намеренно добавляет в выбор хода случайный шаг, чтобы почти равноценные ходы не всегда решались одинаково и ИИ не выкладывал каждый раз одно и то же слово. Вместе с потолками словаря для каждого уровня это даёт разнообразие — ощущение, что напротив сидит кто-то, кто делает выбор, и некоторые из этих решений могли бы принять и вы.
В этом и состоит тихое искусство. Правдоподобному сопернику сдержанность нужна не меньше, чем сила: готовность сыграть просто хорошее слово, оставить очки на столе, быть побеждаемым так, чтобы победа ощущалась заслуженной. Самой трудной инженерной задачей машины был поиск в стоге сена. Самой тонкой — научиться понимать, когда прекратить поиск, что знать и насколько сдерживаться.