nlothik (nlothik) wrote,
nlothik
nlothik

Category:

Интересное математическо-игровое

Если есть возможность научить компьютер что-то делать — он это будет делать намного лучше человека. В том числе — и играть в игры.

Большинство игр типа шашек, шахмат, домино и даже крестиков-ноликов компьютер играет через постройку дерева решений. Для крестиков-ноликов это вполне тривиальная задача, так как количество возможных игр в крестиках-ноликах равно факториалу 9 или примерно 363 тысячам. Для современных компьютеров это ерунда. Шашки уже посложнее — там 500 квинтиллионов (500 000 000 000 000 000 000) возможных игр. И полное дерево решений для шашек таки было построено. Число возможных игр в шахматах же несколько превышает… кгм… количество атомов в наблюдаемой Вселенной, поэтому с построением полного дерева ожидаемо возникает затык. Да и с шашками, вообще-то, тоже, так как 500 квинтиллионов поместятся далеко не во всякий компьютер 🙂 Ну, полное дерево, в принципе, и не нужно. Чтобы выиграть в шахматы, например, у меня, достаточно построить дерево ну хотя бы в четыре уровня, потому что я архихреново в них играю. Чтобы выиграть у гроссмейстера, понадобится дерево пошЫрше и поглЫбже; но это тоже не является проблемой — компьютер теперь с гарантией выигрывает у лучших в мире гроссмейстеров, тема, по сути, закрыта.

Но есть игры, не пользующиеся деревьями решений. Например, морской бой. По сути своей, задача выигрыша в морском бое состоит в поиске нужных данных по несортированному, случайному двоичному массиву. Казалось бы, если массив не сортирован и случаен, значит, оптимальной стратегии в морском бое нет. Но реальность немного интереснее 🙂

Чуваки из конторы DataGenetics провели математический разбор “Морского боя”:

http://www.datagenetics.com/blog/december32011/

Во-первых, выяснилось, что шахматное расположение обстрела совсем ненамного лучше абсолютно случайной стрельбы. Что лично для меня явилось сюрпризом — я полагал, что это сильно сокращает количество ненужных выстрелов.

Во-вторых, выяснилось, что оптимальная стратегия в морском бое таки есть. Так как в игре есть правила и логика, то вероятность расположения кораблей противника является вполне себе вычисляемой величиной. Нет смысла искать пятиклеточный авианосец промежду стреляных клеток, расположенных друг от друга на расстоянии в три клетки.

И что характерно, рассчитать карту плотностей вероятностей у компьютера получается значительно лучше человека.

Карта плотностей вероятностей на 12 ходу после 5 попаданий:

Хотя люди тоже пользуются примерно такой же стратегией — статистически компьютер всё же будет выигрывать. Вот такие пироги с кремниевыми котятами.

Mirrored from Лабораторный Журнал №6.

Tags: игры, интересное, компьютерное, математика
Subscribe

  • Платить преступникам за несовершение преступлений

    Запасаемся попкорном. Мне почему-то кааца, что на преступность это не повлияет от слова “никак”. Да, кстати, а почему мне не платят?…

  • Мир дико тесен

    В ЖЖ есть интересный человек Михаил Шифман, преподаватель теоретической физики в университете Миннисоты, лауреат многочисленных наград. Он часто…

  • Запрет на выселение

    Я чего-то не понимаю. Администрация Бидон Бидоныча в очередной раз продлила запрет на выселение неплатящих аренду жильцов. Момент раз: попробуйте…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments

  • Платить преступникам за несовершение преступлений

    Запасаемся попкорном. Мне почему-то кааца, что на преступность это не повлияет от слова “никак”. Да, кстати, а почему мне не платят?…

  • Мир дико тесен

    В ЖЖ есть интересный человек Михаил Шифман, преподаватель теоретической физики в университете Миннисоты, лауреат многочисленных наград. Он часто…

  • Запрет на выселение

    Я чего-то не понимаю. Администрация Бидон Бидоныча в очередной раз продлила запрет на выселение неплатящих аренду жильцов. Момент раз: попробуйте…