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

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

Теперь вопрос. Как бы этого наблюдателя научить делать предположения систематически, чтобы предположений было не очень много, а каждый шахматный ход какое–то из них либо усиливал, либо ослаблял? Дать каждой фигуре отдельное имя, и предполагать существование маршрута? Дать имя каждому квадрату три–на–три и предполагать присутствие в нём определённых фигур в заданные моменты времени? Считать контрольные суммы ценности фигур на каждой вертикали и горизонтали?
Красивых идей пока нет.

GD Star Rating
loading...
Tagged with →  

32 Responses to Как бы научить этого наблюдателя ?

  1. Zvnamore:

    Я не специалист по этому вопросу, но вот мои мысли на сей счёт:

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

    Сможет ли он восстановить все официальные правила? Рассудим: количество возможных комбинаций положения фигур на доске и их перемещений конечно; значит, при достаточном объёме наблюдений будут установлены все до одного правила их перемещений. Ситуации «можно, но незачем» предполагают, что иногда такой ход будет осуществляться, следовательно правило будет также восстановлено.

    Как научить наблюдателя делать предположения не просто перебором возможных ходов или не путём заглядывания в уже сыгранные партии? Сейчас, если мне память не изменяет, где–то на 23 хода просчитаны все возможные комбинации. Для начала нужно понять, чем обусловлен успех шахматной партии? У серьёзного противника есть только три варианта проиграть: совершить ошибку по невнимательности, сделать рисковых ход на удачу и последний вариант — выбрать проигрышную стратегию игры, которая приведёт к проигрышу на позднем её этапе. То есть, чтобы выиграть, наблюдатель должен реализовать одну из этих возможностей, или несколько. Рассчитывать на риск и на невнимательность нельзя, это вещи считай что непредсказуемые, значит, чтобы выиграть, он должен выбрать верную долговременную стратегию.

    Тогда задача будет следующей: как можно быстрее понять, какую стратегию выбрал противник, и выбрать стратегию собственной игры, которая сможет эффективно ей противостоять. Значит, нужно описать типы возможных стратегий и некие индикаторы, которые позволят судить о том, какая из них выбрана. Рассматривать для этого, скорее всего, нужно комбинацию ходов ключевых для той или иной стратегии фигур.

  2. Ilmig:

    да, интересно. То есть правила восстанавливаются с точки зрения цели игры. Стратегия первична, из ограничений стратегии следуют правила.

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

    Ок, думаю дальше… если честно, я надеялся на какую–то стратегию «без мысли». Чтобы возможные положения восстанавливались чистой статистикой, а о том, что у игры есть стратегия, наблюдатель даже не знал.

  3. Zvnamore:

    стратегия — тоже статистика, просто чуть более сложная. Два коня и ферзь выводятся вперёд — один кластер решений, пешки строятся в клинья — другой. Примерно так и будут описываться стратегии (на деле, конечно, сложнее). Шахматы — задача неинтересная, потому что всегда есть вариант просто взять, да и просчитать все возможные ходы. Думайте над Го — там недавно компьютер чудом выиграл у средней руки профессионала, и это большое событие 🙂

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

  4. Ilmig:

    ну и замечательно. Мне нужны именно недокументированные правила, по которым реально ездят.

  5. Zvnamore:

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

  6. Siratels:

    Если он и не МАТ на рокировке, то взятие на проходе ввергнет его в когнитивный диссонанс.

  7. 424:

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

  8. Ilmig:

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

    Почему не миллионы? Чтобы не было решений через исчерпывающее перечисление всех вариантов. Каких–то ходов в наблюдаемых данных может и не быть.

  9. Retemmho:

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

    //ну да, для эстетов: правила на три повторяющихся хода будем ждать еще игр двести, не меньше, но это в общем–то дела не меняет.

  10. Ilmig:

    ну это человеку хватит. А компьютер как этому научить?

  11. Tavav:

    а компьютер сам учиться будет? или человек его будет учить? «посторонний наблюдатель, совершенно не знакомый с настольными играми вообще» это компьютер?

  12. Ilmig:

    да. Это компьютер, максимум — при участии человека, который будет отвергать некоторые, совсем дикие окончательные ответы.

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

  13. Nortisop:

    Казалось бы, причём тут Ноам Хомский…

  14. 424:

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

  15. Retemmho:

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

  16. Ilmig:

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

  17. Erodelbr:

    Казалось бы, причём здесь нейронные сети.

  18. Peels:

    1) Задача обучения без предварительных знаний о системе в общем виде неразрешима.
    Это значит, что если твой компьютер будет рассматривать шахматную доску как тупо конфигурацию фигур без какой–либо структуры (а–ля «конфигурация номер 1, конфигурация номер 2, итд»), и следить за изменениями этой конфигурации («из конфигурации номер 1 получили конфигурацию 4»), то, хотя он может выучить те изменения, которые он видел, он не сможет «понять» всю игру (т.е. научиться отличать корректные ходы от некорректных). Может звучит банально, но не будем об этом забывать. Поэтому хочешь — не хочешь, а компьютеру придется «подсказать», задав ему некий «настрой обучения».

    2) Если ты дашь компьютеру подсказку вида «конфигурация состоит из фигур, находящихся на клетках» (т.е. теперь компьютер будет видеть запись каждой позиции в терминах фигур), а так же укажешь, что «правила игры простые» (т.е. компьютер может предположить, что описание возможных ходов должно быть по возможности без исключений) то этого по идее уже должно быть достаточно, чтобы статистически выучить по достаточно небольшому набору все основные правила. Сложности действительно возникнут для «пешки на проходе» и других редких конфигураций, ибо если компьютер видел всего два примера взятия на проходе сложно сказать какое обобщение «проще» — предположить что только эти два взятия возможны только в такой ситуации, или что вообще есть целое правило что, мол, любая пешка может брать на проходе. Тут все зависит от того, как ты определишь понятие «просто».

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

  19. Zvnamore:

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

  20. Zvnamore:

    Поделюсь с вами ещё одним наблюдением из казалось бы другой области. Вот есть теорема Ферма, уже пятнадцать лет как доказанная Уайлсом. Формулируется теорема на уровне, доступном ученику средней школы: показать, что в целых числах нет решений для уравнения a*+b*=c* для * больше двух. Казалось бы, правила тут примитивные — возведение в степень есть просто умножение числа на само себя, а умножение как таковое сводится к сложению, и речь у нас идёт только о целых положительных числах. Доказательство великой теоремы Ферма занимает несколько сотен страниц концентрированного текста, под него, фактически, были созданы целые новые области математики. Количество «ходов», нужных для выигрыша в этой «партии» — доказательстве теоремы, всего на пару порядков больше среднего числа ходов шахматной партии. При этом машинного доказательства великой теоремы Ферма до сих пор нет, к нему даже не приблизились, хотя постановка задачи понятна и логична, более того, известно, что есть верное решение. Но все современные компьютеры и программисты тут бессильны — не может пока компьютер построить автоматически такое доказательство, хотя правила игры очень простые.

  21. 424:

    во–первых, есть доказанные наборы фигур при которых мат поставить невозможно для обеих сторон — в этом случае присуждается ничья, а часто еще до того. Ну и есть формулы очевидного материального перевеса, когда партию продолжать тоже бессмысленно. Вообще в более–менее профессиональной игре доводить до последнего хода считается просто неуважением, всегда исход ясен хотя бы за 2–3. В таких партиях определить конечную цель игры сложнее, но тоже возможно.

  22. Zvnamore:

    только если остаются король и одна лёгкая фигура нельзя мат поставить. «Исход ясен» — это очень условно. Тут у нас на наукаблоге была где–то ссылка на видео, в котором на турнире высокого уровня по Го один из игроков в эндшпиле не туда поставил фишку, проиграв при этом уйму очков. В шахматах такие ошибки тоже бывают, причём особенно в быстрых партиях, то есть учить компьютер по недоигранным партиям с «понятным» результатом — это учить его не учитывать возможность ошибки.

  23. 424:

    ага, или вообще нет лёгких фигур. А если две пешки вот–вот пройдут в ферзи — то можно. А двумя конями — нельзя. Короче, не всё так просто как кажется.
    И причём тут вообще Го? Предлагаю набрать современных реальных шахматных партий, и посчитать в скольких игра доведена до мата.

  24. 424:

    нет, современная самообучающаяся система может выделить фигуры и понятие их перемещений. Это вообще несложно, учитывая что две соседних «конфигурации» всегда отличаются перемещением одной фигуры.

  25. Zvnamore:

    при рокировке перемещаются две фигуры за 1 ход. Причём перемещаются так, как по правилам ходить в принципе не могут.

  26. 424:

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

  27. Zvnamore:

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

  28. 424:

    единственное исключение, что сложного в его быстром нахождении?

  29. Zvnamore:

    ничего, ровным счётом.

  30. Peels:

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

    Если ты предоставишь системе описание конфигураций в каком–либо другом формате (ну, например, жпег картинками), она не сможет «выучить» правила даже с очень большим набором данных.

  31. Peels:

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

    Описание такого правила вполне может оказаться «проще» чем полное описание правила рокировки («король может … только один раз … если не ходил … если поля не под ударом …»), и в то же время оно может прекрасно подходить под все наблюдаемые партии.

  32. Ilmig:

    ну и зашибись, стопроцентная точность не нужна.
    Если я сформулирую задачу как «научить компьютер генерировать шахматные партии, издалека похожие на настоящие» — будет проще?

    Кстати, спасибо всем участникам. Я пока додумался до следующей мысли.
    Попросить компьютер оценить расстояние от позиции на ходу N до позиции N+1. Т.е. считать ход разрещенным, если получившаяся позиция не слишком «далеко» от предыдущего. А что такое «далеко»? Вот для этого и нужна тысяча и более примеров. Пусть компьютер создаст целую семью версий понятия расстояние, а потом оценит — какие его «расстояния» действительно были малы между ходами в реальных партиях.

Добавить комментарий