3.3.6 Решения разных игр
Для многих более простых игр слабые (а иногда даже сильные) решения обнаружились без привлечения машин. Например, для игры «магараджа» (или «магараджа и сипаи»), где чёрные имеют набор обычных шахматных фигур, а белые — единственную фигуру «магараджа», способную ходить и как ферзь, и как конь, было доказано, что при правильной игре чёрным гарантирована победа. Ещё до появления компьютеров люди смогли решить и ним, и крестики-нолики, однако последние достижения в области решения игр людям без помощи машин были бы явно не под силу. Например, 29 апреля 2007 г. команда исследователей из Университета Альберты (Канада) под руководством Джонатана Шеффера смогла достичь слабого решения для английских шашек, по правилам которых шашки не бьют назад, а дамки могут ходить лишь на соседние по диагонали поля, но в любую сторону.
Английские шашки — самая большая из игр, решённых до настоящего времени. Размер её поискового пространства (т. е. количество легальных позиций) — примерно 5 × 1020. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (в разное время от 50 до 200) произвела 1014 вычислений.
Исследователям удалось найти решения для весьма внушительного списка игр, в который, в частности, входят «четыре в ряд», фанорона, вари (оваре), калах, шахматные поддавки (белые выигрывают, начиная игру ходом пешки на поле e3), ним, пентаго, баг-чал («тигры и козы»), кварто, тееко и множество других игр, о существовании которых я узнал, когда писал этот абзац.
Последней решённой игрой на данный момент стала пентаго. В отличие от шахмат и го поисковое пространство этой игры небольшое, что позволяет современному компьютеру играть идеально: с учётом всех возможных симметрий количество возможных позиций в пентаго составляет 3 009 081 623 421 558. В течение нескольких часов суперкомпьютер Edison семейства Cray, находящийся в Национальном научно-вычислительном центре энергетических исследований (NERSC), используя для вычислений целых 98 304 потока, нашёл сильное решение игры.