Если есть возможность научить компьютер что-то делать — он это будет делать намного лучше человека. В том числе — и играть в игры.
Большинство игр типа шашек, шахмат, домино и даже крестиков-ноликов компьютер играет через постройку дерева решений. Для крестиков-ноликов это вполне тривиальная задача, так как количество возможных игр в крестиках-ноликах равно факториалу 9 или примерно 363 тысячам. Для современных компьютеров это ерунда. Шашки уже посложнее — там 500 квинтиллионов (500 000 000 000 000 000 000) возможных игр. И полное дерево решений для шашек таки было построено. Число возможных игр в шахматах же несколько превышает… кгм… количество атомов в наблюдаемой Вселенной, поэтому с построением полного дерева ожидаемо возникает затык. Да и с шашками, вообще-то, тоже, так как 500 квинтиллионов поместятся далеко не во всякий компьютер 🙂 Ну, полное дерево, в принципе, и не нужно. Чтобы выиграть в шахматы, например, у меня, достаточно построить дерево ну хотя бы в четыре уровня, потому что я архихреново в них играю. Чтобы выиграть у гроссмейстера, понадобится дерево пошЫрше и поглЫбже; но это тоже не является проблемой — компьютер теперь с гарантией выигрывает у лучших в мире гроссмейстеров, тема, по сути, закрыта.
Но есть игры, не пользующиеся деревьями решений. Например, морской бой. По сути своей, задача выигрыша в морском бое состоит в поиске нужных данных по несортированному, случайному двоичному массиву. Казалось бы, если массив не сортирован и случаен, значит, оптимальной стратегии в морском бое нет. Но реальность немного интереснее 🙂
Чуваки из конторы DataGenetics провели математический разбор “Морского боя”:
http://www.datagenetics.com/blog/december32011/
Во-первых, выяснилось, что шахматное расположение обстрела совсем ненамного лучше абсолютно случайной стрельбы. Что лично для меня явилось сюрпризом — я полагал, что это сильно сокращает количество ненужных выстрелов.
Во-вторых, выяснилось, что оптимальная стратегия в морском бое таки есть. Так как в игре есть правила и логика, то вероятность расположения кораблей противника является вполне себе вычисляемой величиной. Нет смысла искать пятиклеточный авианосец промежду стреляных клеток, расположенных друг от друга на расстоянии в три клетки.
И что характерно, рассчитать карту плотностей вероятностей у компьютера получается значительно лучше человека.
Карта плотностей вероятностей на 12 ходу после 5 попаданий:
Хотя люди тоже пользуются примерно такой же стратегией — статистически компьютер всё же будет выигрывать. Вот такие пироги с кремниевыми котятами.
