Альфа-бета отсечение
Приём, позволяющий не досматривать ветку, которая уже хуже найденного: если соперник в ней имеет ответ сильнее, чем нас устраивает, остальное неважно. Результат не меняется — меняется объём работы. При хорошем порядке ходов даёт примерно вдвое большую глубину за то же время.
Knuth & Moore, Artificial Intelligence, 1975
Амодальное достраивание
Восприятие целой фигуры там, где часть её закрыта другой. Лист за кружкой виден как один лист, а не как две отдельные полосы бумаги. Достроенная часть не порождает ни цвета, ни яркости — отсюда «амодальное»: она присутствует в объекте, но не в изображении на сетчатке.
Michotte, Thines & Crabbe, Les complements amodaux des structures perceptives, 1964
Выскакивание цели
Свойство цели, отличающейся одним простым признаком: она находится за одно и то же время независимо от количества помех. Красный круг среди зелёных выскакивает; красный круг среди красных квадратов и зелёных кругов приходится искать, и время растёт с каждым лишним объектом.
Treisman & Gelade, Cognitive Psychology, 1980
Дамка, летающая по диагонали
Шашка, дошедшая до последнего ряда. В русских шашках она ходит и бьёт вдоль диагонали на любое расстояние и в любую сторону, за что её и называют летающей. Одна дамка часто стоит трёх простых шашек, и вся игра обычно строится вокруг того, кто пройдёт первым.
Дробь Вебера
Отношение едва заметной разницы к самой величине. Оно постоянно там, где абсолютная точность не постоянна: различить десять и одиннадцать точек примерно так же трудно, как сто и сто десять. Отсюда и правило, что ошибка оценки количества растёт пропорционально числу.
Fechner, Elemente der Psychophysik, 1860
Зевок, ошибка внимания
Ход, проигрывающий сразу и по причине, которую сам игрок способен объяснить через секунду после. Зевок отличается от ошибки: ошибка требует разбора, зевок — только внимания. Машины не зевают, у них нет усталости и нет момента, когда взгляд соскользнул мимо нужной линии.
Итеративное углубление
Считать сначала на два полухода, потом на три, потом на четыре, и так пока не кончится время. Кажется расточительным, но последний слой дерева и так больше всех предыдущих вместе. Зато ответ есть в любой момент, и порядок ходов от прошлого прохода ускоряет следующий.
Книга дебютов
Список начальных ходов, заготовленный заранее, обычно людьми и по человеческим партиям. Пока позиция есть в книге, программа не считает вообще — она вспоминает. Это единственное место, где в игре машины прямо присутствует чужой опыт, и именно поэтому AlphaZero от книги отказалась.
Мельница, три в ряд
Три свои фишки в ряд по линии доски. За мельницу снимают одну чужую фишку с доски. Смысл названия в том, что ряд можно размыкать и смыкать снова: каждое новое замыкание — ещё одна снятая фишка, и такая мельница мелет, пока сопернику есть чем платить.
Отравленная пешка
Пешка, которую можно взять, но брать не следует: расплата приходит через несколько ходов. Классическая проверка на глубину — программа с коротким горизонтом берёт материал и гибнет. Человек чаще не берёт, потому что видел это раньше, а не потому что посчитал.
Оценочная функция
Число, которым программа заменяет то, чего не досчитала. Материал, подвижность, безопасность короля, структура — всё сводится к одной величине на листе дерева. Здесь и живут человеческие представления об игре, включая ошибочные: перебор точен, оценка всегда приблизительна.
Поиск по дереву Монте-Карло
Вместо полного перебора программа много раз доигрывает партию до конца случайными или почти случайными ходами и наращивает дерево там, где результаты обнадёживают. Оценочная функция не нужна — оценкой служит статистика доигрышей. Именно этот метод сдвинул го с мёртвой точки и позже лёг в основу AlphaGo.
Coulom, Computers and Games, 2006
Поиск покоя
Ответ на эффект горизонта. Дойдя до предела глубины, программа не останавливается сразу, а досматривает взятия и шахи, пока позиция не станет спокойной, и только тогда её оценивает. Оценивать полагается одну тишину: посреди размена любая оценка врёт на целую фигуру.
Полуход, единица глубины
Ход одной стороны. То, что в шахматной записи считается одним ходом, для программы — два полухода. Единица глубины перебора измеряется именно в них, и от неё зависит всё: каждый лишний полуход умножает работу примерно на число доступных ходов в позиции.
Правило минимакса
Правило выбора хода: считать, что соперник ответит наилучшим для себя образом, и брать вариант, где худший исход всё равно приемлем. Не оптимизм и не осторожность, а предположение о безошибочном противнике. Против ошибающегося человека это часто оказывается слишком скромно.
фон Нейман, Mathematische Annalen, 1928
Рабочая память
Не склад, а рабочий стол: то, с чем вы прямо сейчас производите действия. Хранение и обработка делят один ресурс, поэтому удерживать и одновременно преобразовывать дороже, чем просто удерживать. Тесты на объём и тесты на обновление меряют разные стороны и дают разные числа.
Baddeley & Hitch, Psychology of Learning and Motivation, 1974
Рейтинг Эло
Шкала, где разница в четыреста пунктов означает примерно десятикратный перевес в ожидаемом счёте. Абсолютного значения у числа нет: оно меряет только соотношение внутри одного пула игроков. Поэтому рейтинг движка и рейтинг человека нельзя просто вычесть друг из друга.
Elo, The Rating of Chessplayers, Past and Present, 1978
Самоигра, игра с собой
Обучение на партиях с самим собой. Соперник всегда ровно такой же силы, как ты, поэтому сложность растёт вместе с умением и человеческие партии не нужны. Метод старше нейросетей: так училась программа Сэмюэла в пятидесятых и TD-Gammon в девяностых.
Слепота к изменению
Неспособность заметить крупную перемену в сцене, если момент перемены замаскирован: пустым кадром, морганием, движением глаз или проехавшей дверью. Перемена полностью видна, но не попадает во внимание. Отсюда следует, что подробная картина мира в голове не хранится, а собирается по требованию.
Rensink, O'Regan & Clark, Psychological Science, 1997
Субитизация, счёт без счёта
Мгновенное определение количества без счёта. Работает до трёх-четырёх объектов: ответ приходит сразу, точно и почти без усилия. Дальше включается другой механизм — приблизительная оценка с ошибкой, растущей вместе с числом. Границу между ними видно по времени ответа.
Kaufman et al., American Journal of Psychology, 1949
Таблица транспозиций
К одной и той же позиции ведут разные порядки ходов. Программа хранит уже посчитанные позиции в большой таблице и, встретив знакомую, берёт готовый ответ вместо повторного перебора. Дерево от этого превращается в граф, и работы становится заметно меньше.
Темп, единица опережения
Единица опережения: кто вынужден раскрываться первым. Темп не материал, его не видно в числе фишек, и тем не менее он часто решает партию. В «точках и квадратах» темпом управляют напрямую: отдав два квадрата, вы покупаете право заставить соперника вскрыть цепочку.
Цугцванг, обязанность ходить
Положение, в котором любой ход ухудшает вашу позицию, а права пропустить ход нет. Проигрывает не позиция, а обязанность ходить. В ниме это состояние описано точно: из позиции с нулевым исключающим ИЛИ любой ход ведёт в проигранную, и обойти это нельзя.
Эндшпильная база
Таблица, где для каждой позиции с малым числом фигур записан точный результат и число ходов до него. Строится обратным счётом: от матовых позиций назад. Программа здесь не оценивает и не ищет, а читает готовый ответ — единственный участок доски, закрытый окончательно.
Thompson, ICCA Journal, 1986
Эффект горизонта
Программа считает на конечную глубину, и всё, что случится за ней, для неё не существует. Неприятность можно отодвинуть за горизонт бессмысленными шахами — и позиция покажется хорошей. Беда не в том, что машина ошиблась в оценке, а в том, что оценивать было нечего.
Эффект Струпа
Назвать цвет чернил труднее, если слово означает другой цвет. Задержка — около ста миллисекунд, и она устойчива: чтение у грамотного взрослого запускается само и не отключается по желанию. Автоматизм, который экономит вам время всю жизнь, здесь работает против вас.
Stroop, Journal of Experimental Psychology, 1935