Category: математика

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

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

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

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

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

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

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

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

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

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

Боль­шин­ство моих ЖЖ-дру­зей, навер­ное, в кур­се, что это, и как это рабо­та­ет. Но вдруг кто не зна­ет или не пони­ма­ет.

Самое глав­ное в блок­чейне — это функ­ция одно­сто­рон­не­го шиф­ро­ва­ния, часто назы­ва­е­мая хеш-функ­ци­ей. Одно­сто­рон­нее шиф­ро­ва­ние созда­ёт из бло­ка дан­ных шифр-текст (хеш) опре­де­лён­ной дли­ны, кото­рый невоз­мож­но рас­шиф­ро­вать назад без тупо­го пере­бо­ра всех воз­мож­ных изна­чаль­ных вари­ан­тов. Про­ще все­го думать о хеше как об циф­ро­вом отпе­чат­ке паль­цев. Люди вон какие раз­ные — и по росту, и по цве­ту глаз, волос, и про­че­го, а отпе­чат­ки паль­цев — это их хеш, уни­каль­ный для каж­до­го инди­ви­ду­у­ма.

Если два экс­пер­та про­ве­дут дак­ти­ло­ско­пи­ро­ва­ние одно­го и того же чело­ве­ка, они полу­чат (во вся­ком слу­чае, долж­ны) оди­на­ко­вый резуль­тат. Так и с ком­пью­те­ра­ми — если два чело­ве­ка будут исполь­зо­вать один и тот же алго­ритм хеши­ро­ва­ния на одном и том же набо­ре дан­ных, они долж­ны полу­чить один и тот же хеш. То-есть, если у тебя есть кусок тек­ста, и у меня есть кусок тек­ста, мы его хеши­ру­ем одним и тем же алго­рит­мом, и у нас полу­ча­ет­ся оди­на­ко­вый хеш — это зна­чит, что кус­ки тек­ста, кото­рые мы ана­ли­зи­ро­ва­ли, 100% иден­тич­ны (1).

Теперь постро­им свой соб­ствен­ный при­ми­тив­ный блок­чейн. Блок­чейн — это block chain, т.е. цепь из бло­ков. Каж­дым бло­ком внут­ри нашей цепи будут 5 кус­ков тек­ста, раз­де­лён­ных запя­ты­ми: хеш преды­ду­ще­го бло­ка, три кус­ка «полез­ной нагруз­ки», и хеш для это­го бло­ка. Хра­нить в блок­чейне мож­но любые дан­ные, но допу­стим у нас будет хра­нит­ся инфор­ма­ция о финан­со­вых тран­зак­ци­ях. Исполь­зо­вать будем алго­ритм хеши­ро­ва­ния MD5 (2)

Постро­им пер­вый блок. Так как это началь­ный блок в цепи бло­ков, у него не может быть хеша преды­ду­ще­го бло­ка. Ну и пле­вать, при­ду­ма­ем свой. abcdefghijklmopqrstuvwxyz1234567 — вполне сго­дит­ся. Далее ука­зы­ва­ем тран­зак­цию, кто кому запла­тил, и сколь­ко: Маша,Олег,5 руб­лей. И хеши­ру­ем всё это вме­сте:

md5sum «abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 руб­лей», полу­ча­ем хеш a61d142c8be7fac8b41da05d11c9f76e.

Всё, вот пер­вый блок в нашем блок­чейне:

abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 рублей,a61d142c8be7fac8b41da05d11c9f76e

Стро­им вто­рой блок, где Серё­жа запла­тил Тане 3 руб­ля:

md5sum «a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 руб­ля», полу­ча­ем хеш 20e22c43963d6ee9bbc71d65c4251492, и, соот­вет­ствен­но, блок:

a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 рубля,20e22c43963d6ee9bbc71d65c4251492

И теперь наш блок­чейн выгля­дит так:

abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 рублей,a61d142c8be7fac8b41da05d11c9f76e
a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 рубля,20e22c43963d6ee9bbc71d65c4251492

Ну, и так далее, бло­ков мож­но добав­лять до окон­ча­ния места на жёст­ком дис­ке.

