Что вижу - о том пою (aragont) wrote,
Что вижу - о том пою
aragont

Category:

Спичечный компьютер

Давным-давно на Гиктаймз опубликовали статейку про компьютерное обучение на примере игры в спички. Статья была глупая и без картинок. Я решил немного напрячься и написать свой вариант.

Итак, есть игра в спички. Играющие берут из кучки в 11 спичек либо одну, либо две спички за раз. Тот, кто берёт последнюю - выигрывает. Наша задача - научить играть в эту игру компьютер.

Если позиция в игре известна обоим игрокам, правила не допускают ничью и в них нет случайности вроде бросания костей, то можно доказать, какой из игроков выиграет при правильной тактике - первый или второй. К сожалению, такое доказательство может ничего и не говорить о том, какая тактика правильная. Просто известно, что она есть, и всё.

Сразу скажу, что в нашей игре преимущество у первого игрока.

Для начала, можно нарисовать все возможные варианты ходов и посмотреть, что получится. Цепочки ходов в игре 11 спичек слишком длинные. Я попытался нарисовать игру попроще - в 5 спичек, но всё равно получилось сложновато.

На диаграмме для каждого хода левее нарисованы ходы со взятием одной спички, а правее - двух. Зелёным отмечены победы первого игрока, а красным его проигрыши. Цепочек получилось слишком много, поэтому часть левой ветки я заменил многоточием.

game5

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

Первый вариант математический:

Попробуем перерисовать схему. Стрелки вправо - это взятие двух спичек, вниз - одной. Тонкие стрелки - ходы первого игрока, толстые - второго.

game5-tab

Быстрый просмотр новой схемы показывает, что если первый игрок начнет игру с двух спичек, то он наверняка выиграет, а если с одной, то как повезёт. Кроме того, на короткой выигрышной ветке можно заметить закономерность выигрышных ходов - надо делать ходы, противоположные ходам противника. Он берёт две, я - одну, и наоборот.

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

Второй вариант больше программистский:

Если явная формула на ум не приходит, или правила игры слишком сложны, то специалисты по машинному обучению начинают моделировать на компьютере игру за игрой, постепенно вычеркивая, заведомо проигрышные варианты. (В качестве примера сложных правил могу предложить: спичек мильон, и на каждом ходу можно брать от одной спички, до остатка от умножения номера хода на 2677 и деления на 127 - в общем, вспоминаем "драконий покер").

Вот тут я вернусь к игре 11 спичек и покажу, что самообучающийся компьютер может быть очень прост.

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

s00

У меня всегда начинает компьютер (в этой игре начинающий всегда может выиграть). Его ход определяется бросанием монетки - орел = две спички, решка = одна спичка. После бросания монетки в табличке выбора ходов фишкой помечают клетку, соответствующую текущему количеству спичек на столе и выпавшему выбору (ну, и снимают нужное количество спичек). Если этот ход компьютера приведёт к поражению, то станет понятно, что выбор был неправильным. В этом случае мы поставим в клетке с фишкой жирный крест. Играя в следующий раз в позиции, в которой один вариант помечен как проигрышный, мы уже не будем кидать монетку, а сразу выберем второй вариант.

Поражением компьютера считаются три ситуации:
1. Если после следующего хода человека на столе не останется спичек;
2. После хода человека мы окажемся в позиции, в которой оба варианта выбора помечены крестами. Такая позиция означает, что мы уже попробовали оба варианта и оба раза проиграли;
3. Компьютер на последней спичке попытается взять две. Это чисто программисткое правило. Можно было сразу нарисовать дополнительный крестик в левой колонке, но программисты предпочитают, чтобы всю работу за них делал компьютер.

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

Маленькое замечание. Этот компьютер обучается чему-либо новому только в том случае, когда проигрывает. Если вы будете ему поддаваться, то таблица останется чистой и ничего интересного не получится. Чтобы исключить влияние человеческого фактора на этапе обучения компьютер заставляют играть самого с собой. В этом случае монетка кидается и за компьютер и за человека.

Чтобы сделать объяснения нагляднее я отснял три игры. Итак, начнем.

Компьютер выбросил решку и взял одну спичку
s01

Человек взял две спички
s02

Компьютер выбросил орла и взял две спички
s03

Человек взял одну спичку
s04

Компьютер выбросил орла и взял две спички
s05

Тут у меня ошибка, компьютер сходил второй раз подряд и взял ещё одну спичку. К счастью, на обучение компьютера такие ошибки не влияют, более того - при игре компьютера с собой скорость обучения повышается вдвое.
s06

Человек взял две спички и компьютер проиграл.
s07

Снимаем фишку и ставим на её месте крестик.
s08

Начинаем вторую партию.

Я пропустил начало игры и дошёл до ситуации, когда компьютер снял одну спичку (помечено фишкой) и человек снял одну спичку.
s11

Поскольку в колонке стоит один крестик, то у компьютера нет выхода и он без кидания монеты берёт две спички.
s12

Человек снова выигрывает, а мы снова ставим крестик.
s13

Третья игра.

Компьютер снял одну спичку.
s21

Человек снял одну спичку и загнал компьютер в позицию с двумя крестами.
s22

Компьютер сдаётся, а мы рисуем очередной крестик.
s23

Надеюсь, что теперь правила обучения компьютера вам понятны. Успехов вам в выращивании собственного Искусственного Интеллекта!

З.Ы.
Первые две картинки нарисованы в очень удобной бесплатном редакторе диаграмм Dia. Часть монеток на фотографиях переклеены в столь же бесплатном графическом редакторе Gimp.
Tags: математика, программы
Subscribe

  • Некарательная психиатрия

    Раз в несколько лет меня, как преподавателя, отправляют на освидетельствование у психиатра, а в последний раз дополнительно отправили на…

  • О победителях и побеждённых

    На канале Discovery идёт передача про самодеятельных историков, которые занимаются исследованием остатков укреплений Второй мировой войны. Ведущий:…

  • Наглядные расстояния

    В старших классах школы я жил с родителями на углу Свердлова и Быкова (нынче ул. Братьев Быковых, Екатеринбург). Как-то, на выходе из двора, отец…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment