Альфа-бета отсечение
Оптимизация минимакса, которая пропускает ветви, заведомо не влияющие на результат: ответ тот же, работы в разы меньше.
Поиск несёт две границы: альфа — лучший результат, который вам уже гарантирован, и бета — лучший, который уже гарантирован противнику. Как только выясняется, что ветка хуже найденной ранее альтернативы, остальное можно не разбирать: противник всё равно не позволит вам туда попасть. Ответ при этом точно такой же, как у полного минимакса.
К идее независимо пришло несколько групп в 1950-х, а Дональд Кнут и Рональд Мур разобрали её в 1975 году: при идеальном порядке ходов просматривается примерно квадратный корень от числа узлов, что на практике удваивает достижимую глубину. Поэтому шахматные движки так стараются перебирать самые вероятные ходы первыми, нередко с помощью транспозиционной таблицы. Deep Blue строился на том же принципе.