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

одна из альтернатив минимаксу - так называемый max^n, при котором *каждый* игрок стремится максимизировать собственный выигрыш (а не кооператив 2 против 1 как в минимаксе). С такой стратегией альфа-бета уже работать не будет. Там используется shallow pruning, но в чём именно его суть, я уже плохо помню. Помню только, что он отсекает значительно меньше альфа-беты и вроде как не устойчив к изменению стратегии.

"И снова здравствуйте!"

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

Пока обкатываю алгоритм на 2-ой задаче Клейна с измененным сносом:

	Север  10 8  Q J 9 7  -  Q J 8 7
Снос  J  -  J  -		Восток  A  A 10  A K 9 8 7  A 9
	Юг  K Q 9 7  K 8  Q 10  K 10

Север играет мизер и ходит первым.
Считаю, что уже сделаны ходы:
1. 10 , Т , К
2. 10

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

Юг должен решить, что положить К или 8
1.Если он кладёт 8, то тем самым дает мизеристу возможность перехватить на Д, добрать вторую взятку на 8. Больше тут взяток мизериста нет.

2. Если он кладет К, то с учетом неизбежной угадайки между 0 и 5-ю взятками (угадывать снесен J или нет - 50/50), получается, что мизерист имеет в среднем те же 2 взятки (тут я уже учитываю, что за 0 взяток он получит +1 взятку в пулю).

Первый вопрос:
Получается, что в этом примере нельзя сделать однозначный выбор между К и 8 с точки зрения оптимального МО?

Второй вопрос:
Если будет положена 8, то мизерист может и не перехватывать, а подложиться 7, так как он в среднем получит те же 2 взятки в результате угадайки позднее. Желание мизериста всё-таки перехватить и зафиксировать две взятки связано с чисто психологической особенностью человека ограничить размер ущерба гарантированно и не полагаться на статистику, которая сделает в принципе то же самое за него?

Это сообщение отредактировал isabsent - 14/05/2013, 23:29

1) Да
2) Да (в тех случаях когда такое желание есть )

С точки зрения МО, действительно, нет разницы - перехватывать или пропускать, позволять перехватить или отъедать свои.

Но вот с игровой точки зрения разница есть ... Причем, для обеих сторон. Одни мизерящие предпочтут перехватить. Другие будут рисковать угадайкой на длинный паравоз. Одни ловящие сами предложат 2 взятки без розыгрыша. Другие будут упорствовать до конца, в надежде сунуть 5.

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

Если положить К, то тем самым ловящие лишают играющего свободы выбора. На черве сделать позже повторное "предложение" перехватить уже не получится - в этом случае ее добор будет сделан на руку Востока, а оттуда ловится только бубна. Или же пытаться ловить пику с руки Юга, но уже только на 1 взятку в лучшем случае.
Получается, что ход К во вторую взятку приводит к форсированному выходу на угадайку 5/0 с вероятностями 50% (это если ничего не знать об оптимальных смешанных стратегиях, разумеется, а ловить наобум).
Другими словами, шанс выпустить мизерящего чистым составляет аж 50% ...

Если же во вторую взятку положить 8, то часть игроков предпочтет перехватить и обойтись двумя взятками. Часть же пропустят и пойдут на угадайку 5/0. Т.е. ловящие действуют более гибко - дают возможость перехватить, но и выход на угадайку (при отвергнутом перехвате) при этом никуда не девается. Но в этом случае вероятность выпустить мизерящего снижается - будет уже не 50% от общих шансов, а 50% от доли отвергнутых перехватов трефы.
Если от балды предположить, что перехватить трефу предпочтут 60% мизерящих, то половина от оставшейся части составляет всего лишь 20% - шансы выпустить играющего чистым уменьшились в 2,5 раза.

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

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

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

Резюме: Не МО единым ...

Это сообщение отредактировал Pochemuk - 16/05/2013, 08:35

Мне кажется, что тот, кто первым ходом ходит с 10 перехватывать не будет. Но согласится, если ему предложат 1,5 взятки.
PS Так всё-таки - алгоритм умеет ловить мизер с неизвестным сносом или нет?

А что следует понимать под понятием такого умения?

Если умение словить в 100% случаев угадаечный мизер, так этого никто не умеет - ни человек, ни пароход автомат.

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

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

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

Ключ к решению подобных в задач в установлению соотношения угадайки. Например, почему все считают, что угадайка 50/50 между В и 8?
Конечно, алгоритму будет сложно выявить психологические аспекты альтернативных сносов, поэтому придется использовать математический аппарат. А именно, нужно понять что выгоднее в экономическом плане оставлять игроку при условии стратегии ловли 50/50. Запустить моделирование и получить результаты, на основании которых сместить соотношение угадайки. Смещенное соотношение позволит выявить однозначный план ловли.
Получилось, что мы взяли принцип оптимальности игрока и создали оптимальную стратегию.
Осталось понять, как бороться с игроком, которому известен этот принцип алгоритма.

--------------------

the elephant has you..

Если под неизвестным сносом Вы понимаете ситуацию угадайки - то конечно умеет. Просто я пытаюсь его допилить так, чтобы он статистически правильно его ловил. То есть, если ТЕОРЕТИЧЕСКИ мизер должен быть пойман с вероятностью 50/50, то и мой алгоритм должен давать это же соотношение, а не 30/70 например.

Если Вы что-то другое подразумеваете, то дайте пример - я попробую.

1. Мне кажется, что здесь угадайка 50/50 по признаку снесен В или нет. Если пытаться максимально оттянуть выбор (мизерист не перехватывает), то на 6-ой взятке возникает ситуация, когда ловцы должны решить куда ходить в или в - то есть 50/50. Угадывают - дают паровоз на 5 взяток. Не угадывают - мизерист проносит свою единственную дырку и уходит чистым.

2. Я пытаюсь заставить алгоритм играть "оптимально" пока только в том смысле, что он не должен проигрывать. Такая оптимальность (назовём её "слабой" ) не позволит выжать максимум из ситуации, если противник играет очень предсказуемо - например ВСЕГДА сносит карты с максимальной вероятностью ловли на мизере (как "Марьяж"? ). Эта предсказуемость позволила бы более навороченному алгоритму, умеющему анализировать предсказуемости оппов по истории сыгранных с ними партий, ловить оппов на 100% не доводя до угадайки - просто вычислив снос с максимальной вероятностью ловли.

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

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

3. А как можно бороться с игроком, который выбирает камень, ножницы или бумагу случайно с одинаковой частотой? Никак. Можно только поступать так же и тогда в среднем ни он ни Вы не выиграете. Бороться можно только если Вы выявили предсказуемость оппа - возможно не 100%-ю, а хотя бы статистическую: например камень он выбирает чаще. Тогда Вы начинаете чаще выбирать бумагу.

Это сообщение отредактировал isabsent - 16/05/2013, 13:12

А какая вероятность, что там В108? И почему не учитывается эта возможность?

--------------------

the elephant has you..