Чем это кру­то? Тем, что блок­чейн лежит в сво­бод­ном досту­пе, и ЛЮБОЙ чело­век, взяв этот блок­чейн, может соб­ствен­но­руч­но пере­вы­чис­лить все хеши и про­ве­рить все запи­си: если хеши сов­па­да­ют, зна­чит, инфор­ма­ции мож­но дове­рять. Имен­но этим и зани­ма­ют­ся май­не­ры — они пере­про­ве­ря­ют тран­зак­ции для крип­то­ва­лют, то-есть, обес­пе­чи­ва­ют функ­ци­о­ни­ро­ва­ние пла­тёж­ной систе­мы, за что им отстё­ги­ва­ют денег.

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

1. 100% гаран­тии, разу­ме­ет­ся, быть не может, но если алго­ритм шиф­ро­ва­ния нор­маль­ный и не име­ет кол­ли­зий (это когда два раз­ных набо­ра дан­ных дают один и тот же хеш), то веро­ят­ность сов­па­де­ния будет при­мер­но 1/количество воз­мож­ных хешей, т.е. для хеша дли­ной 128 бит это 2.94E-39, или пре­не­бре­жи­тель­но мало. Для хеша дли­ной 512 бит это вооб­ще чис­ло со 150+ сим­во­ла­ми после деся­тич­ной точ­ки.
2. Алго­ритм хеши­ро­ва­ния MD5 доста­точ­но хре­но­вый по совре­мен­ным мер­кам, и име­ет кол­ли­зии. Прав­да, для реаль­но чита­е­мо­го чело­ве­ком тек­ста мож­но пре­не­бречь — все суще­ству­ю­щие при­ме­ры кол­ли­зий это хеши спе­ци­аль­но сге­не­ри­ро­ван­ных дво­ич­ных дан­ных. Но в реаль­но рабо­чих при­ло­же­ни­ях, тем не менее, реко­мен­ду­ет­ся исполь­зо­вать более кол­ли­зи­он­но­устой­чи­вые алго­рит­мы, типа SHA-256 (исполь­зу­ет­ся в блок­чейне для бит­ко­и­на) или SHA‑3.

Отку­да в циф­ро­вом зву­ке берёт­ся шум? Он берёт­ся из не вполне точ­но­го пред­став­ле­ния ана­ло­го­во­го сиг­на­ла, так как для того, что­бы опи­сать сину­со­и­ду, у нас име­ет­ся конеч­ное коли­че­ство коор­ди­нат по оси Y. В слу­чае с ком­пакт-дис­ка­ми это 65536 воз­мож­ных зна­че­ний, так как у нас есть 16 бит — 15 бит на опи­са­ние уров­ня плюс один бит на знак. 8‑битные зву­ко­вые фай­лы, кста­ти, без­зна­ко­вые (во бар­дак!) Ось Х про­бле­мы не пред­став­ля­ет, в пол­ном соот­вет­ствии с тео­ре­мой Най­к­ви­ста-Шен­но­на-Котель­ни­ко­ва

Зави­си­мость в деци­бе­лах отно­ше­ния сигнал/шум от того, каким коли­че­ством уров­ней опи­сы­ва­ет­ся сиг­нал, линей­ная, и рас­счи­ты­ва­ет­ся как 20log₁₀(2^{коли­че­ство бит}), или при­мер­но 6.02 × коли­че­ство бит.

Стой­кие апо­ло­ге­ты ана­ло­го­вых носи­те­лей напи­ра­ют на то, что, мол на циф­ро­вом носи­те­ле все­го 65536 уров­ней, а на нашем-то тёп­лом лам­по­вом вини­ле (или на маг­нит­ной плён­ке) коли­че­ство уров­ней ана­ло­го­вое, т.е. неогра­ни­чен­ное!!! Ага, ага. А вот хрен вам. С ана­ло­го­во­го носи­те­ля точ­но так же мож­но достать конеч­ное коли­че­ство уров­ней сиг­на­ла, и для хоро­ше­го «доре­во­лю­ци­он­но­го» вини­ла это чис­ло состав­ля­ет при­мер­но 2000 или 11 бит. Это даст пре­дель­ное отно­ше­ние сигнал/шум в рай­оне 70 дБ — что, вооб­ще-то, не так уж пло­хо. Это замет­но луч­ше MP3-шек, напри­мер =))) Толь­ко винил надо хоро­шень­ко помыть-почи­стить, что­бы не было слыш­но пыли — она силь­но пор­тит впе­чат­ле­ние.

