Главная В клубе 1954 Войти
Здравствуйте, гость Правила · Помощь

»  Оценка карты играющего при заданном сносе, Определение результата игры для мизера и игры на взятки Подписаться | Сообщить другу | Версия для печати
      » 19/03/2018, 22:31,  bamboo 
Не могу утверждать наверняка, но в данной ситуации думаю картина понятна всем. Хотя возможны варианты, когда определённые неясности всё-таки остаются.
Вцелом же, если бы не было определённых моментов, то так или иначе, вполне возможно сделать советующие выводы.
      » 20/03/2018, 22:10,  Сашун 
Сашун ( 4 мая 2000, 20:45)
Фьюмен Г.P. Общая теория игр, М., Физматиздат, 1952. Цитата

===== ГЛАВА 26. ГРУППОВАЯ СТРАТЕГИЯ. ИГРА ТРЕХ ИГРОКОВ =======

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

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

"Коалиционная" война, впрочем, имеет место почти в каждой партии, а в некоторых вариантах правил она даже узаконена. "Коалиционная" война начинается  тогда, когда наиболее активному игроку удается  построить потенциально выигрывающую позицию. Тогда оба его противника, временно забыв обо всех своих распрях, прикладывают все силы к тому, чтобы ee разрушить. Некоторые варианты игр содержат на этот случай правило объявления выигрышной позиции (даве или предложение увеличить ставку или предложение капитуляции).
Когда позиция объявлена, двое оставшихся  игроков решают, кто из них будет лидером. До тех пор, пока позиция не разрушена, лидер обычно играет за своего партнера так, будто ресурсы партнера являются его собственными. Правило лидера вводится  довольно редко, потому, что лидер в принципе всегда имеет возможность разрушать позицию преимущественно силами своего партнера, преследуя  исключительно своекорыстные цели. <p>Быстро начавшись, "коалиционная" война столь же быстро и заканчивается, потому что игрок, построивший выигрывающую позицию, после ее разрушения  оказывается  обычно совершенно обессиленным и временно перестает представлять угрозу для своих противников. Более того. Довольно часто, сокрушая  чужую позицию, другой игрок строит свою, и тогда бывшие противники объединяются  уже против следующего претендента на победу. И так далее, и так далее...

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

--------------------
С уважением, А.Малышев
      » 21/03/2018, 06:14,  платан 
Поэтому я играю на четверых, там вероятность того, что все трое смогут объединиться против меня, гораздо меньше, чем в игре втроём. Что я ненавижу на Гамблере больше всего - когда кто-то вылетает и заставляют доигрывать втроём - а ведь это совсем другая игра! Вы же не заставляете играющих втроём доигрывать в гусарика!
      » 8/04/2018, 13:39,  american_boy 
Сашун (20 марта 2018, 22:10)
Сашун ( 4 мая 2000, 20:45)
Фьюмен Г.P. Общая теория игр, М., Физматиздат, 1952. Цитата

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

Вот, дескать, 18 лет подряд толкую и никто так и не въехал в истинный смысл происходящего…

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

А теперь, вернёмся в 21 век.
Хотите явно сговориться? Тогда для начала вас накажут, потом забанят.
Неявно? Это передача мыслей на расстоянии? В 5 играх из 5 в авторассадке у вас это получится? На дистанции 40 в пулю? Приёмник не подкачает?
Выбросьте вы все эти книжки на свалку.
Поверьте, пройдёт ещё немного времени и очные турниры будут проходить за экранами мониторов, расставленными за игровыми столами в зале. Или настоящий преферанс – это по-прежнему, чтобы людям добыть огонь, надо заранее подготовить на относительно плоской поверхности продольную выемку, после чего начинать быстро-быстро водить по этой выемке деревянной палочкой, после образования на дне выемки тлеющий древесной пыли нужно воспламенить трут (древесную кору, сухую траву)?
В топку все ваши картонки!
После этого, можно переходить к конструктивному обсуждению существующих проблем.

Это сообщение отредактировал american_boy - 8/04/2018, 13:40
      » 24/04/2018, 02:09,  Фрэд 
Я значительно усовершенствовал свою прогу, правда, пока выложить не готов, там есть что подправить. Но сейчас она обсчитывает весь спектр раскладов, если задана одна рука и снос. И у меня такой вопрос:

Morozko_prr (28 нояб. 2017, 19:57)
Погонял тут на досуге прогу Словеснова на посчитанных мною ранее (ВРУЧНУЮ !!!wink.gif мизерах. Ответственно заявляю, что у нее очень и очень неплохой результат по МО. Погрешность не превышает 0,01 СЧМ (в скобках дается мой результат расчета):

1) На мизере Сашуна (В)_9(Д)_1097_ТД10987 (Ход чужой):
-2,00503 (-2,01365). Время расчета проги - 409 мин(**) (у меня с учетом занятости, отдыха и перепроверок моих расчетов ВРУЧНУЮ уходило примерно 2 недели в среднем),
---


Я прогнал этот мизер при условии, что играет Юг, а ход Востока. Среднее кол-во взяток получилось 2,3944 (см.ссылку на скрин в конце поста). А что значат вот эти цифры: -2,00503 (-2,01365)? То же самое? Почему не совпадают результаты? Может кто-то перепроверить? По идее у меня не должно быть ошибки, я проверял на многих раскладах. Или ваши результаты подразумевают что-то другое?

Кстати, у меня время расчёта составило 25 минут. Что в 25 раз медленнее, чем у Андрея и Николая, но почти в 20 раз быстрее, чем у Словеснова. Но сейчас не это самое главное.

Вот скрин.
      » 24/04/2018, 08:24,  Pochemuk 
Фрэд (24 апр. 2018, 02:09)
Среднее кол-во взяток получилось 2,3944 (см.ссылку на скрин в конце поста). А что значат вот эти цифры: -2,00503 (-2,01365)? То же самое? Почему не совпадают результаты? Может кто-то перепроверить? По идее у меня не должно быть ошибки, я проверял на многих раскладах. Или ваши результаты подразумевают что-то другое?

Да, они подразумевают несколько другое.

Ты считаешь среднее число взяток, а Морозко - МО.

При подсчете МО каждая взятая взятка считается за -1 условных очка, а чистый - за +1, а не за 0.
      » 24/04/2018, 09:26,  Фрэд 
Ага, понятно. Значит согласно моим данным МО будет: (71940-13925-42224*2-1650*3-46661*6-8456*7)/184756=-2.005028...

Т.е. в точности такой же результат, как и у БКП. Без всяких погрешностей. Что радует, значит я всё сделал правильно. Осталось только ещё раз в 20 повысить скорость) В принципе у меня есть идеи, как усовершенствовать алгоритмы транспонирования и хэширования, ну и ещё кое-что.

Понятно конечно, что это всё на известном сносе и без учёта торговли (т.е. возможного перебития мизера). Что нивелирует практическую ценность результатов.

Это сообщение отредактировал Фрэд - 24/04/2018, 09:28
      » 24/04/2018, 09:34,  Фрэд 
Только не могу понять одной вещи. Зачем вот это вот всё считать вручную? 2 месяца? И какой практический смысл в отбрасывании раскладов, где мизер перебивается? Если мы хотим приблизиться к реальности, то и снос должен быть не известен. Другими словами, не всегда надо оставлять голую 9-ку. Иногда голого валета пик. А я б даже иной раз и 9Д треф оставил, снеся 7 червей от длинной. Ибо на такой длинной масти перехват далеко не всегда работает.
      » 24/04/2018, 11:45,  Pochemuk 
Фрэд (24 апр. 2018, 09:34)
Если мы хотим приблизиться к реальности, то и снос должен быть не известен. Другими словами, не всегда надо оставлять голую 9-ку. Иногда голого валета пик. А я б даже иной раз и 9Д треф оставил, снеся 7 червей от длинной.

Всё правильно ... Вероятность не взять взятку и на Вs.gif и на 9c.gif при снесенной даме - весьма мала. Поэтому работать будут именно по одному из этих сносов. Что почти наверняка (но не всегда) позволит перехватить трефу дамой и отпихнуться девяткой - одна взятка. Ну или (если даму перебьют) позволит уменьшить паровоз на одну взятку.

И даже если не брать в рассмотрение это "хитрый" снос, то даже чередование пики и трефы весьма повысит шансы.
Вот здесь шансы остаться чистым при оставлении 9c.gif менее 40%. Чередуя пику/трефу их можно повысить до, грубо, 50% - в части случаев оставленная масть не будет ловиться, а в половине оставшихся случаев снос не угадают.

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

Т.е. нужно знать, с какой вероятностью мы возьмем по 3 взятки независимо от сноса, а с какой длина паровоза распределится 3:2 или 2:3 или 6:1 и т.д.

Посчитать это чисто вручную - малореально за разумное время. А вот при помощи "калькулятора" - вполне.
Главное - не надо даже учить его обсчитывать "угадайки". Механизм обсчета "угадаек" в смешанных стратегиях - это отдельная песня. Но вот подготовить необходимые исходные данные "калькулятор" вполне может.
      » 24/04/2018, 12:37,  Фрэд 
Со всем согласен кроме того, что даму могут перехватить. Не перехватишь ее) Вистующим надо сразу, ещё до хода решать, играть на голую 9 или на 9Д.Выбор, в общем-то очевиден, что надо сразу пихать 7-8 с двух рук под 9-ку. А то может глупо получиться: пойдут со старших, а у тебя там голая 9 и ноль взяток) А так по крайней мере одна.
      » 24/04/2018, 13:06,  Pochemuk 
Север
s -
c Q 9
d 10 9 7
h A 10 9 8 7
Запад
s 10 9 8 7
c K 10 8
d A Q 8
h -
Восток
s A K Q
c A J 7
d K J
h K J
Юг
s J
c -
d -
h Q

Я имею в виду именно "перехватить", а не заходить в старшую:

После проноса на черву Востока трефы с руки Запада режем трефу оставшейся фоской. Теперь пытаться положить даму бесполезно. Тому как перехватим тузом и на 7c.gif пронесем от Запада последнюю бубну.


Это сообщение отредактировал Pochemuk - 24/04/2018, 13:58
      » 24/04/2018, 15:44,  Фрэд 
А. Ну всё равно. Я положил 9. Что будет делать Восток? Бить? А если 9 голая?)
      » 24/04/2018, 16:42,  Pochemuk 
Фрэд (24 апр. 2018, 15:44)
А. Ну всё равно. Я положил 9. Что будет делать Восток? Бить? А если 9 голая?)

Ну ладно, уговорил ...

Тогда сначала отбираем третью бубну, проносим на ней Тc.gif и прорезаем трефу.

И перехватывай, не перехватывай ... 5 взяток.

Тут мизеряшему надо было перехватывать черву, заходить в 9c.gif и со скорбной рожей говорить: "Две взятки". Все согласятся, т.к. подумают, что 9c.gif бланковые smile.gif

Иначе вистующим придется решать: совать под эту девятку на 2/3 взятки, или отбирать ее и пытаться пихнуть под даму с вариантами на 1/6 взяток.

Конечно, 6 оно получше. Но 2 надежнее.

Вот такие многовариантные сносы с перехватами весьма трудно обсчитать. Одно дело, когда угадайка имеет место в раскладах без перехватов. Другое - когда с перехватами. Тут уже не два-три варианта сноса надо угадывать, а еще и решать задачу за вистующих: а почему не перехватил? А за играющего - а не перехватить/пропустить ли?

Это сообщение отредактировал Pochemuk - 24/04/2018, 16:53
      » 24/04/2018, 17:16,  Фрэд 
Ну да) Одну конкретную сдачу можно алгоритмизировать (мне кажется, что это не очень сложно) только если есть гарантированный подсад. И играть на него. На максимальный гарантированный подсад, и не идти на угадайки типа 0-5, если есть гарантированная одна. Это же касается и игры на взятки, только здесь уже становится важен контракт. Бывают же расклады, где вистующие могут дать гарантированные 6 взяток или пойти на угадайку 5-7. И если заказано 7, но надо давать гарантированные 6. А если заказаны 6 (вист например полуответственный), надо идти на угадайку 5-7.

А вот в случае угадаек на мизерах типа 0-сколько-то там, нужно, чтобы прога сыграла этот расклад несколько миллионов раз, накопила статистику, и на основе её делала ходы, иногда так, иногда эдак.
      » 24/04/2018, 20:35,  Pochemuk 
По поводу статистики - это к Искусственным Нейронным Сетям. Они и статистику набирают, и обрабатывают ее, и самокорректируются по ней ...

Вот только есть 2 момента применительно к ИНС:

1. ИНС, в основном, применяются с целью распознавания и кластеризации/классификации. Т.е. дают однозначный ответ - жив кот или мертв.
Для выработки смешанных стратегий нужно оперировать уже частично с нечеткими рекомендациями - насколько кот жив, насколько мертв, и насколько он собака.
Это решаемо, но использует другие более сложные модели ИНС с нелинейной функцией обратного распространения ошибки. Впрочем, судя по тому, что ИНС научили блефовать при игре в лимитный техасский холдем, ничего невозможного нет.

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

Другую сложность мы уже обсуждали - как заставить "калькулятор" забыть известный снос до момента выполнения критического хода? И чтоб это было без существенного падения производительности ...
А без "модели неизвестного сноса" про выработку смешанных стратегий и думать нечего.
      » 5/05/2018, 12:46,  extasy 
С нейросетями, применительно к преф-решателю, неоднозначная ситуация.
Проблем несколько:
Во-первых, это точность распознавания. Если перебор вариантов дает точный ответ, то ИНС оперирует приблизительными числами с некоторой погрешностью распознавания. В принципе, для некоторых задач это вполне подходит.
Во-вторых, это скорость. Минимальные требования к ИНС это два слоя с 300 нейронами на первом слое. А в реальности, потребуется каскад из таких нейросетей. При использовании обычного процессора время работы будет дольше, чем при переборе вариантов альфа-бета алгоритмом.

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

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

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

--------------------
the elephant has you..
      » 6/05/2018, 13:17,  Pochemuk 
extasy ( 5 мая 2018, 12:46)
Пока что совершенно непонятно как подойти к решению задач втемную. А если не получится создать приемлемый вариант на А-Б, то значит и не будет учителя для ИНС и придется обучать нейросеть на алгоритмах без учителя.

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

Мне вот даже не понятно, можно ли перебором решать более простую задачу: нахождение фиксирующих ходов вистующих при игре на открытых картах, но с неизвестным (многовариантным) сносом.

Я тебе уже писал в личной переписке, для интересующихся повторю и здесь:

Совместить перебор с альфа-бета отсечениями и поиск оптимальных (фиксирующих) ходов при многовариантном сносе представляется проблематичным.

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

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

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

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

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

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

Что касается обучением без учителя, то таки да ... Других вариантов не вижу.
Так и представляю, как сидят 3 мощных суперкомпьютера под управлением четвертого менее мощного сдатчика и самообучаются в игре друг с другом smile.gif

Самое интересное, что при таком самообучении у каждого может проявиться своя манера игры. Ведь британскими учеными научно доказано, что многослойные ИНС могут обладать множеством устойчивых локальных оптимумов и найти глобальный оптимум в процессе самообучения можно, скорее, случайно.
      » 8/05/2018, 04:22,  Фрэд 
Я всё-таки выложу свою последнюю версию, хотя дорабатывать там можно ещё много.

Краткое описание.
При запуске программы предлагается сформировать расклад из карт "колоды". При наведении мыши на любую из карт она подсвечивается и по краям её появляются стрелки. Нажав на выбранную, вы переместите карту в нужную руку или в снос (снос = "N"). Из руки в руку, а также из сноса и обратно карты также можно перемещать.

Логика формирования расклада:
Если на карте сноса нажать "N", она переместится обратно в колоду. Если на карте к.л. руки нажать "N", она переместится в снос, если там меньше 2-х карт; в противном случае в колоду. Больше 10 карт в одну руку не положится, соотв.стрелки будут неактивны.

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

Если полностью сформирована рука S и снос (остальные обе руки сформированы не полностью или вообще не сформированы), появляется окно "рассчитать все расклады для S?". Его можно игнорировать, продолжая формировать расклад, но если нажать, начнётся расчёт всех возможных раскладов, которых, как известно, 184756 штук, причём будут рассмотрены первые ходы со всех рук, а также (если первым ходит разыгрывающий) варианты ходов руки разыгрывающего со всех возможных принципиально различных карт (эквивалент первого хода втёмную, после чего вистующие вскрываются). Тут пока не отсекаются "глупые" ходы, типа с туза при чистом мизере, но на самом деле это не сильно замедляет просчёт. По сравнению с обычным просчётом (первый ход строго фиксирован, ходы втёмную не рассматриваются) расширенный просчёт медленнее примерно на ~20--50% в зависимости от структуры руки S. Время такого просчёта, к сожалению, пока довольно большое. От 2-3 минут для простых рук до получаса примерно. В среднем где-то минут 10-15. Счётчик посчитанных раскладов при этом высвечивается в правом верхнем углу, поэтому всегда известно, сколько раскладов посчитано к конкретному времени. Ближе к концу расклады считаются значительно быстрее, чем вначале, т.к. большая часть данных берётся из таблицы, формирующейся в процессе. По завершении просчёта данные в виде списка появляются на рабочей части экрана. (их я собираюсь усовершенствовать, т.е. отражать МО в вистах для различных контрактов, но это потом)

Просчёт одиночного расклада начинается, если нажать "готово". Но он всё равно не совсем одиночный. Просчитаются (помимо указанного первого хода и козыря) первые ходы со всех рук и 5 вариантов козырей (включая БК), а результаты будут отражены в таблице (для мизера вариант козыря, конечно, только один - БК). Появится меню, как и в первой версии программы. Можно включить подсветку оптимальных ходов, а также пойти самому вопреки этому и посмотреть, к чему это приведёт. Теперь не обязательно возвращаться к первому ходу, если хочется сформировать новый расклад, это можно сделать из любой глубины розыгрыша текущего. Также в меню предусмотрено и "рассчитать все расклады для S?" (см.выше). Но все расклады считаются только для руки S. Для одиночных раскладов можно выбрать в качестве разыгрывающего любую руку, но она переключится на S, если выбрать этот пункт меню. Кроме этого, таблица активна. Ячейки будут подсвечиваться при наведении мыши, и кликнув по нужной, вы смените козыря и/или первый ход (не формируя новый расклад).

Ссылка на прогу: https://dl.dropboxusercontent.com/s/t7jedbb...gnz/pref6.3.exe
      » 8/05/2018, 11:16,  Dukhin 
Фрэд ( 8 мая 2018, 04:22)
Я всё-таки выложу свою последнюю версию, хотя дорабатывать там можно ещё много.

Краткое описание.
При запуске программы предлагается сформировать расклад из карт "колоды". При наведении мыши на любую из карт она подсвечивается и по краям её появляются стрелки. Нажав на выбранную, вы переместите карту в нужную руку или в снос (снос = "N"wink.gif. Из руки в руку, а также из сноса и обратно карты также можно перемещать.

Логика формирования расклада:
Если на карте сноса нажать "N", она переместится обратно в колоду. Если на карте к.л. руки нажать "N", она переместится в снос, если там меньше 2-х карт; в противном случае в колоду. Больше 10 карт в одну руку не положится, соотв.стрелки будут неактивны.

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

Если полностью сформирована рука S и снос (остальные обе руки сформированы не полностью или вообще не сформированы), появляется окно "рассчитать все расклады для S?". Его можно игнорировать, продолжая формировать расклад, но если нажать, начнётся расчёт всех возможных раскладов, которых, как известно, 184756 штук, причём будут рассмотрены первые  ходы со всех рук, а также (если первым ходит разыгрывающий) варианты ходов руки разыгрывающего со всех возможных принципиально различных карт (эквивалент первого хода втёмную, после чего вистующие вскрываются). Тут пока не отсекаются "глупые" ходы, типа с туза при чистом мизере, но на самом деле это не сильно замедляет просчёт. По сравнению с обычным просчётом (первый ход строго фиксирован, ходы втёмную не рассматриваются) расширенный просчёт медленнее примерно на ~20--50% в зависимости от структуры руки S. Время такого просчёта, к сожалению, пока довольно большое. От 2-3 минут для простых рук до получаса примерно. В среднем где-то минут 10-15. Счётчик посчитанных раскладов при этом высвечивается в правом верхнем углу, поэтому всегда известно, сколько раскладов посчитано к конкретному времени. Ближе к концу расклады считаются значительно быстрее, чем вначале, т.к. большая часть данных берётся из таблицы, формирующейся в процессе. По завершении просчёта данные в виде списка появляются на рабочей части экрана. (их я собираюсь усовершенствовать, т.е. отражать МО в вистах для различных контрактов, но это потом)

Просчёт одиночного расклада начинается, если нажать "готово". Но он всё равно не совсем одиночный. Просчитаются (помимо указанного первого хода и козыря) первые ходы со всех рук и 5 вариантов козырей (включая БК), а результаты будут отражены в таблице (для мизера вариант козыря, конечно, только один - БК). Появится меню, как и в первой версии программы. Можно включить подсветку оптимальных ходов, а также пойти самому вопреки этому и посмотреть, к чему это приведёт. Теперь не обязательно возвращаться к первому ходу, если хочется сформировать новый расклад, это можно сделать из любой глубины розыгрыша текущего. Также в меню предусмотрено и "рассчитать все расклады для S?" (см.выше). Но все расклады считаются только для руки S. Для одиночных раскладов можно выбрать в качестве разыгрывающего любую руку, но она переключится на S, если выбрать этот пункт меню. Кроме этого, таблица активна. Ячейки будут подсвечиваться при наведении мыши, и кликнув по нужной, вы смените козыря и/или первый ход (не формируя новый расклад).

Ссылка на прогу: https://dl.dropboxusercontent.com/s/t7jedbb...gnz/pref6.3.exe

со стрелочками - очень хорошая идея. крайне удобно.
спасибо.

принимаются ли пожелания по дальнейшему развитию интерфейса?
      » 8/05/2018, 14:42,  Фрэд 
Да, конечно принимаются)
      » 8/05/2018, 15:06,  Dukhin 
Фрэд ( 8 мая 2018, 14:42)
Да, конечно принимаются)

Илья, можно через личку? )

michael.dukhin@yandex.ru
      » 8/05/2018, 15:37,  Фрэд 
Дополнение к описанию.

Хеш-таблица представляет собой динамический массив, каждым элементом которого является также динамический массив. Для одиночных раскладов её первая размерность устанавливается 2000000, вторая размерность - ноль (т.е. изначально она памяти не занимает). Данные в таблицу заносятся, когда номер хода кратен трём (т.е. на столе нет выхоженных карт), начиная с 3-го и до 24-го хода. 27-й ход (когда у всех по одной карте) заносить бессмысленно. Сначала расклад транспонируется по достоинству карт и по мастям (с учётом козыря), потом с помощью хеш-функции высчитывается ключ (максимально случайно в диапазоне от 0 до 2000000), и размерность ячейки таблицы с этим номером расширяется до 28, чтобы записать в неё расклад (максимальное число карт: 27 + чей ход). Каждая такая (любая из 28-ми) ячейка - размером 1 байт (8 бит), хотя это, я понимаю, расточительно. Для конкретной карты ведь достаточно 5 бит (+ ещё 1 бит для определения козырь/нет), но я пока не знаю, как это сделать без ущерба для всего остального (во встроенных инструментах среды программирования есть только переменные размером 1 байт, если хочется чего-то другого, надо формировать новый класс переменных, я этим не заморачивался). На самом деле, размерность устанавливается не 28, а 29. Одна ячейка резервируется под кэш, чтобы туда записать результат расклада, т.е. кол-во взяток, которое получается. Таблица работает по принципу цепочек, т.е. когда происходит коллизия, размер соотв. ячейки увеличивается ещё на 29. Т.е. в одну ячейку может быть записано несколько раскладов. Коллизии редки (меньше 1%), если таблица заполнена процентов на 10, но когда она заполняется наполовину и больше, коллизии могут достигать 50% и более. Как ни странно, это мало влияет на скорость расчёта (я экспериментировал с различными размерами).

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

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

Если выбирается "посчитать все расклады для S", размер таблицы устанавливается в 10 раз больше, т.е. 20000000. И она обнуляется всегда, когда задаётся новый расклад. Иначе будет занимать много оперативки. 20 млн и так многовато, но у меня на компе с оперативкой 2 гига считается без проблем.
      » 8/05/2018, 15:46,  Фрэд 
Dukhin ( 8 мая 2018, 15:06)
Фрэд ( 8 мая 2018, 14:42)
Да, конечно принимаются)

Илья, можно через личку? )

michael.dukhin@yandex.ru

Написал)
      » 9/05/2018, 16:03,  extasy 
Фрэд ( 8 мая 2018, 15:37)
Дополнение к описанию.

Хеш-таблица представляет собой динамический массив, каждым элементом которого является также динамический массив. Для одиночных раскладов её первая размерность устанавливается 2000000, вторая размерность - ноль (т.е. изначально она памяти не занимает). Данные в таблицу заносятся, когда номер хода кратен трём (т.е. на столе нет выхоженных карт), начиная с 3-го и до 24-го хода. 27-й ход (когда у всех по одной карте) заносить бессмысленно. Сначала расклад транспонируется по достоинству карт и по мастям (с учётом козыря), потом с помощью хеш-функции высчитывается ключ (максимально случайно в диапазоне от 0 до 2000000), и размерность ячейки таблицы с этим номером расширяется до 28, чтобы записать в неё расклад (максимальное число карт: 27 + чей ход). Каждая такая (любая из 28-ми) ячейка - размером 1 байт (8 бит), хотя это, я понимаю, расточительно. Для конкретной карты ведь достаточно 5 бит (+ ещё 1 бит для определения козырь/нет), но я пока не знаю, как это сделать без ущерба для всего остального (во встроенных инструментах среды программирования есть только переменные размером 1 байт, если хочется чего-то другого, надо формировать новый класс переменных, я этим не заморачивался). На самом деле, размерность устанавливается не 28, а 29. Одна ячейка резервируется под кэш, чтобы туда записать результат расклада, т.е. кол-во взяток, которое получается. Таблица работает по принципу цепочек, т.е. когда происходит коллизия, размер соотв. ячейки увеличивается ещё на 29. Т.е. в одну ячейку может быть записано несколько раскладов. Коллизии редки (меньше 1%), если таблица заполнена процентов на 10, но когда она заполняется наполовину и больше, коллизии могут достигать 50% и более. Как ни странно, это мало влияет на скорость расчёта (я экспериментировал с различными размерами).

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

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

Если выбирается "посчитать все расклады для S", размер таблицы устанавливается в 10 раз больше, т.е. 20000000. И она обнуляется всегда, когда задаётся новый расклад. Иначе будет занимать много оперативки. 20 млн и так многовато, но у меня на компе с оперативкой 2 гига считается без проблем.

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

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

--------------------
the elephant has you..
      » 9/05/2018, 18:23,  Фрэд 
Да, я читал (не помню, в этой теме или другой) про таблицу с вытеснением. Надо будет попробовать. Мне почему-то интуитивно кажется, что в этом случае будет удаляться много раскладов, которые нам рано или поздно встретятся повторно, и их придётся просчитывать как бы с нуля. Возможно, я не прав.

А идея насчёт разных таблиц для разнокарточных концовок мне очень нравится, это я как раз и сам хотел попробовать. Меньше памяти должно занять по-любому.
      » 10/05/2018, 11:16,  Pochemuk 
Фрэд ( 9 мая 2018, 18:23)
Да, я читал (не помню, в этой теме или другой) про таблицу с вытеснением. Надо будет попробовать. Мне почему-то интуитивно кажется, что в этом случае будет удаляться много раскладов, которые нам рано или поздно встретятся повторно, и их придётся просчитывать как бы с нуля. Возможно, я не прав.

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

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

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

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

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

Фрэд ( 8 мая 2018, 15:37)
Первый результат (кол-во взяток) в таблицу записывается при рекурсивном подъёме. Потом, если в другой ветви дерева ходов при рекурсивном спуске встречается такой же расклад (с учётом транспонирования), результат мгновенно берётся из таблицы, и дальнейшего спуска по ходам не производится. Альфа-бета-отсечения организованы таким образом, чтобы они не конфликтовали с хешированием. Потому что, когда мы отсекаем ходы по альфе, мы имеем только приблизительный результат, и его нельзя записывать в таблицу. Точнее, можно, но тогда надо отслеживать дополнительные условия, и это приводит только к увеличению времени расчёта. Поэтому эти отсечения игнорируются, если расклад, к которому мы возвращаемся после отсечения, уже захеширован, но туда ещё не записан результат (кол-во взяток). Это, конечно, во многом нивелирует эффективность отсечений, но всё равно увеличивает скорость в разы (а при отключённом хешировании скорость увеличивается на 2-3 порядка). Не знаю, может я тут сделал что-то неоптимально, опыта-то нету.


Напрягает меня здесь много чего.

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

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

Во-вторых, озадачила фраза "Альфа-бета-отсечения организованы таким образом, чтобы они не конфликтовали с хешированием".
Альфа-бета отсечения - это костяк перебора. Ничего в нем менять не надо. Это все равно, что прорубать окна/двери в несущих стенах. Может быть и красиво, только вот ни к чему хорошему не приведет.
Наоборот, кэширование прекрасно вписывается в концепцию перебора с отсечениями. Если кэшировать не результаты, а полученные границы оценок.

Еще раз изложу суть альфа-бета отсечений:

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

Т.е. вся работа ведется не с точными значениями, как в классическом минимаксном переборе, а с оценками и границами оценок. Границы в ходе перебора постепенно уточняются и сужаются. В конце концов они стянутся в точку - верхняя станет равна нижней.
При этом если текущая оценка больше или равна этой общей границы, то производится немедленная отсечка. А если меньше, то отсечка будет произведена на более высоком рекурсивном уровне при возврате.
За счет этого достигается значительное сокращение дерева перебора.
      » 10/05/2018, 18:31,  Фрэд 
Привет, Андрей) Да, я конечно открывал ссылки, которые ты мне присылал. Но обо всём по порядку)

Почему я не использовал классическую альфа-бету? Рассказываю. Когда я решил этим всем заняться, в первую очередь меня интересовала удобная визуализация раскладов и розыгрышей, с чего я, собственно, и начал. Ну то есть, вот карты, их можно двигать и делать ходы согласно правилам. Но как-то немного глупо их двигать просто так, поэтому я решил прикрутить что-то типа решателя, не имея на тот момент представления обо всех этих алгоритмах. Конечно гуглил, но не сразу въезжал, что к чему. И организовал я решение на основе классического минимакса. При этом долго думал, как же его сделать. Получалось, что только с помощью 30-кратного вложенного цикла. Который можно заменить рекурсивной процедурой, которая выглядит красиво, но нужно очень чётко представлять границы итераций, что для опытного программера, наверное, плёвое дело, а я только спустя время разобрался во всех нюансах. Ну и вот, в минимаксе используются точные значения. А чтобы использовать вместо него альфа-бету, нужно менять всю идеологию основной рекурсии, что мне делать очень не хотелось (но придётся, как я понимаю). И я прикрутил к уже реализованному минимаксу отсечения, которые строго говоря нельзя назвать альфа-бетой, но которые по сути выполняют ту же функцию. Сразу скажу, что я оперировал в качестве результата полным кол-вом взяток, которые берёт разыгрывающий, а не кол-вом взяток, которые получаются из хвоста розыгрыша. Но это на самом деле не принципиально, потому что в любой момент розыгрыша я знаю, сколько уже взяток он взял, они фиксируются в глобальной переменной.

Теперь о том, как это работает (пошагово). Мы проверили ход первой картой, например, разыгрывающего (не важно, это может быть самый первый ход или где-то в глубине розыгрыша), рассмотрели все ответы на него и получили, например, 6 взяток. Проверяем ход второй картой и, например, видим, что какой-то ответ вистующих даёт те же 6 взяток. Всё, дальнейшие ответы не рассматриваем. В реализации это выглядит так: на некоторой глубине рекурсии (когда мы по ней поднимаемся) мы рассмотрели все варианты ответов на некий ход ВИСТУЮЩЕГО и получили результат для разыгрывающего, например, 6. Перед тем, как перейти к рассмотрению следующего хода ВИСТУЮЩЕГО и ответов на него, мы производим проверку, а нужно ли это делать? Т.е. мы проверяем ход РАЗЫГРЫВАЮЩЕГО, который был сделан перед этим . И если это был не корневой ход, то мы сравниваем сравниваем результат хода ВИСТУЮЩЕГО на текущей глубине рекурсии с результатом предыдущих ходов РАЗЫГРЫВАЮЩЕГО на предыдущей глубине, они все записаны в массив глобальных переменных. И если мы видим, что этот результат был 6 или больше, мы следующие ходы ВИСТУЮЩЕГО на текущей глубине рекурсии не рассматриваем, а моментально перескакиваем на предыдущую глубину, где ходил РАЗЫГРЫВАЮЩИЙ, и уже начинаем рассматривать следующий его ход. Причём мы можем перескочить сразу на несколько уровней вверх, т.к. вистующие могут делать до 4-х ходов подряд, и мы естественно изначально проверяем это. Т.е. на той "глубокой" глубине, где ходил вистующий, мы проверяем, а когда же последний раз ходил разыгрывающий, а это может быть один ход назад, два, три или четыре. Всё это, конечно, касается и противоположной стороны, т.е. вистующий и разыгрывающий меняются местами, только разыгрывающий максимум может сделать не 4 хода подряд, а 2.

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

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

Кстати, насчёт мультитейбла. Ну я его сделал (дело 10 минут). На массиве раскладов скорость возросла примерно процентов на 7. Но коллизии всё равно есть. Причём их даже больше, но это я связываю с тем, что вместо одной таблицы на 2 млн ячеек я сделал 8 таблиц по 300 000 ячеек (точнее, переменная, описывающая таблицу, осталась одна, я просто ввёл для неё ещё одну размерность). З00 тыщ судя по всему маловато даже для раскладов с одинаковым кол-вом карт.

У меня пока всё)
      » 10/05/2018, 19:15,  Фрэд 
Забыл сказать. В моей реализации нынешней (без оценки границ, а с точными значениями) я примерно представляю, как можно организовать расчёт расклада с неизвестным сносом, чтобы это не сильно увеличивало время расчёта. Пока всё очень умозрительно, но мысли есть. С классической альфа-бетой как-то пока вообще непонятно, как это сделать.
      » 11/05/2018, 12:46,  Кутруповезет 
Фрэд (10 мая 2018, 18:31)

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

То, что здесь описано, это как раз алгоритм бета-отсечения - когда рассматривается ход вистующих. А вот альфа-отсечение - когда рассматривается ход играющего - у вас не описано. Если его действительно в вашей программе нет, то его можно добавить без изменения всей идеологии, и это должно дать не меньшее ускорение.
      » 11/05/2018, 13:20,  Pochemuk 
Фрэд (10 мая 2018, 18:31)
Мы проверили ход первой картой, например, разыгрывающего (не важно, это может быть самый первый ход или где-то в глубине розыгрыша), рассмотрели все ответы на него и получили, например, 6 взяток. Проверяем ход второй картой и, например, видим, что какой-то ответ вистующих даёт те же 6 взяток. Всё, дальнейшие ответы не рассматриваем.

Вот теперь я начал понимать твой алгоритм. И могу сказать, что это совсем не алгоритм альфа-бета отсечений. Чем-то похожий, но не он.

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

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

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

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

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

В алгоритме альфа-бета отсечений происходит почти то же самое, но и еще кое что:
На каждый уровень рекурсии приходит не только оценка верхней границы БЕТА, но и оценка нижней границы АЛЬФА, полученная ранее из анализа параллельных ветвей.
Таким образом, у нас нет необходимости давать нижней границе фиктивное низкое значение перед переборм вариантов. Мы уже имеем вполне конкретное рабочее значение. И при передачи хода противнику (уже в первом варианте нашего хода) эта АЛЬФА станет для него вполне конкретной оценкой верхней границы результата соперника БЕТОЙ. Реальной, а не завышенной, как у тебя!!!

В результате уже при разборе первого варианта ходов отсечений будет гораздо больше.

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

Немножко лирического отступления:

Давным давно, в далекой, далекой галактике когда мобилы были большими, я переписывался со Словесновым. По поводу того, почему у меня так медленно считает. Ну и он мне указал на мою ошибку - она была именно такой smile.gif

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

Фрэд (10 мая 2018, 18:31)
Сразу скажу, что я оперировал в качестве результата полным кол-вом взяток, которые берёт разыгрывающий, а не кол-вом взяток, которые получаются из хвоста розыгрыша. Но это на самом деле не принципиально, потому что в любой момент розыгрыша я знаю, сколько уже взяток он взял, они фиксируются в глобальной переменной.

Можно и так, но это неудобно при кэшировании ...

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

Фрэд (10 мая 2018, 18:31)
Кстати, насчёт мультитейбла. Ну я его сделал (дело 10 минут). На массиве раскладов скорость возросла примерно процентов на 7. Но коллизии всё равно есть. Причём их даже больше, но это я связываю с тем, что вместо одной таблицы на 2 млн ячеек я сделал 8 таблиц по 300 000 ячеек (точнее, переменная, описывающая таблицу, осталась одна, я просто ввёл для неё ещё одну размерность). З00 тыщ судя по всему маловато даже для раскладов с одинаковым кол-вом карт.

Это потому что все таблицы одинакового размера. А этого не нужно.

Для 9-карточных концовок с избытком хватит таблицы из нескольких сот ячеек.
Для 2-карточных концовок, вообще, достаточно 2-3 десятков ячеек.
А самые большие таблицы нужны для 5-6-7-карточных концовок, наверное. Там уже счет пойдет на десятки и сотни тысяч. Вот сэкономленный объем и надо им отдать.
« Предыдущая тема | Перечень тем | Следующая тема »
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей: