Главная Online 1369 Login
Здравствуйте, гость Правила · Помощь

»  Оценка карты играющего при заданном сносе, Определение результата игры для мизера и игры на взятки Подписаться | Сообщить другу | Версия для печати
      » 16/03/2018, 01:05,  Pochemuk 
american_boy (15 марта 2018, 22:48)
Во-первых, давайте сразу правильно определимся с атмосферой, в которой находимся. Призываю к общению на одном языке.
...
У нас проходит примерно такой разговор. Я говорю:  "Николай Николаевич! Сделайте-ка мне быстренько одну программку, я  уже всё придумал надо просто дать  задание вашим программистам."

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

Да разве кто-то против общаться на одном языке?

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

Что касается страшных слов "Zobrist-хеш", "транспонирование" и т.д., то когда мы с Николаем взялись за эту задачу, то даже о галимом альфа-бете переборе из нас двоих только я слышал. Транспонирование раскладов я к тому времени продумал хорошо, но как его применять - понятия не имел. Потому что путал понятия кэш и хеш, про Zobrist краем глаза слышал, а как правильно организовать кэширование даже не задумывался.

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

Хотели переходить к решению неизвестного сноса (двухвариантного и многовариантного), но запал уже потихоньку за год иссяк. Да и задачка оказалась не такой "простой", как представлялось.

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

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

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

Это сообщение отредактировал Pochemuk - 16/03/2018, 01:07
      » 16/03/2018, 02:05,  Фрэд 
Pochemuk, истово плюсую! Я примерно в похожей ситуации, только занимаюсь этим в одиночку и примерно с декабря прошлого года. В свободное от работы и других дел время.
      » 17/03/2018, 01:59,  Байкер 
Приходилось рассматривать похожую проблему в связи со сносами на мизерах. В связи с этим любопытно было посмотреть на дискуссию, на озвученные "трудности"...
Главное впечатление и вывод: вы пытаетесь преферанс адаптировать под ваши алгоритмические достижения, а я считаю правильным с помощью алгоритмических подходов решать проблемы преферанса.

Например, в данном случае я начал бы с классифицирования по формальным критериям типов сносов из всего их множества. Например:
- очевидные;
- равновероятные;
- проверяемые;
- дезинформирующие;
- разновероятные.
У вас мб другой набор, а тем более, наименования. Но когда вы проникнетесь этой "простотой", то вам станет очевидным, что делать дальше.
Но на сим замолкаю: тут все очень умные, сами знают, что надо делать, и какого-то там байкера слушать не надо. Ему надо говорить, что он ничего не понимает в настоящем преферансе... )
      » 17/03/2018, 21:48,  american_boy 
Если уже готовые варианты сноса обсчитать не могут, то заставить прогу ещё и выбирать снос – звучит как издевательство )))

Это сообщение отредактировал american_boy - 17/03/2018, 22:03
      » 17/03/2018, 22:18,  Байкер 
Определение вистующим сноса игрока и, как следствие, тактики разыгрывания - аспект (проблема) преферанса.
А вы во что "играть" собрались? Если в преферанс, то я и посоветовал вам попробовать "с помощью алгоритмических подходов решать проблемы преферанса". Но нет - так нет, я не настаиваю. )
      » 17/03/2018, 22:57,  american_boy 
Никто ж не против создания проги, которая сразу умеет всё. Так мы и последних программистов распугаем.
Честно говоря, если б я был программистом я б разобрал сначала марьяж. Но не мне им советовать, ребята толковые, сами разберутся, не будем им мешать нашими советами)))
      » 17/03/2018, 23:28,  Байкер 
american_boy (17 марта 2018, 22:57)
Так мы и последних программистов распугаем.

Тут программисты не нужны и даже вредны. Тут нужны "алгоритмисты".
Но согласен, что это бесполезный разговор.
      » 18/03/2018, 10:20,  Кутруповезет 
Фрэд (11 марта 2018, 05:24)
...было интересно самому сделать.

Запустил вашу программу на Win 7, все нормально работает. Просчитал с десяток раскладов – ошибок не нашел, все верно.
Примите поздравления – вот так вот взять и написать такую программу с корректным расчетом и еще с графическим интерфейсом – не очень-то просто.

