Думаете можно весь набор возможных мизеров разобрать по такого типа классификации? Это было бы похоже на нахождение базиса в пространстве мизеров .

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

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

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

Предлагаю устроить диспут на тему "Как формализовать понятие стратегии?"

Это сообщение отредактировал isabsent - 18/04/2013, 21:30

Если бы игра велась между двумя соперниками, то в этом случае многие матричные игры решаются эффективно численными методами. См. в поиске "Методы приближённого решения матричных игр" или "Численные методы решения матричных игр".

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

В шахматах есть такое понятие - advanced chess. Это "когда игроки во время игры могут пользоваться компьютером и рассматривать варианты, предлагаемые шахматными программами". Не знаю, как сейчас, а до недавнего времени такой симбиоз давал результат лучше, чем "чистая программа", и значительно лучше, чем человек. Так может быть всё-таки есть смысл пока отложить разработку преферансного ИИ, а попробовать сделать калькуляторы для вычисления реальных величин, типа МО?

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



Это сообщение отредактировал isabsent - 19/04/2013, 02:50

Под матричными играми обычно подразумевает игры с одновременными ходами. Они намного проще. Кроме того под смешанными стратегиями в таких играх (обычно?) понимают композицию ИЗНАЧАЛЬНО ЗАДАННЫХ ЧИСТЫХ СТРАТЕГИЙ, полностью определенных ДО НАЧАЛА ИГРЫ. Веса в композиция этих чистых стратегий выбираются тоже ДО НАЧАЛА ИГРЫ и не меняются в процессе игры. В случае преферанса это не так.

Если Вы видели где-нибудь разбор игры двух игроков с последовательными ходами и смешанными стратегиями, веса которых вычисляются ПОСЛЕ КАЖДОГО ХОДА оппонента - киньте ссылочку, плз.

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

Есть класс задач - "задачи преследования-уклонения" - в которых перехватчик преследует цель. Цель меняет направление движения случайно, но не совсем - по определенным правилам, перехватчик тоже вынужден двигаться по определенным правилам (законы Ньютона и мощности двигателей являются как бы аналогами правил хода в преферансе). То есть имеем как бы игру перехватчика и ракеты. Такие задачи называются дифференциальными задачами теории игр, потому что описываются дифференциальными уравнениями. Преферанс - это аналог такой задачи, в которой дифференциальные уравнения заменены на разностные и количество возможных ходов сильно ограничено.

Это сообщение отредактировал isabsent - 19/04/2013, 04:22

Не совсем так. В некоторых классах мизеров с дырами в двух-трех мастях возможно сведение к одновременному принятию решений всеми сторонами. Это относится к случаям, когда при угадайке перехват невозможен, либо нецелесообразен ввиду малой длины паровоза при некритично различающихся прогнозируемых вероятностях ловли дыр. Либо, наоборот, производится всегда ...

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

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

Т.е. все эти три хода могли бы рассматриваться как одновременные.

Но вот стратегия принятия решения перехвата/пропуска в эту схему как-то не вписывается. Во первых, она принимается на основании конкректного расклада (т.е. в зависимости от длин паровозов). А во вторых, может быть скорректирована, если ловящие ошибутся и вынуждены будут (нет, не выпустить мизерящего раньше времени) укоротить возможный паровоз.

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

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

Это сообщение отредактировал Pochemuk - 19/04/2013, 10:42

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

Александр дело говорит. На самом деле никакой ИИ для калькулятора не нужен. Калькулятор должен выдавать только следующие результаты в случае неизвестного сноса (но при ограниченном количестве вариантов сноса, задаваемых вручную):

1. Вероятности ловли каждой дырки, если ловится только она одна. Если перехват невозможен, то так же приводятся вероятности каждой длины паровоза.
2. Вероятности того, что ловятся 2, 3 и т.д. дыры из возможных (для каждого сочетания дыр). Так же должны выдаваться длины паровозов для каждой дыры каждого набора дыр с их вероятностями.

Например, {7 8 9 Т}{7 8 К}{7 8 Д}{7 10}.
Задаются возможные сносы: {Т К}{Т Д}{Т 10}{К Д}{К 10}{Д 10}{10 7}. Для интереса можно добавить в другой раз одномастные {К 7} и {Д 7} и сравнить результаты.

Одна из строчек результата может выглядеть так:

Ловятся одновременно К и Д и не ловятся Т и 10 с вероятностью ...%
Вероятности длин паравозов в случае ловли каждой из этх дыр:
К-1 : ...%, Д-1 : ...%
К-2 : ...%, Д-2 : ...%
К-3 : ...%, Д-3 : ...%
К-4 : ...%, Д-4 : ...%
К-5 : ...%, Д-5 : ...%
К-6 : ...%, Д-6 : ...%
К-7 : ...%, Д-7 : ...%
К-8 : ...%, Д-8 : ...%
К-9 : ...%, Д-9 : ...%
К-10: ...%, Д-10: ...%

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

Давайте конкретизируем что мы хотим калькулировать.

1. Калькулятору известны карты на руках ловящих? Он предполагает один из сносов, которые Вы ему разрешили предположить и дальше он что делает? Вычисляет НА ОТКРЫТЫХ КАРТАХ сколько взяток он даст мизеристу - и так для каждого сноса? Если Вы имеете ввиду только это, то тогда ИИ не нужен.

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

1. Нет, не так. Мы обсчитываем не конкретную сдачу мизера при различных вариантах сноса, а руку мизерящего "в общем".

2. Тоже не так. Зачем калькулятору ИИ для того, чтобы поймать единственную ловящуюся дырку. Либо она оставлена и ловится 100% (но на разные коллективы с разными вероятностями), либо снесена и мизер чист.

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

Повторю: калькулятор не считает вероятности того, что поймают или выпустят в зависимости от стратегий. И не использует в своих расчетах знание о стратегиях. Он считает вероятности того, что дыра ловится одна или в комбинации с другими дырами. А так же вероятности различных длин паровозов, при условии, что будут ловить именно ее, а играющий не перехватит.

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

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

Это сообщение отредактировал Pochemuk - 19/04/2013, 14:32

P.S. Кстати, метод Брауна-Робинсона (МБР) можно использовать для вычисления стратегий "на лету", т.е. в параллель вычислениям вероятностям. Просто надо предполагать, что игра ведется не по одной платежной матрице, а сразу по нескольким. И ход Рока (сдача карт ловцам при фиксированной руке мизерящего и сносе) выбирает ту или иную матрицу платежей с некоторой вероятность. Таким образом, каждую сдачу (снос + ход Рока для распределения карт у вистующих) можно передавать в МБР последовательно. Результаты МБР будут использоваться для корректировки стратегий сноса.

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

Это сообщение отредактировал Pochemuk - 19/04/2013, 15:10