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

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

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

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

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

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

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

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

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

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

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