27 февр. 2011 г.

Люди-переводчики

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

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

Когда перед человеком возникает задача, то он её сначала переводит с языка того, кто проблему ставит, на свой язык, чтобы понять её и выработать план решения. Поэтому лучше всего взаимодействие идёт между примерно равными людьми. Если же постановщик задачи и исполнитель очень далеки, то могут возникать неожиданные и сложные недопонимания (их даже бывает трудно обнаружить, так как люди совсем не понимают друг друга). По этой причине важно, чтобы тот, кто формулирует задачу, умел влезть в шкуру того, кто её будет выполнять. Мне кажется, что часто люди недовольны своим начальником именно из-за его неспособности или нежелания помочь с переводом задачи со своего языка на язык исполнителя. Орать на «идиотов вокруг» может каждый, а уметь внятно объяснить, чего надо делать - это обязательный навык для руководителя.

Я, например, обычно плохо понимаю, чего хотят бухгалтеры, врачи, таможенники... Они находятся в своём контексте, используют свой сленг, говорят противоречивые вещи. Доходит до смешного: буквально вчера сотрудница сауны не смогла нормально сказать, где зарезервированный мною номер. Она, махнув рукой в сторону стены с десятком одинаковых дверей, сказала: «Вон та дверь». Ей-то очевидно, какая именно дверь, потому что за некоторыми дверьми скрываются лестницы на другие этажи, за некоторыми находятся швабры и вёдра, а за какими-то уже парятся другие компании. А я всей этой информацией не владею, поэтому не могу понять, какая именно «та дверь» мне нужна... А она не способна понять, почему я не понимаю таких простых вещей.

Классический (пусть и не смешной) пример непонимания:
Человек повторно приходит к врачу, чтобы пожаловаться, что назначенные свечи от геморроя не помогают. «Уже по пачке в день ем, а толку никакого!» - зло говорит пациент. Врач очень удивляется, но на всякий случай переспрашивает: «Вы их ртом глотали?» Пациент злится ещё сильнее: «Нет, в задницу себе засовывал!»

Чему учат книжки о том, как стать успешным/богатым/стройным/сильным/уверенным/счастливым? Они учат, как правильно перевести с русского языка слово, например, «сильный» в примерно следующий набор смыслов: «каждое утро делать зарядку», «правильно питаться», «ложиться и просыпаться примерно в одинаковое время», «выполнять такие-то упражнения», «достаточное время отдыхать, чтобы организм восстанавливался», «продолжать всё это делать хотя бы пару месяцев, а не бросать через неделю, как большинство»...

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

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

Приведу пример, задачи, сформулированной в одной из книг Мартина Гарднера:

На столе рубашками вниз лежат девять игральных карт (одной масти, чтобы было проще): туз, 2, 3, 4, 5, 6, 7, 8, 9. Два игрока поочерёдно берут со стола одну карту и кладут в свою стопку. Выигрывает тот, у кого первого в стопке найдётся три карты, сумма чисел на которых составляет ровно 15 (будем считать, что туз - это единица). Вопрос у задачки вполне естественный: как правильно в это играть?

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

Хорошего вам окончания выходных дней!

37 комментариев:

  1. магический квадрат и крестики-нолики?

    ОтветитьУдалить
  2. Какая-то слишком элементарная задача.
    Тот, кто берёт первую карту, может и должен вынуждать второго брать определенные карты, чтобы не дать первому закончить игру. Соответсвенно алгоритм "подбирается" за несколько минут:
    Первый берет 6, второй вынужден взять 9
    Первый берет 7, второй не может взять 6, чтобы выиграть, но должен взять и 2 и 8.

    Как эту задачу можно "переводить" - не увидел :/

    ОтветитьУдалить
  3. Анонимный27.02.2011, 11:44

    Если внимательно читать условие, то задача уже не кажется такой элементарной ;) Выигрывает тот, у кого найдётся три карты, общей суммой в 15.

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

    ОтветитьУдалить
  4. to Denter:
    А почему он должен взять и 2, и 8? Пусть себе берет 8 - в сумме эти три числа не дадут 15. Вы, наверное, опустили какие-то очевидные для Вас следующие шаги.

    ОтветитьУдалить
  5. Тут дали крайне существенное уточнение - карт с суммой 15 должно быть ровно три (вообще подобная невнимательность с моей стороны непростительна :/ ).
    И это значит, что задачу действительно нужно переформулировать.
    Думаем дальше...

    ОтветитьУдалить
  6. Как только первый игрок взял первую карту, у него есть возможность добрать 15 очков только двумя другими картами.

    Допустим, он взял 5-ку. Тогда ему надо взять еще две карты общей суммой на 10. Таких вариантов много. Но как только он берет карту во второй раз, второму игроку нужно взять всего одну единственную карту, чтобы первый игрок не выиграл. И он, естественно, ее берет. Так что первый при любом раскладе выиграть не может.

    Рассмотрим теперь, может ли выиграть 2-й игрок. В партии первую карту второй игрок может брать какую угодно, выбор второй карты вторым игроком четко привязан к выбору второй карты первым игроком (т.е. если второй игрок обязан взять единственную карту, которая позволяет первому выиграть). Первый игрок должен выбрать третью карту. Теперь, когда он выиграть не может (второй игрок забрал нужную ему карту) его задача сводится к тому, чтобы помешать выиграть второму игроку. На столе может лежать только одна единственная карта, которая позволяет второму игроку победить, соответвенно, первый игрок при третьем вытягивании выбирает именно эту карту (если она еще есть на столе).

    Все, партия закончилась ничьей - ни один игрок при верной стратегии выиграть не может.

    ОтветитьУдалить
  7. Черт, неправильное решение: почему-то я предположил, что каждый игрок тянет по 3 карты. На самом деле, если тянут до последней карты, нужно передумывать все заново.

    ОтветитьУдалить
  8. нарисовал "магический квадрат"
    (816)
    (357)
    (492)
    а дальше как в крестики-нолики. проще решения не вижу. не математик.

    ОтветитьУдалить
  9. Анонимный27.02.2011, 13:41

    Тот кто первым берет карту имеет больше шансов выйграть: 1) даже,если они оба будут удачно снимать карты, первый игрок ранше наберет 15 баллов. 2) даже, если они оба будут неудачно снмать карты, первому игроку достанется больше карт. 3) первому игроку достается больше шанса взять первым самую удачную карту ( с картой под №5 больше комбинаций чтобы получить 15).
    Поэтому считаю правильным, если каждый игрок будет иметь отдельную колоду из 9 карт, и будут брать карты одновременно.

    ОтветитьУдалить
  10. Анонимный27.02.2011, 13:48

    Если конечно мы не видим карты (т.е. они перевернуты)

    Заурби.

    ОтветитьУдалить
  11. "Если конечно мы не видим карты"
    рубашками вниз по условию. видим значит.

    да, у первого, вроде, чуть больше шансов. но вопрос "как играть", а не "кто выиграет"?

    ОтветитьУдалить
  12. Анонимный27.02.2011, 15:35

    Если мы будем видеть карты, здесь просто никто не выйграет.

    Заурби.

    ОтветитьУдалить
  13. Анонимный27.02.2011, 15:51

    Первый берёт 5ку и обеспечивает себе непроигрыш (при неглупой игре).
    Второй первой берёт любую, далее - такую, которая в сумме с предыдущей картой первого даёт сумму 10.
    Так он обеспечивает непроигрыш себе.
    (доказывается простым перебором всех троек с суммой 15, их не очень много).

    Получается, что игра скучная как крестики-нолики: если оба знают как ходить, то будет ничья.

    ОтветитьУдалить
  14. BrainStill - по видимому, именно об этом и была задача. То, что первый должен брать пятерку, а второй - ту, которая входит в три выигрышные комбинации (иначе он проигрывает), я дошел. Но вод до этого изящного перехода к магическому квадрату дойти не сумел...

    Поделитесь ходом рассуждений, пожалуйста.

    ОтветитьУдалить
  15. А действительно, крестики нолики.

    4|9|2
    3|5|7
    8|1|6

    ОтветитьУдалить
  16. Не знаю, как это надо переформулировать. Рисуется египетский квадрат и становится понятно, какую карточку надо тянуть. Кстати, видел похожую задачу в с3 по информатике

    ОтветитьУдалить
  17. Denter, рассуждения мои туповаты) я выписал наборы по 3 цифры, дающих в сумме 15, чтобы затем выстроить цифры в порядке их популярности (смысл, надеюсь, ясен). получилось: 5 -4 раза 8,6,4,2 -- по 3 раза, 1,9,3,7 -- по 2. потом увидел в этом тот самый "магический" квадрат из школьного учебника. написав квадрат увидел поле для крестиков. никакой математики. только волшебство) и да, я, судя по всему, не первый. Yras76 предложил это во втором комментарии еще

    ОтветитьУдалить
  18. BrainStill, спасибо. Шаги по выписыванию комбинаций и по популярности я тоже сделал, но вот именно переход к "магическому квадрату" не всплыл. Комментарии же с подсказками не читал внимательно :)

    ОтветитьУдалить
  19. Анонимный27.02.2011, 23:08

    а- первый игрок. в- второй игрок.
    1) а берет 5
    в берет 1
    а берет 4
    в должен взять 6
    а берет 3
    если в берет 8, а берет 9 и выигрывает
    если в берет 9, а берет 8 и выигрывает.

    2)а берет 5
    в берет 2
    а берет 4
    в должен взять 6
    а берет 1
    если в берет 9, а берет 8 и выигрывает
    если в берет 8, а берет 9 и выигрывает

    3) а берет 5
    в берет 3
    а берет 4
    в должен взять 6
    а берет 1
    если в берет 9, а берет 8 и выигрывает
    если в берет 8, а берет 9 и выигрывает

    4) а берет 5
    в берет 4
    а берет 6
    в нужно будет взять 1или2
    а берет 2или1
    если в берет 8или7, а берет 7или8 и выигрывает
    если в берет 9или8, а берет 8или9 и выигрывает

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

    Заурби.

    ОтветитьУдалить
  20. анонимус(заурби?) ты неправ.
    посмотри на приведенные квадраты.
    представь что это поле для крестиков-ноликов.(надеюсь идеальную стратегию ты знаешь)
    выбор а- ставишь крестик в клетку выбора б-нолик.
    при идеальной игре обоих - ничья

    ОтветитьУдалить
  21. Диоффантовое уравнение x+y+z=15, с ограничивающим условием 0<x<y<z<10, имеет всего 8 решений:

    1,5,9
    1,6,8
    2,4,9
    2,5,8
    2,6,7
    3,4,8
    3,5,7
    4,5,6

    Карта 5 имеет максимальную ценность, поскольку она появляется в 4-х решениях из 8-ми. Карты с четными номерами 2,4,6,8 имеют большую ценность, чем карты с нечетными номерами 1,3,7,9, поскольку каждое четное число появляется в 3-х, тогда как каждое нечетное - только в 2-х решениях. Следовательно, первому игроку (А) следует выбрать карту 5 на первом же ходу, а второму (B) следует ответить выбором любой из четных чисел, например, 2. Если игрок (A) не выбрал лучшую карту 5 на первом ходу, то очевидно этим следует воспользоваться игрооку (B). Следуя шахматной терминологии, такую стратегию начала игры можно было бы назвать стремлением к захвату центра.

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

    Простой перебор вариантов показывает, что после подобного начала, т. е. 5|2, игра может быть сведена любой из сторон к ничейному результату, другими словами, каждая сторона может достичь ничью независимо от дальнейших действий противника. Например, вот типичная последовательность ходов, ведущая к ничейному исходу (* - вынужденный ход, ! - лучший ход):

    5|2
    4|6*
    7*|3*
    1!|9*
    8*|ничья

    Неразумный отказ от возможности выбрать 'центральную' карту 5 на первом шаге врядь ли может служить базой для выигрышной стратегии одной из сторон.

    ОтветитьУдалить
  22. to Заурби
    В качестве примера разберу Ваш первый вариант на магическом квадрате (для удобства).
    После хода "в берет 6" игрок а должен взять 8, чтобы не проиграть следующим ходом.

    ОтветитьУдалить
  23. Arthur Baraov, про Афганистан довольно неожиданно получилось. :-)

    ОтветитьУдалить
  24. Анонимный01.03.2011, 21:43

    занятно, видимо благодаря десятичности нашей системы счисления, большинство строят решения разбив число 15 на 5+10, хотя ничто не мешает набрать это число и другими комбинациями (6+7+2 допустим)
    готового решения в голове нет, хотя первый же комментарий подкидывает изрядную пищу для размышлений и преобразований

    ОтветитьУдалить
  25. Правильная стратегия в этой игре допускает точную и полную математическую формализацию. Правильная игра в конечном итоге сводится к выбору самого сильного хода на каждом этапе игры. А как измерить силу хода? Легко спросить, труднее ответить. Но давайте все-таки попробуем.

    Ясно, что сила хода не является функцией карты. Не трудно также понять, что сила хода должна быть функцией карты m в сочетании с ситуацией S, сложившейся на момент выбора этой карты: F= f(m; S).

    Ради краткости назовем каждую возможную тройку карт, дающую в сумме 15, триплетом:

    [1,5,9]
    [1,6,8]
    [2,4,9]
    [2,5,8]
    [2,6,7]
    [3,4,8]
    [3,5,7]
    [4,5,6]

    Чтобы полностью описать состояние игры на любой момент, достаточно приписать каждому числу в каждом триплете определенный цвет согласно следующему правилу: Зелёный (Green) - число выбрано первым игроком, Красный (Red) - число выбрано вторым игроком, Жёлтый (Yellow) - число ещё не выбрано. Выбор любой карты тем или иным игроком приводит к соответствующему изменению цвета чисел во всех триплетах, где эта карта присутствует.

    Каждый ход на любом этапе игры оказывает одно, и только одно, из следующих 6-ти действий на каждый из тех триплетов, где выбранное число учавствует (порядок следования цветов в триплете не имеет значения):

    (Y,Y,Y) -> (G,Y,Y) или (Y,Y,Y) -> (R,Y,Y): Инициализировать триплет, т. е. делать ставку на этот триплет.
    (G,Y,Y) -> (G,G,Y) или (R,Y,Y) -> (R,R,Y): Усилить триплет, т. е. угрожать немедленным поражением (шах).
    (G,G,Y) -> (G,G,G) или (R,R,Y) -> (R,R,R): Завершить триплет, т. е. выиграть игру (мат).

    (R,Y,Y) -> (R,G,Y) или (G,Y,Y) -> (G,R,Y): Убить триплет, т. е. разрушить ставку противника на этот триплет.
    (R,R,Y) -> (R,R,G) или (G,G,Y) -> (G,G,R): Нейтрализовать триплет, т. е. избежать немедленное поражение (ответ на шах).
    (R,G,Y) -> (R,G,G) или (G,R,Y) -> (G,R,R): Убить мёртвый триплет, т. е. бессмысленное действие.

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

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

    Я утверждаю, что следующая пропорция весов элементарных действий достигает цели:

    W(завершение триплета)=100
    W(нейтрализация триплета)=25
    W(усиление триплета)=5
    W(инициализация триплета)=2
    W(убийство триплета)=1
    W(убийство мёртвого триплета)=0

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

    Чтобы проиллюстрировать расчет силы хода на конкретном примере, рассмотрим ситуацию, которая сложится после первой пары ходов двух неумелых игроков S={1|8}. В этой ситуации, из семи возможных ходов выбор карты 5 все ещё является самым сильным ходом:

    f(5; 1|8) = W(усиление [1,5,9]) + W(убийство [2,5,8]) + W(инициализация [3,5,7]) + W(инициализация [4,5,6]) = 5 + 1 + 2 + 2 = 10

    ОтветитьУдалить
  26. P. S. Я не поленился так подробно расписать этот алгоритм правильной стратегии поскольку идеи и концепции заложенные в нем могут быть использованы успешно в гораздо более сложных играх. Подозреваю, что разработчики компьютерного гроссмейстера Deep Blue, который побил Гарри Каспарова, использовали подобного рода идеи.

    Сим объявляю в клубе 4-х коней конкурс на поиск функции f(move; State) для измерения силы шахматного хода. Победитель получит звание почетного гражданина Старых Васюков и специальный орден Chess Killer.

    ОтветитьУдалить
  27. Артур,в этой игре нет плохого первого хода.Первый игрок при любом начале может свести игру к ничьей.
    Так как игра неглубокая(всего 9 ходов) и на последнем этапе ходы выбираются однозначно, то гораздо проще построить дерево ходов(или рассмотреть перебор в глубину при компьютерной реализации)

    Ваша оценочная функция по идее должна сработать.Только первый ход у нее будет однозначный.

    ОтветитьУдалить
  28. в этой игре нет плохого первого хода. Первый игрок при любом начале может свести игру к ничьей. - Yras76

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

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

    ОтветитьУдалить
  29. Arthur Baraov, спасибо, что проделали такую большую работу по демонстрации сложности "метода кувалды" (или метода грубой силы). Таким путём Вы показали, что даже достаточно простые задачи имеет смысл упрощать (в данном случае, свести к крестикам-ноликам, например).

    Да, любую задачу из теории игр можно решать таким образом, но это требует огромных ресурсов. Шахматы до сих пор не перебраны полностью, поэтому современные программы, играющие в шахматы, пользуются сложными эвристиками для выбора хороших ходов. Собственно, по этой причине людям долгое время удавалось обыгрывать компьютеры :) Человек смотрит на шахматную доску как-то иначе. Не как на множество состояний (с этой конструкцией никакой памяти не хватит), а как на что-то простое. Как мы сейчас смотрели на магический квадрат, на котором играем в крестики-нолики :)

    ОтветитьУдалить
  30. Илья, боюсь что Вы несовсем правильно поняли предложенный анализ природы этой игры. Я не предлагаю перебрать все возможные варианты течения игры с целью найти совершенную функцию для измерения силы хода. Вы совершенно правы, что подобный подход к анализу сложных игр как шахматы является не только бесперспективным, но я бы даже сказал бессмысленным, поскольку он не представляет никакой познавательной ценности.

    То что я предлагаю - это прямая противоположность такому подходу. Я не пришел к функции f(m; S) на основе перебора всех возможных последовательностей ходов с обеих сторон от начала до конца игры. Количество таких вариантов, даже в такой простой игре как эта, огромно: 9! = 362880 (строго говоря, чуть меньше, ибо некоторые из них завершатся матом до разбора всех карт). Обратите внимание, что моя функция не смотрит дальше чем на один ход, т. е. это не то, что можно было бы назвать глубоким перебором вариантов игры - совсем наоборот.

    Моя функция - результат именнно эвристического анализа. Я не пересмотрел все варианты возможных течений игры даже после вывода этой функции, но почти уверен, что она позволяет довольно разумно оценить сравнительную ценность любого хода в любой ситуации. А что касается вычислительных затрат - их почти нет. Получить эффективный метод оценки сравнительной ценности любого хода в любой ситуации - это прямая противоположность методу перебора всех возможных вариантов игры, и в этом как раз смысл и ценность этого подхода к анализу стратегии правильной игры.

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

    Христианская религия отвечает на вопрос своими десятью заповедями. У Кота Матроскина был свой ответ: Ребята давайте жить дружно. Кто-то советует: Обращайтесь с другими так, как вы хотели бы чтобы с вами обращались. Народная мудрость гласит: С волками жить - по-волчьи выть.

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

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

    Есть очень интересная фундаментальная проблема в теории игр, Дилемма Заключенного, с которой наверняка многие читатели знакомы. Проблема приобретает гораздо большую жизненность и значимость, когда она повторяется(Википедия):

    В книге «Эволюция кооперации» (1984) Роберт Аксельрод исследовал расширение сценария ДЗ, которое он назвал повторяющаяся дилемма заключённого (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.

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

    Лучшей детерминистской стратегией оказалась Око за око (Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предаёт, на следующем шаге игрок иногда, вне зависимости от предыдущего шага, сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание — когда решение одного игрока сообщается другому с ошибкой.


    Око за око - вот по-настоящему эвристический, гениальный по своей простоте, динамический принцип поведения.

    ОтветитьУдалить
  32. Анонимный03.03.2011, 02:24

    Ход в центр (4:4) не является самым лучшим, самый лучший ход — «в угол» (7:1).

    Для «ноликов» расклад такой:

    0|-|0
    -+-+-
    -|x|-
    -+-+-
    0|-|0

    0|x|0
    -+-+-
    -|0|-
    -+-+-
    -|0|-

    x|-|-
    -+-+-
    -|0|-
    -+-+-
    -|-|-

    2 Arthur: эвристика хороша там, где есть необходимость срезать. Просчитать шахматную партию полностью на компьютере пока что нельзя, потому используются оценочные функции, подобные Вашей. Просчитать крестики-нолики — раз плюнуть.

    Оценочная функция позиции существует и в шахматах, и в XO, но без почти полного перебора она не строится. А если она «эффективна», но не точна, то грош ей цена.

    ОтветитьУдалить
  33. Ваша оценочная функция по идее должна сработать - Yras76

    Увы, оценочная функция, которую я так расхваливал, дает сбой. Не зря говорят: Поспешишь - людей насмешишь.

    (а) Сможете доказать, что у начинающего есть стратегия, которая гарантирует выигрыш против игрока, пользующегося моей оценочной функцией?

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

    ОтветитьУдалить
  34. Ваш велосипед не едет-вам и карты в руки.
    У меня уже есть стратегия.

    ОтветитьУдалить
  35. Анонимный04.03.2011, 06:22

    Ваша эвристика обыгрывается так:

    2|7|6
    -+-+-
    9|5|1
    -+-+-
    4|3|8

    X6, O5 (больше всего троек, центровой ход), X4

    .|.|x
    -+-+-
    .|o|.
    -+-+-
    x|.|.

    Теперь Ваш алгоритм говорит O ходить опять в угол: 1,3,7,9 имеют по 5+1=6 очков, а 2 и 8 — 5 + 1 + 1 = 7 (обратите внимание, ход в угол будет предпочтительнее при любых положительных весах!). Что и губит O:

    o|.|x
    -+-+-
    .|o|.
    -+-+-
    x|.|x


    PS Для тренировки, найдите единственный правильный ход для X в этой позиции, а также дайте оценку (выигрыш X, выигрыш O, ничья) другим ходам:

    .|.|o
    -+-+-
    .|.|.
    -+-+-
    .|X|.

    PPS %;?%?;:?:!!!1! Как сделать <pre> в комментариях?

    ОтветитьУдалить
  36. Fractal,

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

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний