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

»  Оценка карты играющего при заданном сносе, Определение результата игры для мизера и игры на взятки Подписаться | Сообщить другу | Версия для печати
      » 2/12/2017, 11:42,  Kirk 
Протокол-то проще: клик по кнопке, или выбор из списка - и все дела.
Но вот что на кнопке должно быть написано, и что она делать должна, нажавшись... это ж все надо заранее придумать! Вот к этому-то "заранее" программисты 1970-х и были морально не готовы.
      » 8/12/2017, 21:49,  american_boy 
Нейросеть AlphaZero разгромила действующего чемпиона мира среди компьютерных программ Stockfish


Нейросеть AlphaZero – разработка компании DeepMind – победила сильнейшую шахматную компьютерную программу Stockfish 8.
Соперники провели 100 партий с контролем 1 минута на ход. AlphaZero выиграла 28 партий (25 белыми) и сыграла вничью 72 партии – общий счет 64:36.
AlphaZero – более универсальная версия нейросети AlphaGo Zero, которая в свою очередь является улучшенной версией AlphaGo. В мае 2017 года AlphaGo победила сильнейшего игрока в го Кэ Цзе.
В отличие от других шахматных программ (в том числе Stockfish) AlphaZero выбирает ход не за счет перебора возможных ходов, а применяя алгоритмы, которые вырабатываются при обучении в играх с самой собой. Для сравнения: AlphaZero рассматривала 80 тысяч позиций за секунду, Stockfish 8 – 70 миллионов позиций за секунду.
Известно, что AlphaZero обучалась шахматам, зная только правила игры. После 4 часов игры с самой собой нейросеть была готова к партиям против Stockfish 8.




Ключевое слово "разгромила".

Далее, важно отметить: "Известно, что AlphaZero обучалась шахматам, зная только правила игры" и "После 4 часов игры с самой собой нейросеть была готова к партиям против Stockfish 8".

ну и последнее 28 побед +72 ничьи=100. ни одного поражения.

такие вот делишки

Это сообщение отредактировал american_boy - 8/12/2017, 21:51
      » 8/12/2017, 22:08,  bamboo 
фигасе Stockfish 8 лох лохом
      » 8/12/2017, 22:10,  Apophis 
не, ну в техасский холдем не факт. тут рулетка канешно, не та игра.
      » 8/12/2017, 22:12,  american_boy 
ну вот. все отметились.
я тоже так считаю
      » 9/12/2017, 12:09,  Pochemuk 
Apophis ( 8 дек. 2017, 22:10)
не, ну в техасский холдем не факт. тут рулетка канешно, не та игра.

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

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

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

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

Это сообщение отредактировал Pochemuk - 9/12/2017, 12:10
      » 9/12/2017, 16:49,  Pochemuk 
И еще вот какая мысль о том, почему сложно приспособить НС к преферансу и другим играм с неполной информацией:

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

Задача определения "Хороший/Плохой ход (решение)" тоже кое-как вписывается в эту область, только вот всё дело в том, что в преферансе хорошим решением может быть не конкретное "чистое" решение, а смешанная стратегия.

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

А это уже ни разу не задача классификации/кластеризации.

Я, конечно, обладаю познаниями в НС на уровне "исчезающе малая величина", но предполагаю, что такая задача перед НС, играющей в шахматы, не ставилась :)
      » 9/12/2017, 19:39,  american_boy 
да коллега, как мы видим, НС умеет играть только в игры с полной инфой. Нормальных прог по игре с неполной инфой по сути нет. Тут ей придётся иметь дело только с жалкими людишками.
      » 10/12/2017, 02:03,  Невозмутимый 
да ето все фигня Cepheus давно уже возюкает не только людей но и других ботов

HFT trading и тп боты впереди планеты всей. Преферанс не решен только потому что никому не интересно его решать
      » 10/12/2017, 12:38,  Pochemuk 
Невозмутимый (10 дек. 2017, 02:03)
да ето все фигня Cepheus давно уже возюкает не только людей но и других ботов

Ссылки по теме:

http://www.gipsyteam.ru/news/4362-proschay-limitnyy-holdem

http://www.pokeroff.ru/limitniy-ha-holdem-...en-post-2898582

Только там речь идет о лимитном хлдэме.

Это сообщение отредактировал Pochemuk - 10/12/2017, 13:23
      » 10/12/2017, 17:19,  Невозмутимый 
Принципиальной разницы нет. Дерево решений будет гораздо больше, поэтому создать GTO approximation будет труднее но это вопрос исключительно ресурсов.
В играх с неполной информацией нет ничего волшебного, боты потихоньку доедают людей и там.
      » 11/03/2018, 05:24,  Фрэд 
Сам ни разу не программист, но накатал такой простенький графический интерфейс. Чтобы он не был совсем унылым, заодно сюда же прикрутил и решение преферансных раскладов на открытых картах (с подсказками оптимальных ходов), хотя, конечно, этот велосипед был изобретён много лет назад. Но программа Словеснова у меня на ХР не работает, да и было интересно самому сделать. Экзешник залил на дропбокс: вот сюда.

Проверил на винде ХР (обязателен фреймворк 4.0),7,8,10. На десятке графика как-то странно расползается (а может, что-то с настройками монитора было не то), на остальных системах работает норм, только размеры шрифта различаются. Минимальный размер рабочего поля 1200х700, его можно менять в сторону увеличения (т.е. окно программы делать больше/меньше).

Скорость просчёта раскладов меня честно говоря пока не очень удовлетворяет, некоторые сложные расклады считаются десятки секунд (один расклад), особенно мизера на совсем не мизерной карте. У меня есть идеи, как ускорить, но нужно будет перелопатить значительную часть алгоритма. Конечно, в случае просчёта спектра раскладов (при фиксированной одной руке) каждый расклад будет считаться гораздо быстрее, но если их будет сто тыщ, пока не знаю, как долго это будет. Это я ещё не реализовал (хотя хочу). Также как и оптимальную игру против играющего на открытых картах, но с плавающим сносом.

Мне интересно, как у вас это будет работать. Может я не все глюки-баги отловил. Может ругаться антивирус, но не верьте ему, нет здесь вирусов)

Выглядит это примерно так: ссылка на яндекс-фотки

Можно, кстати, это рассматривать как задачу для "песочницы"wink.gif
      » 11/03/2018, 11:46,  Pochemuk 
Что-то я мало чего в этой программе понял ...

Выглядит она не совсем так, как на скрине с яндекс-фоток:

1. Нет левого меню.
2. Области интерфейса разделены линиями, что как-то хуже смотрится.
3. Нет области для сноса.
4. Зачем-то окно программы работает в режиме "всегда сверху".

Вобщем не смог даже толком раскидать карты, не говоря о том, чтобы запустить.
      » 11/03/2018, 16:52,  american_boy 
Если отбросить несущественное (интерфейс, который всегда можно подкрутить), а перейти сразу к главному – к попытке реализовать плавающий снос, то задача очень своевременная.
И почему только обращают внимание на несущественное? И так понятно, что интерфейс надо полностью менять. Не об этом же должна голова болеть! Мне это напомнило картину – Шуре Остап дал 2 т.р., а он с ними в автобусе за 5 копейками полез и просрал эти 2 т.р. Чел же о другом толкует. Ну как же так? Показывают белое – видят чёрное. Также мне это напоминает другую картину: в бою мы выпускаем ракету по вражескому самолёту, а он зажигает спичку, прикуривает, бросает её в сторону от самолёта и наша ракета не обращая внимания на самолёт, летит поражать эту спичку. Ну как так? Ещё пример: мы ползём по минному полю, разминируем мину за миной. И тут пролетает красивая птичка, а мы говорим: "ой, какая красивая птичка! Дай ка я её получше рассмотрю". Не до птичек нам со спичками сейчас! Не разменивайтесь вы на 5 копеек!

В подтверждение своих слов (о том, что всё нужно делать грамотно, профессионально, на высшем уровне) привожу несколько своих работ.

вот, пожалуйста, полюбуйтесь


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

Прогу запустил, всё работает. Давайте идти дальше.
Тут нужна идея. А потом и алгоритм. Идеи могу взять на себя. Важно, чтобы мои идеи исполнялись. На начальном этапе не плохо было бы разобрать прогу марьяж и проверить, как она работает против плавающего сноса. Или убедиться, что она всё-таки подгладывает. Надо сделать из марьяжа - решатель против плавающего сноса. Это очень круто продвинет преферансную мысль. Если окажется что, прога подглядывает – перейти к другой проге, называется Пуля. Правда она мне не нравится, т.к. косячит часто. Она то точно снос не знает, а начитать с чего то надо. Идеально - выйти напрямую на программистов этих прог. Если упрётся в бабки – сумму до 10 т.р. могу пожертвовать лично. А сколько таких как я, представляете? Так что, кое что будет. Программистов можно успокоить этим на первом этапе. Это я шучу. Естественно всё придётся делать нам самим.

Итак мы подошли к сути. Плавающий снос бывает следующих типов:
1. Возможен "безопасный розыгрыш". Чтоб это прога чётко фиксировала и сразу сообщала об этом.
2. Возможен "безопасный розыгрыш" до 2, 3, 4-ого и т.д. хода. Крайне важно уметь делать "тихие ходы", в течении которых, наш опп может открыть свои карты раньше времени. Тут прога должна сообщать, что "безопасный розыгрыш" возможен до 2, 3, 4-ого и т.д. хода.
3. "а дилемма ли это вообще?" часто дилеммой называют не то, что таковой не является. Например, у игрока на 3-й руке карта до сноса ТДхх-КД10-ТД10-КВ или ТДхх-КД10-ТД10-К7, как играть? Да понятно же как. Совсем другое дело если карта ТДхх КД10-ТД7-КВ – тут уже реальная дилемма.


4. "тяжёлый случай", когда в определённый момент всё-таки надо определяться на какой снос играть. Как тут играть? Ответ: если уметь делать 1-е , 2-е и 3-е, то уже пофиг.



Зададимся, друзья, сейчас более важным вопросом: как СНОСИТЬ игроку? ибо дилеммы вистующих действительно могут быть неразрешимы. Именно игроку важно знать какой снос оптимален. С игрока надо начинать, как ни крути. Перефразирую Морозку : важно не то как будут ловить (* на мизере), важно то каким ДОЛЖЕН быть снос при определённых вероятностях отлова каждой дырки на мизере.
      » 11/03/2018, 17:26,  Фрэд 
Pochemuk (11 марта 2018, 11:46)
Что-то я мало чего в этой программе понял ...

Выглядит она не совсем так, как на скрине с яндекс-фоток:

1. Нет левого меню.
2. Области интерфейса разделены линиями, что как-то хуже смотрится.
3. Нет области для сноса.
4. Зачем-то окно программы работает в режиме "всегда сверху".

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

Ну там надо сперва раскидать карты к Югу, Западу и Востоку, а 2 оставшиеся и будут прикупом. Появится окошко "готово?", по нему кликнуть, после чего произойдёт расчёт и интерфейс преобразуется к тому виду, как на скрине. Наверное было бы проще, если бы все карты изначально были, например, у Юга, от которого их раскидывать к Востоку, Западу и в прикуп (меньше действий мышкой), но это, если что, всё решаемо и непринципиально. То, что окно всегда сверху, косячок, согласен.
      » 11/03/2018, 17:38,  Фрэд 
american_boy, насчёт Марьяжа могу сказать следующее. Если в партнёрах нет Рентгенов, карт они не видят. Бывали случаи неоптимального их розыгрыша при моём неизвестном сносе. Когда снос очевиден, конечно, ошибок они не делают и считают быстро. Но на распасах Марьяж играет оч.слабо и предсказуемо. Если поставить конвы, максимально близкие к здешнему Питеру, я у них всё на распасах и выигрываю в основном, хотя сам далеко не мастер. 5-10 вистов на сдачу при длительной игре.

Насчёт реализации плавающего сноса, понятно, что на каком-то ходу надо делать выбор, на какой снос играть. И минимизировать потери/максимизировать бонусы при этом.
      » 11/03/2018, 19:03,  american_boy 
Я бы сказал что распас и пас/пика в марьяже отстой. А вот вист всветлую играет чётко. Отловить дилемный снос играясь в марьяж просто нереально ибо кучу времени займёт, гораздо удобнее вырезать из марьяжа вист всветлую, назвать это решателем против плавающих сносов и дальше улучшать этот компонент.

Кстати в проге Словеснова просто необходимо сделать такую фишку: программа играет против одного сноса, а на самом деле игрок снёс по другому. Интересна разница, когда игра идёт против одного сноса (расчет всех раскладов), а снос оказывается другим! Фишка должна быть простой для реализации на первый взгляд.

Кстати, на проге Словеснова пробовал начать научное исследование на тему : когда всё-таки оставлять смягчение в ситуациях Тхх-х и ТДх-х . Т.е. всего 4 варианта сноса: Тх(х)-(х) или Т(хх)-х, ТД(х)-(х) или Т(Дх)-х.
Без этой фишки решить эту задачу века не удаётся.
      » 12/03/2018, 13:06,  Pochemuk 
american_boy (11 марта 2018, 19:03)
Я бы сказал что распас и пас/пика в марьяже отстой.  А вот вист всветлую играет чётко.

Это Вы имеете в виду Марьяж для Винды?

Я в него уже несколько лет (около 5) не играю. Зла не хватает ибо. И генератор там конкретно косячный (а что еще от 24-битного LGA ожидать? ...). И розыгрыш втемную, мягко говоря, странный ...

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

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

Например, при третьей руке {К 9}{Т Д}{К 9}{Т К Д В 10 9} есть неплохой шанс обмануть программу. Надо только знать, что она сносит сама в таких случаях и снести по другому.

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

Пример (Юг на 3-й руке играет 8БК):
Запад
s J 8 7
c A 9 8
d Q 7
h J 9
Восток
s 10 9
c J 10
d J 9 8
h Q 8 7
Юг
s A K Q
c K Q 7
d A K 10
h A K 10

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

Т.е. мы пытались выяснить, какие ходы приводят к лучшему результату при всех возможных сносах (известных). Но этого оказалось мало. Причем последствия хода могут проявится не непосредственно в результате него, а существенно позже.
      » 12/03/2018, 15:42,  Фрэд 
Не совсем понял, в чём фишка последнего расклада. Если хотим зафиксировать 8, выходим с мелких треф, на пику несём вторую трефу от Востока. Или имеется в виду, что кто-то может блефануть и оставить в трефе синглет?

Короче, алгоритм игры на неизвестном сносе наверное должен быть примерно такой. Играющий играет как бы на 12-ти картах, в нужный момент снося нужную, а вистующие смотрят, есть ли при таком варианте игры фиксированный подсад. Если есть, играют на него. Если нет, играют на угадайку. Это так, очень грубо пока.
      » 12/03/2018, 23:32,  Pochemuk 
Фрэд (12 марта 2018, 15:42)
Если хотим зафиксировать 8, выходим с мелких треф, на пику несём вторую трефу от Востока.

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

Но при игре на известном сносе можно трефу не пропускать, тому как на третью пику мы теперь будем знать, какую красную масть можно нести.

Т.е. тезис "Если ход является допустимым при любом известном сносе, то он является допустимым и при сносе неизвестном" в корне не верен. "Любой" и "неизвестный" в данном случае не синонимичны.

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

Фрэд (12 марта 2018, 15:42)
Короче, алгоритм игры на неизвестном сносе наверное должен быть примерно такой. Играющий играет как бы на 12-ти картах, в нужный момент снося нужную, а вистующие смотрят, есть ли при таком варианте игры фиксированный подсад. Если есть, играют на него. Если нет, играют на угадайку. Это так, очень грубо пока.


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

В общем, нужен какой-то оригинальный подход, позволяющий находить угадаечные концовки в процессе перебора, но без вот этих 12 карт. Возможно ли это в принципе - не понятно.
      » 13/03/2018, 00:35,  Фрэд 
Pochemuk (12 марта 2018, 23:32)
Т.е. тезис "Если ход является допустимым при любом известном сносе, то он является допустимым и при сносе неизвестном" в корне не верен. "Любой" и "неизвестный" в данном случае не синонимичны.

Ну это-то понятно.


Pochemuk (12 марта 2018, 23:32)
Фрэд (12 марта 2018, 15:42)
Короче, алгоритм игры на неизвестном сносе наверное должен быть примерно такой. Играющий играет как бы на 12-ти картах, в нужный момент снося нужную, а вистующие смотрят, есть ли при таком варианте игры фиксированный подсад. Если есть, играют на него. Если нет, играют на угадайку. Это так, очень грубо пока.


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

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

Я, вообще, когда в конце того года от нечего делать решил "решатель" написать (сначала скачал БПС, он не запустился, а легендарная прога МишиХ канула в лету), думал, ха! Какие тут нафик таблицы для одного расклада! А оказалось, что без таблиц даже один расклад считается порой минуты и десятки минут. Даже если исключить из рассмотрения ходы с соседних карт (в случае трельяжа и т.п.). Пришлось мудрить. В общем, сделал таблицу на 2 млн ячеек, куда пишутся промежуточные расклады после каждого 3-го хода (начиная с 6-го и заканчивая 24-м), и идёт проверка, встречались ли они уже при другом ходе розыгрыша. Ну и ещё они перед записью в таблицу "минимизируются". Т.е. если в какой-то масти, например, ТД7 (и больше ничего), это тоже самое, что 987. Это значительно убыстряет подсчёт.
      » 13/03/2018, 00:53,  Фрэд 
Кстати, я убрал этот глючок, что окно программы было всегда поверх других окон. Просто добавлением в код одной короткой строчки. Не знаю, почему не сделал это сразу) Если что, залил сюда новый вариант.

Любопытно, когда тестировал всё это дело на простых и не очень раскладах, нашёл несколько косяков в этюдах из книжки Лесного, например) В этюде, известном, как задача Галактионова (кажется, даже в Марьяже она есть), за вистующих в одном месте ход указан неправильно, он приведёт не к 4-м, а к 5 взяткам. Как же так можно?)

А вот тот мизер, который у меня по ссылке на яндекс-фотки, кто-нить смотрел? Не то чтобы я его придумал, он спонтанно получился в процессе тестирования. В нём, как оказалось, есть некоторая изюминка, которая сходу может быть не видна.
      » 13/03/2018, 03:17,  Фрэд 
Фрэд (11 марта 2018, 05:24)
Скорость просчёта раскладов меня честно говоря пока не очень удовлетворяет, некоторые сложные расклады считаются десятки секунд (один расклад), особенно мизера на совсем не мизерной карте. У меня есть идеи, как ускорить, но нужно будет перелопатить значительную часть алгоритма.

Подправил алгоритм, скорость просчёта увеличилась примерно в 2,5-3 раза. Оно здесь.
      » 13/03/2018, 13:07,  Pochemuk 
Фрэд (13 марта 2018, 00:35)
Я, вообще, когда в конце того года от нечего делать решил "решатель" написать (сначала скачал БПС, он не запустился, а легендарная прога МишиХ канула в лету), думал, ха! Какие тут нафик таблицы для одного расклада! А оказалось, что без таблиц даже один расклад считается порой минуты и десятки минут. Даже если исключить из рассмотрения ходы с соседних карт (в случае трельяжа и т.п.). Пришлось мудрить. В общем, сделал таблицу на 2 млн ячеек, куда пишутся промежуточные расклады после каждого 3-го хода (начиная с 6-го и заканчивая 24-м), и идёт проверка, встречались ли они уже при другом ходе розыгрыша. Ну и ещё они перед записью в таблицу "минимизируются". Т.е. если в какой-то масти, например, ТД7 (и больше ничего), это тоже самое, что 987. Это значительно убыстряет подсчёт.

Я БПС на работе (Win8) не рискую запускать, а дома тоже XP. Поставил виртуалку, установил на нее Win7 - заработала. Но тормозит ужасно. Одну руку играющего при неизвестном раскладе вистующих может полчаса обсчитывать. Многовато будет, многовато ...

С Михаилом Кривчиковым я списывался по поводу PrefGuru. Исходники утеряны после того, как жесткий диск умер. Но особых сожалений это не вызвало, т.к. эта программа считает очень медленно.

Минуты и десятки минут? Ну это слишком!
Я несколько лет назад написал на Delphi альфа-бета перебор без кэширования (без запоминания). Так там счет шел на секунды, десятки секунд в худшем случае. И это даже практически без всяких ускорителей для прогнозирования лучшего хода. Единственное что было сделано - вначале рассматривались ходы, форсированно берущие взятку, а потом - отдающие. Даже этого было достаточно, чтобы сократить время перебора раза в 2.

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

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

В общем, я могу рассказать всё это подробно, но думаю, Вам стоит обратиться к Николаю. Всё-таки, реализация была именно его от нуля. А я просто играл роль "научного руководителя" - подбирал алгоритмы, способы, представления ... и спорил с ним, спорил, спорил smile.gif
Если для нашей программы сумеете сделать простой, но аккуратный интерфейс, думаю, он тогда перестанет стесняться и выложит ее в открытый доступ smile.gif
      » 13/03/2018, 21:26,  american_boy 
Предлагаю всё-таки начать с 2-х вариантов сноса. Игру против всех возможных сносов пока опустим. Это реальная задача или нет?

Я сам указываю проге "снос А" и "снос Б".

Результат должен быть таким:

При сносе А = ТД(х)-(х):
1) И вистующие играют на этот снос (т.е. угадывают снос) = то 5,5 взяток.
2) Вистующие играют на снос Б (т.е. ошибаются в сносе) = то 5,6 взяток
И наоборот,
При сносе Б = Т(Дх)-х:
3) И вистующие играют на этот снос (т.е. угадывают снос) = то 5,4 взятки.
4) Вистующие играют на снос А, (т.е. ошибаются в сносе) то 5,6 взяток

Ответьте мне на этот простой вопрос.
      » 13/03/2018, 23:06,  Pochemuk 
american_boy (13 марта 2018, 21:26)
Предлагаю всё-таки начать с 2-х вариантов сноса. Игру против всех возможных сносов пока опустим. Это реальная задача или нет?

Ответьте мне на этот простой вопрос.

Не в такой постановке ...

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

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

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

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

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

Но как воплотить это на практике - не придумал. Кроме того, такие "нечеткие" карты не вписывались совершенно в механизм транспонирования раскладов. Пришлось бы все менять к чертовой бабушке, а у нас это было так изящно сделано.
      » 13/03/2018, 23:58,  american_boy 
Уже и ошибки нашли… хотя я ничего пока не предлагал как это сделать.

Абстрагируйтесь вы от общего, решаем частный пример.

Я игрок, у меня рука ТК87-ТД87-ТД7-7 и я должен сделать снос. Варианта у меня всего 2. Не 1, не 3, не 4 не 5, а 2.

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

Проге не надо думать над приоритетностью одного сноса над другим.

я не заставляю прогу угадывать на 100% снос. Безопасного розыгрыша может и не быть, это понятно. ей нужно только обсчитать все варианты и дать ответ в том виде который я указал.

Хитрость реализации в том, что в определённый момент времени всплывает другой снос… я об этом и спрашиваю. Это можно алгоритмизировать?

Мне надо подумать над алгоритмом. Завра напишу как сделать.

осталось/не осталось смягчение - это ведь тоже угадайка, не прада ли?)))

Это сообщение отредактировал american_boy - 14/03/2018, 00:12
      » 14/03/2018, 12:53,  Pochemuk 
american_boy (13 марта 2018, 23:58)
Уже и ошибки нашли… хотя я ничего пока не предлагал как это сделать.

Абстрагируйтесь вы от общего, решаем частный пример.

Я игрок, у меня рука ТК87-ТД87-ТД7-7 и я должен сделать снос. Варианта у меня всего 2. Не 1, не 3, не 4 не 5, а 2.

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

Проге не надо думать над приоритетностью одного сноса над другим.

я не заставляю прогу угадывать на 100% снос. Безопасного розыгрыша может и не быть, это понятно. ей нужно только обсчитать все варианты и дать ответ в том виде который я указал.

Хитрость реализации в том, что в определённый момент времени всплывает другой снос… я об этом и спрашиваю. Это можно алгоритмизировать?

Мне надо подумать над алгоритмом. Завра напишу как сделать.

осталось/не осталось смягчение - это ведь тоже угадайка, не прада ли?)))

Да кто ж говорит об ошибках?

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

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

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

Весь вопрос в том, как определить наличие/отсутствие фиксажа без значительного падения производительности?

А потеря производительности будет грандиозная. Доказать не могу, но могу показать на пальцах:

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

2. Мало использовать для разных вариантов сноса один кэш. Надо как-то в нем еще разделять варианты "до определения сноса" и "после определения сноса" и еще по вариантам сноса. И еще проводить параллельно анализ: вот так в момент определения сноса результат зафиксирован не зависимо от сноса, а вот здесь различается, в зависимости от сноса.

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

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

Т.е. и сам перебор и работа с кэшем могут очень сильно уронить производительность. И это только для одного расклада вистующих. А их надо перебрать 184756.
      » 14/03/2018, 15:28,  Фрэд 
Pochemuk (13 марта 2018, 13:07)
Минуты и десятки минут? Ну это слишком!
Я несколько лет назад написал на Delphi альфа-бета перебор без кэширования (без запоминания). Так там счет шел на секунды, десятки секунд в худшем случае. И это даже практически без всяких ускорителей для прогнозирования лучшего хода. Единственное что было сделано - вначале рассматривались ходы, форсированно берущие взятку, а потом - отдающие. Даже этого было достаточно, чтобы сократить время перебора раза в 2.

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

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

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

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

Меня на самом деле напрягает другое. Почему изначально у меня считалось всё так медленно. Подозреваю, дело в организации массива данных и способа реализации ходов по правилам игры. У меня фактически 12 динамических одномерных массивов (4 масти х 3 руки), длина каждого из которых варьируется от 0 до 8 и которые складываются в многомерный массив под названием "расклад". Плюс массив из вышедших карт, он нужен для возврата ходов, а последние 1-2 его карты всегда нужны, когда номер хода не кратен 3.

По поводу остального пока ничего конкретного сказать не могу. Но согласен с Вами, что считать задачу "для любого конкретного сноса" мне умозрительно представляется бесперспективным. Насчёт "нечётких" карт интересная мысля. Надо подумать...
      » 15/03/2018, 22:48,  american_boy 
Во-первых, давайте сразу правильно определимся с атмосферой, в которой находимся. Призываю к общению на одном языке. На языке программирования мне не удастся всё растолковать и понять тоже, воспринимайте меня скорее как генерального директора фирмы, племянника руководителя холдинга, состоящей из 80 таких фирм, 25 лет, закончил плехановку, красный диплом, работаю в фирме 3 дня, слова типа "Zobrist-хеш", "транспонирование", "избыточный минимум" услышал от вас впервые на вчерашней планёрке. Кроме того, специально приглашённые мной программисты из других фирм нашего холдинга, (по словам сказанным в кулуарах), также не смогли разобраться в данной терминологии.

Вы - руководитель технического подразделения, академик РАН, теоретик, имеете всяческие регалии, 65 лет, в подчинении у вас талантливые ребята, которых вы сами подобрали, работаете в фирме 20 лет. Т.е. стандартная ситуация.

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

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

Необходимо усовершенствовать существующие проги на работу с двумя вариантами сноса. Т.е создать решатель на 2 сноса.

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

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

Возьмём типичный пример.

Снос А = ТД(х)-(х)
Снос Б = Т(Дх)-х

Решение вижу следующим образом. Программе указываются 2 варианта сноса. Во всех вариантах оптимальной игры при сносе А отмечаются те ходы, где мелькают эти 4 карты (или где они должны промелькнуть). Теперь перед этим ходом, переключается тумблер. Вистующие переключают свою мысль на снос Б, и разыгрывают в уме расклад до конца при сносе Б. При сносе А они тоже естественно знают чем всё должно закончиться т.к. играют оптимально. Теперь сравниваются результаты. Если результат хуже – это ход отмечается негативным, соответственно этот способ розыгрыша несёт опасность. Значит надо выбирать другой! Если результаты при А и Б совпадают - такой ход можно делать безопасно, он не навредит оптимальности.
Таким образом, если в ключевых ходах находится безопасный способ – он и будет лучший при 2-х возможных вариантах сноса.

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

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