В слу­чае с плён­кой уже надо гово­рить более пред­мет­но — тут смот­ря какая плён­ка. Наи­луч­шее каче­ство в домаш­них усло­ви­ях дава­ли кату­шеч­ные маг­ни­то­фо­ны — с них мож­но было тоже достать при­мер­но 11 бит. Кас­се­ты, когда толь­ко появи­лись, были пол­ное и окон­ча­тель­ное гов­но, и дава­ли где-то 6‑битный звук. Это­го было вполне доста­точ­но для при­ме­не­ния в дик­то­фо­нах (для коих, их, соб­ствен­но, и раз­ра­бо­та­ли), но недо­ста­точ­но для каче­ствен­но­го вос­про­из­ве­де­ния музы­ки. Тем не менее, их рас­ту­щая попу­ляр­ность и сопут­ству­ю­щие посто­ян­ные улуч­ше­ния в обла­сти элек­тро­ни­ки при­ве­ли к тому, что посте­пен­но они вышли на уро­вень кату­шеч­ных маг­ни­то­фо­нов, а с вве­де­ни­ем тех­но­ло­гий типа Dolby и про­чих улуч­шай­зе­ров, даже немно­го пре­взо­шли их (кату­шеч­ные маг­ни­то­фо­ны к это­му вре­ме­ни уже, ясен пень, никто не улуч­шал). Но — это при нали­чии хоро­шей кас­сет­ной деки, каче­ствен­ной сту­дий­ной ком­пакт-кас­се­ты, и т.д. А вос­хи­щать­ся ана­ло­го­вым носи­те­лем МК-60, суну­тым в Элек­тро­ни­ку-302 мож­но раз­ве что после тре­тьей бутыл­ки.

Что име­ем с гуся? С гуся име­ем то, что ана­ло­го­вый носи­тель тоже, по сути, циф­ро­вой — коли­че­ство вытас­ки­ва­е­мой с него инфор­ма­ции конеч­но. Это для любо­го носи­те­ля спра­вед­ли­во — даже для 35mm фото­гра­фи­че­ской плён­ки. С неё — в иде­а­ле — мож­но достать 10 мега­пик­се­лей. Повто­рюсь — в иде­а­ле. Со сним­ков на совет­скую ч/б плён­ку сере­ди­ны 1960х годов я вытя­ги­вал при­мер­но 1 мега­пик­сель, не более.

Таки доде­лал про­грам­ку на Питоне, рису­ю­щую спектр сиг­на­ла и авто­ма­ти­че­ски счи­та­ю­щую КНИ+шум и ОСШ. Попут­но узнал, как водит­ся, мно­го ново­го. За что люб­лю Питон — так это за то, что про­грам­ма зани­ма­ет менее 40 строк. На тех же Сях я бы усрал­ся это рисо­вать. Даже на Шар­пах бы усрал­ся.

Про­грам­ме скарм­ли­ва­ет­ся зву­ко­вой файл с сиг­на­лом часто­той в 1 kHz, сге­не­ри­ро­ван­ный про­грам­мой Adobe Audition (в деви­че­стве Syntrillium CoolEdit). Но мож­но взять и бес­плат­ный Audacity, резуль­тат будет точ­но такой же. Про­грам­ма чита­ет файл, берёт зна­че­ние с наи­боль­шим пиком и даёт ему обо­зна­че­ние в 0 деци­бел. Осталь­ное, соот­вет­ствен­но, отри­ца­тель­ные вели­чи­ны. Под­счи­ты­ва­ет­ся сред­не­квад­ра­тич­ное зна­че­ние все­го, что не сиг­нал, и делит­ся на уро­вень сиг­на­ла. Полу­ча­ет­ся КНИ+шум (THD+N). Потом счи­та­ем ОСШ (отно­ше­ние сигнал/шум, SNR) в деци­бе­лах: 20log₁₀(сиг­нал / шум)

Вот так выгля­дит ана­лиз зву­ко­во­го фай­ла с сиг­на­лом 1 kHz, раз­ре­ше­ни­ем 16-бит, часто­та дис­кре­ти­за­ции — 48 kHz:

Это весь­ма близ­ко к тео­ре­ти­че­ско­му иде­а­лу — в иде­а­ле, раз­ре­ше­ние 16 бит может дать ОСШ в 96.3 dB. Но у меня не иде­ал, так как я исполь­зую чуть менее, чем 16 бит — ибо если гене­ри­ро­вать сину­со­и­ду с уров­нем в 0 dB (т.е. по-мак­си­му­му), то поче­му-то уже лезут нели­ней­ные иска­же­ния. Так что я создаю её с уров­нем в ‑0.1 dB, мини­маль­ным отступ­ле­ни­ем от мак­си­му­ма, кото­рое мне даёт делать Audition. В любом слу­чае, 94 dB — это дохре­на.

КНИ в 2 тысяч­ных про­цен­та это тоже пре­крас­но. Без при­бо­ров это­го никто нико­гда не уви­дит, иска­же­ния начи­на­ют быть слы­ши­мы­ми, когда уже вплот­ную при­бли­жа­ют­ся к 1%, хотя это силь­но зави­сит от того, что имен­но слу­ша­ем: если чистые сину­со­и­ды, то иска­же­ния начи­на­ют быть замет­ны­ми гораз­до рань­ше, а если в каче­стве тесто­во­го мате­ри­а­ла брать аль­бо­мы фиф­ти­сен­тов и про­чих, то там мож­но и 10% иска­же­ний не услы­шать. Что не озна­ча­ет, что аппа­ра­ту­ра, даю­щая КНИ в 0.05%, ничем не луч­ше аппа­ра­ту­ры, даю­щей 0.1% — она луч­ше; про­сто в реаль­но­сти уша­ми это­го ни один живой чело­век не услы­шит.

А теперь — сно­ва пнём фор­мат MP3 🙂 Никто как-то вот не заду­мы­ва­ет­ся о том, что они слу­ша­ют в тыся­че­дол­ла­ро­вых дере­вян­ных науш­ни­ках, под­клю­чён­ных к внеш­ним уси­ли­те­лям клас­са А за семь­сот дол­ла­ров, обе­ща­ю­щим КНИ в 0.00045%

А меж­ду тем это реа­лии MP3 с бит­рей­том в 192 килобита/сек:

А это — 320 килобит/сек:

Получ­ше, конеч­но, чем 192 kbps, но всё рав­но про­се­да­ние каче­ства очень нали­цо — про­ис­хо­дит серьёз­ное ужи­ма­ние дина­ми­че­ско­го диа­па­зо­на (я в кур­се, что ДД и ОСШ это не вполне одно и то же, но они свя­за­ны). На неко­то­ром мате­ри­а­ле (напри­мер, клас­си­че­ская музы­ка, обла­да­ю­щая боль­шим дина­ми­че­ским диа­па­зо­ном) это может быть очень замет­но. На 192 кило­би­тах так это точ­но замет­но, тихая пар­тия скрип­ки сопро­вож­да­ет­ся скре­же­том арте­фак­тов сжа­тия с поте­ря­ми — соб­ствен­но­уш­но, так ска­зать, слы­шал. Даль­ней­шее уве­ли­че­ние бит­рей­та после 320 килобит/с, кста­ти, уже ниче­го не даёт — ОСШ так и оста­ёт­ся в рай­оне 55 деци­бел.

Ещё надо будет попи­нать вини­ло­филь­ство и про­чее плён­ко­ло­же­ство, но это в дру­гой раз 🙂

По сове­ту ув. ny-quant попро­бо­вал исполь­зо­вать фор­му­лу x = r * x (1 — x) в каче­стве гене­ра­то­ра слу­чай­ных вели­чин. Одно­го пре­об­ра­зо­ва­ния мне пока­за­лось мало, так что делал два кря­ду.

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

Ну, как гри­ца, pics or it didn’t happen.

Резуль­тат исполь­зо­ва­ния функ­ции NumPy.random.random():

И резуль­та­ты, полу­чен­ные из двой­но­го при­ме­не­ния x = r * x (1 — x) с дву­мя раз­ны­ми зна­че­ни­я­ми r:

Вооб­ще — непло­хо, дол­жен при­знать.

Но если при­бли­зить и рас­смот­реть деталь­нее, ста­но­вит­ся замет­ной раз­ни­ца. Спра­ва — x = r * x (1 — x), сле­ва — NumPy.random.random()

Как вид­но, x = r * x (1 — x) чаще при­ни­ма­ет гра­нич­ные зна­че­ния, там мно­го бело­го и мно­го чёр­но­го, и мало серо­го. Из-за это­го, кажет­ся, что есть узо­ры, как на булат­ной ста­ли. Я не мате­ма­тик, но мне кажет­ся, что боль­шая рав­но­мер­ность явля­ет­ся жела­тель­ной.

Но вооб­ще — для такой про­стой фор­му­лы дол­жен при­знать, впе­чат­ля­ет.