Д.Ф. Бил [89] и Дана Hay [1113], [1114] изучали недостатки минимаксного поиска, касающиеся приближенных оценок. Они показали, что при некоторых предположениях о независимости распределения листовых значений в дереве применение минимаксного поиска может привести к получению таких значений для корня, которые фактически являются менее надежными, чем полученные с помощью непосредственного использования самой функции оценки. В книге Перла Heuristics [1188] дано частичное объяснение этого кажущегося парадокса и приведен анализ многих алгоритмов ведения игр. Баум и Смит [83] предложили заменить алгоритм минимаксного поиска алгоритмом, основанном на учете вероятностей, и показали, что он приводит к осуществлению лучших вариантов выбора в некоторых играх.

Но объем теоретических результатов исследования влияния останова поиска на разных уровнях и применения функций оценки все еще остается недостаточным.

Алгоритм поиска на основе ожидаемого минимаксного значения был предложен Дональдом Мичи [1043], хотя, безусловно, он непосредственно следует из принципов оценки дерева игры, выдвинутых фон Нейманом и Моргенштерном. Брюс Бол-лард [65] распространил метод альфа-бета-отсечения на деревья с узлами жеребьевки. Первый успешно действующей программой игры в нарды была разработанная Берлинером программа BKG [104], [107]; в ней использовалась сложная, сконструированная вручную функция оценки, а поиск осуществлялся только на глубину 1. Это была первая программа, которая смогла победить чемпиона мира — человека в одной из основных классических игр [106]. По завершении соревнований Берлинер сразу же объявил, что это был очень короткий показательный матч (а не матч чемпионата мира) и что программе BKG очень повезло со жребием. Работа Герри Тесауро, приведшая вначале к созданию программы Neurogammon [1498], а затем TD-Gammon [1500], показала, что гораздо лучшие результаты могут быть достигнуты с помощью обучения с подкреплением. Эта тема будет рассматриваться более подробно в главе 21.

Первой из классических игр, полное решение которой было найдено компьютером, оказались не шахматы, а шашки. Кристофер Стрейчи [1469] написал первую работоспособную программу игры в шашки. Шеффер [1357] составил очень доступный отчет о разработке программы Chinook, ставшей чемпионом мира по шашкам, в котором все факты изложены "без прикрас".