Недавно появилась какая-то прога для Андроида. Разработчики заручились поддержкой Д.В. Лесного и использовали оригинальные алгоритмы Л. Натансона.

Были ли они доработаны - не знаю. У меня самого эта прога не идет. Не хватает каких-то системных библиотек в сборке. Разработчики ничем помочь не смогли.

Знаю только, что оппоненты дополнены кроме Студента, бакалавра, Магистра, Рентгена (Шулер в этой проге) еще и Школьником - слабым игроком, доступным в бесплатной версии.

Она под процессор ARM v.7 скомпилирована из С++ кода. Возможно, что не идёт из-за того, что у Вас ARM v.6 на девайсе. У меня она идёт. Школьник даже для меня сильно слабый. А Студент из 15 раз что я играл, три-четыре раза делал такие вещи, которые даже моя андроид-прога на 100% раскусывает (лёжа и мизеры, но не на распасах).

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

да, это фактически стандартная часть реализации любой альфа-беты. Делается при помощи хэша Зобриста. Но там ещё есть пара фишек, которые позволяют сильно ускорить процесс. Я их сам из пальца высосал и больше нигде не видел, так что воспользуюсь вашим примером и придержу "ноу хау" Скажу только, что сейчас моя прога полностью анализирует более 1000 независимых начальных раскладов в секунду ("начальный" - т.е. у каждого по 10 карт). И это всё без многопоточности, на одном трёхгигагерцовом ядре. Т.е. на 4х-ядернике фактически оно будет работать в 4 раза быстрее. Что с этой прогой делать, я пока не придумал, правда. Чисто академический интерес пока.

Можно полюбопытствовать?

1. Какой размер хэша выбран?
2. Какова его средняя заполненность?
3. Какой процент коллизий?

Размер хэша - около 150 тыщ записей. Выбран эмпирически: начал с маленького и увеличивал до тех пор, пока алгоритм не перестал ускоряться.
2 и 3 не считал.

А кроме Zobrist-хэширования применяются какие-либо эмпирики для сокращения дерева позиций?

Разумеется.

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

Да, ответ правильный. Даже Менделеев тут к месту. ))
Моя версия такая. Если посмотреть на все возможные в преферансе ситуации (расклады), то их необозримое множество. Допустим, миллиард. Но если приглядеться к масти Т7, то нетрудно сообразить, что К7 - практически то же самое. И если это принять, то ситуаций делается в 2 раза меньше: 500 миллионов. А если же сюда на том же основании "приплести" и Т8 с К8, то остается всего 250 миллионов - почти пустяки.
Правомерно ли такое допущение: Т7 = К8? А почему нет? В результатах разыгрывания отличия будут измеряться в единицах процента. Но нам сейчас важнее различия в решениях, в выборе карты, а таких отличий не будет совсем. То есть там, где ходить надо Т, а потом 7 (а не 7 и Т), там надо играть К и 8, а не 8 и К.
Что получается? А то, что главная сложность во всем этом деле - правильная классификация множества исходных мастей. Но по части всяких классификаций и систематизаций у меня, слава Богу, определенно талант, и всё получилось как нельзя лучше.
А получилось именно то, что всего мастей полтора десятка. А рук всего 3 типа. Итого 50 исходных сочетаний. Ситуаций для них тоже не много: ходишь сам, реагируешь на ход, проносишь... Получилось полторы сотни. Наконец, в пределах масти (или их сочетаний) нужно разобраться. То есть если у вас 2 масти для разыгрывания (особенно однотипных), то с какой именно масти и с какой ее карты начинать? Короче говоря, весь преферанс в аспекте "Распасы" сведен к трем сотням ситуаций, которые тщательно рассмотрены. Пропусков нет, вот тут привет и благодарность Менделееву.

Что "итого"? В рамках сделанных допущений ошибок, разумеется, нет. Еще ни одной не встретил. Пропуски "ситуаций" - были редчайшие случаи, но в малозначительных мелочах. Насколько система адекватна? Сам алгоритм ошибок не дает никогда - я пока ни одной не встречал. Но в моей практической игре ошибок много. Но это мои ошибки. Чего ожидать, если в процессе лениться и не считать расклад (и тебя эти ошибки ждут, если не сделаешь функцию)? Плюс, есть таки в моем алгоритме понятия, которые сами по себе громоздки, и для практики они упрощены, но когда дело касается таких случаев, проскакивают ошибки. Пример: угроза "УДС" - так в алгоритме закодировано, - это беззащитное состояние руки, угроза паровоза. Понятно, что такого надо избегать в своих действиях. Но определение не совсем формально, и ошибки в трактовке дают ошибки в игре. Или там для паровозных и "очень" паровозных типов рук игра разная - разные таблицы, - но элементарно лень углубляться в эти нюансы... А вот в машинном исполнении того же самого ошибок практически не было бы совсем. Сам я думаю, что в этом варианте мой алгоритм покажет не менее 95% эффективности относительно идеальных 100%. К слову, просто перебором без учета расклада не удастся превысить и 80%. И сейчас я к тому говорю, что в игре против людей никакой "квантовой химии, и всякой s-p-гибридизации" не требуется, ибо никто из homo... не устоит и так. Там всё же игровой монстр, несмотря на простоту гаек и болтов, из которых он устроен. А цели бороться с другими алгоритмами распасов никогда и не ставилось. Хотя бы потому, что об их существовании еще никто и никогда не заявлял. ))

Это сообщение отредактировал Байкер - 17/03/2013, 14:09

У меня мотив скорее даже не написать алгоритм, который обыгрывает людей, а написать алгоритм который "закроет тему", что называется. То есть будет играть так хорошо, как позволяет железо, в отличие от "Марьяжа", который на любом железе не превысит свой потолок - мастерство игры человека, который заложил в него конечный набор известных ему игровых стратегий. Судя по всему возможности современного железа подошли к этому вплотную. Я подозреваю, что они уже ДАЖЕ ПРЕВЫСИЛИ необходимый уровень для всех игр, кроме распасов.

В идеале это было бы что-то типа "таблицы Байкера", но не хранимое в алгоритме в виде ПОЛНОЙ таблицы для всех сдач (как можно сейчас сделать, если попытаться повторить твой путь), а вычисляемое в процессе игры только в той ЧАСТИ, которая нужна для розыгрыша конкретной сдачи.

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

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