Но скорость расчета очень маленькая. Я запускаю на одной машине BPS Словеснова и вашу программу. На вашей программе время расчета, например, задачи Галактионова - около 5 секунд. На BPS – около1 сек. Причем в BPS это время расчета для опции «Решение для всех игроков и козырей», т.е. там считается и выдается результат для 3*6 = 18 разных вариантов. Получаем, что BPS быстрее в 5*18 = 90 раз. А программа Extasy и Pochemuk по их словам еще быстрее.

Одна из причин медленной работы вашей программы, видимо, то, что в ней не реализованы альфа-бета перебор и другие приемы ускорения. Но не может ли быть и другой причины? Может, дело в том, что у вас отличается базовая логика решения?

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

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

Это сообщение отредактировал Кутруповезет - 18/03/2018, 11:07
      » 18/03/2018, 13:07,  Pochemuk 
Кутруповезет (18 марта 2018, 10:20)
Фрэд (11 марта 2018, 05:24)
...было интересно самому сделать.

Запустил вашу программу на Win 7, все нормально работает. Просчитал с десяток раскладов – ошибок не нашел, все верно.
Примите поздравления – вот так вот взять и написать такую программу с корректным расчетом и еще с графическим интерфейсом – не очень-то просто.

Но скорость расчета очень маленькая. Я запускаю на одной машине BPS Словеснова и вашу программу. На вашей программе время расчета, например, задачи Галактионова - около 5 секунд. На BPS – около1 сек. Причем в BPS это время расчета для опции «Решение для всех игроков и козырей», т.е. там считается и выдается результат для 3*6 = 18 разных вариантов. Получаем, что BPS быстрее в 5*18 = 90 раз. А программа Extasy и Pochemuk по их словам еще быстрее.

Одна из причин медленной работы вашей программы, видимо, то, что в ней не реализованы альфа-бета перебор и другие приемы ускорения. Но не может ли быть и другой причины? Может, дело в том, что у вас отличается базовая логика решения?

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

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

Если бы не был реализован альфа-бета перебор, то решение единичного расклада имело бы порядок десятков минут, а то и нескольких часов. Альфа-бета отсечения - основной способ сокращения дерева перебора. В свое время он был революционным. Сейчас является неотъемлемой частью игровых программ. Кроме новейших, основанных на ИНС. Но ИНС для решения раскладов пока что мало подходит.

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

Хотя, повторю, итоговая реализация может немного отличаться от того, что планировалось и обсуждалось.

1. Перебор дерева решений осуществляется с применением алгоритма альфа-бета отсечений. Подход NegaMax не применяется, т.к. усложняет логику программы дополнительными проверками. Вместо этого применяются несколько более простых различных процедур для каждой из сторон, а так же для начальной атаки (т.к. для начальной атаки альфа-бета отсечения не применяются). Так же не применяется альфа-бета отсечения с амортизацией - тесты не выявили существенного повышения эффективности работы с кэшем, а сложность алгоритма амортизации чуть выше, что привело к просадке производительности почти на 1%.
2. Дерево отсечений не строится для последней взятки, т.к. дерева нет - все ходы единственно возможные. Вместо дерева непосредственно расчитывается принадлежность этой взятки. Это снижает глубину рекурсий.
3. Для позиций, в которых нет выхоженных на стол карт (т.е. для позиций перед первым ходом во взятку, кроме первой) строится транспозиция - карты мастей и сами масти переупорядочиваются с учетом выхоженных карт (так же сноса), длины/силы некозырных мастей, козырной масти.
4. От полученной транспозиции вычисляется хеш. Мы решили применять Zobrist-хеширование. Во-первых, просто, во вторых - равномерно.
5. В качестве индекса кэш-таблицы можно брать несколько старших или младших битов хеша. Но Николай решил брать остаток от деления на размер кэш-таблицы. Это несколько дольше, но позволяет более гибко оперировать ее размером, что немаловажно для исследования его влияния на производительность.
6. В кэш-таблице хранятся транспозиции с оценкам альфа-бета интервала. Если транспозиция не найдена (ячейка с соответствующим индексом не заполнена или имеет место коллизия - заполнена другой транспозицией), то запускаем процедуру альфа-бета перебора. После чего записываем полученный интервал в таблицу.
7. Если транспозиция найдена в кэш-таблице, то дальнейшее поведение зависит от хранимого в ней диапазона альфа-бета, текущего значения альфа-бета диапазона и числа оставшихся на руках карт. Либо сразу возвращаем оценку, либо тоже запускаем перебор для уточнения диапазона. Уточненное значение альфа-бета диапазона записывается в таблицу.
8. Для позиций с выхоженными на стол картами транспозиции не вычисляются и кэширование не производится. Вместо этого применяются эвристики нахождения лучшего ответа, повышающие вероятность нахождения хорошего хода уже в начале перебора. Эти эвристики реализованы в виде процедур, обращение к которым производится по ссылкам из массива. Это позволяет легко менять такие эвристики для экспериментов.
9. Для первого хода во взятку тоже применяются эвристики, но их эффективность несколько ниже. Вернее, эффект от них был до применения кэширования, но кэширование само по себе реализовано столь эффективно, что перекрывает весь эффект от этих эвристик.
10. Еще надо отдельно отметить, что перед перебором на любом уровне сначала создается список допустимых ходов/ответов с учетом секвенсов и отсутствующих карт. Так, если в руке {10 9 7} одной масти а восьмерка уже вышла (или в сносе), то достаточно рассмотреть ход только в одну карту из этого набора. У Словеснова наборы допустимых ответов для второй и третьей руки создаются оба на этапе перебора ответов второй руки. Это позволяет для третьей руки создавать этот набор тоже один раз. Еще там, кажется, если масть хода первой руки не сменилась, то эти наборы не переформируются. У Николая это не так. Ибо основная сложность не в получении набора (он применил весьма изощренные структуры данных, позволяющие получать эти наборы достаточно просто), а в сортировке этих ответов по рекомендациям эвристик. А эти рекомендации будут разными в зависимости от уже выхоженных во взятку карт. Поэтому выигрыш от повторного использования этих наборов минимален или отсутствует.

Что не релизовано, так это перебор с нулевым окном. Я склонялся к MTD(f), а Николай к NegaScout. Но эксперименты с NegaScout он проводил еще до реализации кэширования. Выигрыш был, но после реализации кэширования сошел на нет. А до MTD(f), который как раз заточнен под работу с кэшем, так руки и не дошли.

Вот как-то так ...

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

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

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

Это сообщение отредактировал Pochemuk - 18/03/2018, 13:21
      » 18/03/2018, 16:03,  Кутруповезет 
Pochemuk (18 марта 2018, 13:07)

Андрей, спасибо за подробные объяснения, очень интересно и познавательно.
Да, это целая наука, и немаленькая.

А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков. Но действительно ли это препятствие непреодолимо? У меня, как и положено дилетанту, есть некоторые сомнения в этом. Может, ребята всего лишь немного недодумали, недоработали?

Это сообщение отредактировал Кутруповезет - 18/03/2018, 16:27
      » 18/03/2018, 17:36,  Байкер 
Кутруповезет (18 марта 2018, 16:03)
А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков.

Почему невозможно? Возможно - я же сделал.
Но...
Во-первых, это можно сделать только алгоритмически - в значении "алгоритмы преферанса", а не алгоритмы счетных дел.
Во-вторых, результат "калькулирования" меняется от 0% знания (пока не сделано ни одного хода, вы не можете судить предметно о раскладе карт противников) до 100% (по окончании разыгрывания расклад вы точно узнаете), но в каждый текущий момент принятия решения степень знания может оставаться недостаточной для однозначности - текущая ситуация может оставаться ситуацией с неполной информацией. Хотя и во многих случаях расклад считается полностью после нескольких первых ходов.
В-третьих, существует проблема ввода текущей информации при попытках "автоматизации". Вручную в параллельно с вашей игрой работающую программу - долго и неудобно в контексте хода реальной партии, а способы автоматического считывания с экрана, видимо, существуют, но я не в теме.
В-четвертых, алгоритм расчета расклада на распасах в результате не столько сложный, сколько "объемный", много мелочей надо помнить и сопоставлять по ходу дела, поэтому "вручную" - удерживая всё в голове, - его реализация в ходе реальной игры весьма трудоемкая вещь. Там отдельно надо заниматься созданием мнемонических правил использования...
Короче, лично я на это всё пока забил, и расклад на распасах на практике не считаю. Хотя и знаю, как это сделать. )

Это сообщение отредактировал Байкер - 18/03/2018, 17:40
      » 18/03/2018, 18:10,  Кутруповезет 
Байкер (18 марта 2018, 17:36)
Кутруповезет (18 марта 2018, 16:03)
А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков.

Почему невозможно? Возможно - я же сделал.
Но...
Во-первых, это можно сделать только алгоритмически - в значении "алгоритмы преферанса", а не алгоритмы счетных дел.

Да, Юра, этот вариант оценки карты - алгоритмический - вполне возможен и я представляю, как это может работать.

Мой вопрос был именно о программных вычислениях - о переборе вариантов на распасах. В идеале такая программа выдавала бы МО руки при распасах для определенного расклада. Следующим шагом было бы вычисление МО руки при распасах как среднего МО для всех раскладов.

Это сообщение отредактировал Кутруповезет - 18/03/2018, 18:17
      » 18/03/2018, 19:03,  Pochemuk 
Кутруповезет (18 марта 2018, 16:03)
А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков.

Нет ничего не возможного. Есть только цена, которую Вы готовы заплатить. © smile.gif

Можно было здесь прочитать мнение, что распасы игра бескоалиционная. А, следовательно, для нее надо искать равновесие Нэша, а это сложно и вообще непонятно, как это делается.

В этом заблуждении есть целых 2 заблуждения smile.gif

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

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

А в чем же тогда проблема?

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

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

Но лучше пояснить на примерах:

Пример 1.

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

Пример 2.

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

Т.к. перебор дерева игры построен на принципе Минимакса, то в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

Это сообщение отредактировал Pochemuk - 18/03/2018, 19:47
      » 18/03/2018, 20:18,  Dukhin 
Pochemuk (18 марта 2018, 19:03)
Кутруповезет (18 марта 2018, 16:03)
А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков.

Нет ничего не возможного. Есть только цена, которую Вы готовы заплатить. © :)

Можно было здесь прочитать мнение, что распасы игра бескоалиционная. А, следовательно, для нее надо искать равновесие Нэша, а это сложно и вообще непонятно, как это делается.

В этом заблуждении есть целых 2 заблуждения :)

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

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

А в чем же тогда проблема?

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

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

Но лучше пояснить на примерах:

Пример 1.

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

Пример 2.

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

Т.к. перебор дерева игры построен на принципе Минимакса, то в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

Андрей.
я немного занимался конкретно этим вопросом.

максимум, на что имеет смысл замахиваться, это то, что описал Юра:
"онлайн помощник для распасов"

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

этот путь менее трудоемкий и более эффективный, т.к. огромное влияние оказывает level и текущее состояние оппонентов.
      » 18/03/2018, 20:22,  Байкер 
Pochemuk (18 марта 2018, 19:03)
...перебор дерева игры построен на принципе Минимакса, ... в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

Ну, ты загнул... А откуда тогда берутся о-о-очень сильные "исполнители" распасов? Которых очень трудно обыграть? Они тоже действуют "перебором" - тем или иным алгоритмом?
Еще раз напрашивается спросить: в преферанс играть не пробовали (в смысле создания алгоритмов)? )
      » 18/03/2018, 20:28,  Pochemuk 
Байкер (18 марта 2018, 20:22)
Ну, ты загнул... А откуда тогда берутся о-о-очень сильные "исполнители" распасов? Которых очень трудно обыграть? Они тоже действуют "перебором" - тем или иным алгоритмом?

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

А "исполнители" как раз потому и играют сильно, что они не перебирают. Тем более, что переборный алгоритм работает на открытых картах, а они играют на закрытых. Как и их соперники.
      » 18/03/2018, 20:49,  Байкер 
Pochemuk (18 марта 2018, 20:28)
Речь идет не об игре, а об переборном анализе распасов. Т.е. я объясняю, почему переборный алгоритм для распасов не подходит.

Говорим мы об одном и том же, только на разных языках. Речь о том, чтобы найти оптимальный ход, когда он ваш. Конечно, перебор для этого в распасах не подходит. Особенно (точнее, хотя бы потому) если расклад еще не удалось посчитать. Вроде, как очевидно... Или нет? ))
      » 18/03/2018, 21:01,  Pochemuk 
Байкер (18 марта 2018, 20:49)
Речь о том, чтобы найти оптимальный ход, когда он ваш. Конечно, перебор для этого в распасах не подходит. Особенно (точнее, хотя бы потому) если расклад еще не удалось посчитать. Вроде, как очевидно... Или нет? ))

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

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

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

Вот и получится, что для большинства наших ходов нельзя получить точный окончательный результат, а только диапазон количества взяток.
      » 18/03/2018, 21:49,  Кутруповезет 
Байкер (18 марта 2018, 20:22)
Pochemuk (18 марта 2018, 19:03)
...перебор дерева игры построен на принципе Минимакса, ... в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

Ну, ты загнул... А откуда тогда берутся о-о-очень сильные "исполнители" распасов? Которых очень трудно обыграть? Они тоже действуют "перебором" - тем или иным алгоритмом?

Совершенно верно. Сам факт того, что существуют очень сильные игроки в распас, говорит в пользу того, что весьма точная оценка МО карты на распасе человеком возможна. Невзирая ни на какие минимаксы.

Это сообщение отредактировал Кутруповезет - 18/03/2018, 22:41
      » 18/03/2018, 21:54,  Кутруповезет 
Если итоговый вывод такой:
()
Т.к. перебор дерева игры построен на принципе Минимакса, то в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

то что вы имеете в виду под:
Pochemuk (18 марта 2018, 19:03)

Нет ничего не возможного. Есть только цена, которую Вы готовы заплатить.
?
      » 18/03/2018, 22:20,  Pochemuk 
Кутруповезет (18 марта 2018, 21:54)
Если итоговый вывод такой:
()
Т.к. перебор дерева игры построен на принципе Минимакса, то в данном случае он не пригоден. А другого способа перебора никто еще не придумал.

то что вы имеете в виду под:
Pochemuk (18 марта 2018, 19:03)

Нет ничего не возможного. Есть только цена, которую Вы готовы заплатить.
?

Например, готовы ли Вы отказаться от точной оценки хода и перейти к интервальной?

А что? Может быть в этом что-то и есть.

Например, если один ход дает интервал числа взяток [2, 3], а другой [4, 6], ясно, что выбирать надо первый. Но вот как быть, если второй дает интервал [1, 5]?

И, кстати, для таких интервальных оценок никакие альфа-бета отсечения еще не придуманы. Так что, готовьтесь к тому, что основная цена, которую придется платить - существенное падение производительности.
      » 18/03/2018, 22:24,  Фрэд 
Очень интересная и познавательная дискуссия, всем спасибо) Ситуация у меня в проге такая, что мне удалось, по-видимому, удачно организовать транспонирование и хэширование, в отличие от альфа-бета-перебора. Потому что, когда я его отключаю, время просчёта почти не увеличивается. А если отключить хэширование, то упомянутая здесь задача Галактионова считается часа 3 примерно. С хэшированием (у меня на компе), но без отсечений - 2 секунды. Помимо этого, правда, у меня организованы следующие правила отсечения заведомо неоптимальных ходов:

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

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

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

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

Пункты 3 и 4 не касаются мизеров, конечно. Эти правила заметно ускоряют перебор. Примерно раза в 3.

Таких правил можно напридумывать много. Но это увеличивает объём кода, а, кроме того, можно понаделать ошибок, заблокировав правильные ходы.

Покамест я хочу разобраться с альфа-бета-перебором. Идея-то его проста как дважды два четыре, но с применением его к расчёту раскладов возникли некоторые трудности. Ведь мы не можем оценить конкретный ход, пока не разыграем после него всё до конца. Единственное, что можем сделать - это проверить, доберём ли мы за оставшиеся после него ходы взяток больше, чем при более ранних вариантах. Ну, например. Выход с первой карты разыгрывающего дал ему 8 взяток. Проверяем выход со второй карты. И вдруг видим, что после первых двух кругов ходов взяток у него 0. Осталось 8 кругов ходов, т.е. больше 8 взяток он уже не возьмёт. Следовательно, отсекаем вариант выхода с этой карты. Всё это касается, конечно, и промежуточных вариантов розыгрыша. Вот это я и попытался реализовать. Но в результате скорость обсчёта раскладов выросла только в 2 раза примерно. Что мало.

Пока у меня всё)
      » 18/03/2018, 22:35,  Байкер 
Pochemuk (18 марта 2018, 21:01)
Байкер (18 марта 2018, 20:49)
Речь о том, чтобы найти оптимальный ход, когда он ваш. Конечно, перебор для этого в распасах не подходит. Особенно (точнее, хотя бы потому) если расклад еще не удалось посчитать. Вроде, как очевидно... Или нет? ))

Перебор не подходит для распасов даже и на открытых картах.

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

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

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

Чего ты "помешался" на этом переборе? Я тебе про то и толкую, что не перебором надо заниматься, а алгоритмизацией собственно преферанса как игры. "В преферанс поиграть не пробовали?.." )

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

И что? Из этого и надо исходить как из начального условия: "иногда ему может быть пофиг куда ходить". Что в этом удивительного или особенного?

Для всех наших ходов всегда можно получить точный окончательный результат, читай, оптимальное решение. Правда, в соответствии с исходными данными, которые автор алгоритма соизволил принимать во внимание, в соответствии с заданным критерием оптимальности и достигнутой точностью работы созданного алгоритма.
      » 18/03/2018, 22:42,  Pochemuk 
Фрэд (18 марта 2018, 22:24)
Помимо этого, правда, у меня организованы следующие правила отсечения заведомо неоптимальных ходов:

Я бы не назвал это отсечениями. Чтобы не возникало терминологической путаницы.

В терминах альфа-бета перебора отсечением называется прекращение уточнения результата хода, если предварительная оценка оказалась хуже, чем результат другого хода. Зачем делать ход, который заведомо хуже другого? А раз он не будет сделан, то и его точный результат нас не интересует.

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

П. 1 даже называть как-то не надо. И так понятно, что это надо применять.
П. 2 мы не реализовывали. Но вряд ли в нем много пользы при кэшировании. Ситуации, когда "все мои" быстро заносятся в кэш и по второму разу не обсчитываются.
П. 3, 4 это и есть эвристики лучшего хода. Только их не надо мешать в кучу с прочими улучшениями, а выделить отдельно.

Что касается максимально возможного числа взяток исходя из оставшихся карт, то это можно учесть корректировкой диапазона альфа-бета. И у нас и у Словеснова именно так и сделано.
      » 18/03/2018, 22:45,  Pochemuk 
Байкер (18 марта 2018, 22:35)
Чего ты "помешался" на этом переборе?

Я ни на чем не помешался.

Просто в этой теме обсуждают программы, которые работают на принципе минимаксного перебора.
      » 18/03/2018, 22:52,  Кутруповезет 
Фрэд (18 марта 2018, 22:24)

Вот еще по графическому интерфейсу:
- Если нажать кнопку "Разыграть до конца", то после розыгрыша невозможно нажать ни на "Новый расклад", ни на "Изменить расклад", приходится возвращаться к 1 ходу.

Это сообщение отредактировал Кутруповезет - 18/03/2018, 23:05
      » 18/03/2018, 23:03,  Фрэд 
Букву уже удалил, сам заметил)

Да, согласен, что надо сделать возможным переход к новому раскладу с любого момента розыгрыша текущего. Это делов на 5 минут в общем)
      » 19/03/2018, 12:10,  american_boy 
Pochemuk (18 марта 2018, 22:45)
Байкер (18 марта 2018, 22:35)
Чего ты "помешался" на этом переборе?

Я ни на чем не помешался.


Честно говоря, не понимаю, почему программисты ставят палки в колёса.
Не преферансисты должны подстраиваться под существующие методы перебора, а программисты, выслушав суть проблемы, сначала попытаться понять о чем говорят опытные преферансисты, потом взять какое-то время подумать, возможно, посоветоваться. И начать действовать как им говорят. Другого пути нет.
А тут сразу в одну минуту слышишь: нельзя, невозможно, нереально.
Кто как не опытные преферансисты подскажут логику принятия решений?
      » 19/03/2018, 12:46,  Байкер 
Какая-то польза тоже есть: все "стороны" согласились, что на поезде до Луны доехать нельзя. )
      » 19/03/2018, 15:02,  Невозмутимый 
да программисты походу видимо никогда в преферанс не играли, только пихают несчастным преферансистам свои методы

слава богу что нашлись готовые помочь ценным советом
« Предыдущая тема | Перечень тем | Следующая тема »
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей: