[duMka]

Hello!

Хочу написать покеррум. Может кто-то уже чем-то подобным занимался и готов поделится алгоритмами? Прежде всего интересует быстрый алгоритм сравнения комбинаций и надёжный и быстрый алгоритм тасования колоды. Может кто-нибудь идеи какие подкинет?

[Профи]

Сообщение от duMka писал(а) ср, 22 декабря 2004 11:25

Может кто-нибудь идеи какие подкинет?

[Зарегистрироваться?]

[Gump]

Сообщение от duMka писал(а) ср, 22 декабря 2004 11:25

Хочу написать покеррум. Может кто-то уже чем-то подобным занимался и готов поделится алгоритмами? Прежде всего интересует быстрый алгоритм сравнения комбинаций и надёжный и быстрый алгоритм тасования колоды.

Достойное начинание. Вот на твоем руме мы и будем играть приват-турниры .
Не хочу отговаривать конечно, но я думаю ты догадываешься, что раскрутка будет стоить в разы больше, чем стоимость написания, плюс всякие завлекательные программы. А с учетом того, какое кол-во народа охотится за бонусами (особенно в России), вложения не факт, что окупятся. Хотя я готов отказаться от получения у тебя бонуса .
А насчет написания алгоритма: мне интересно, а ты обсчитвывал например до этого казинный покер. Если да, то что, тебе не подходит тот же алгоритм раздачи и сравнения карт игрока с игроками дилера? У меня какие-то софты на Си++ остались.

[duMka]

Hello!

Сообщение от Gump писал(а) ср, 22 декабря 2004 11:55

Достойное начинание. Вот на твоем руме мы и будем играть приват-турниры .
Не хочу отговаривать конечно, но я думаю ты догадываешься, что раскрутка будет стоить в разы больше, чем стоимость написания, плюс всякие завлекательные программы. А с учетом того, какое кол-во народа охотится за бонусами (особенно в России), вложения не факт, что окупятся. Хотя я готов отказаться от получения у тебя бонуса .
А насчет написания алгоритма: мне интересно, а ты обсчитвывал например до этого казинный покер. Если да, то что, тебе не подходит тот же алгоритм раздачи и сравнения карт игрока с игроками дилера? У меня какие-то софты на Си++ остались.

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

Пишу я на Делфи, так что в Си трудновато разобратся, но если есть в программе какие-то оригинальные идеи, то я бы посмотрел, хотя лучше на словах объяснить в чём фишка.

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

[Gump]

Сообщение от duMka писал(а) ср, 22 декабря 2004 12:42

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

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

Сообщение от duMka писал(а) ср, 22 декабря 2004 12:42

Пишу я на Делфи, так что в Си трудновато разобратся, но если есть в программе какие-то оригинальные идеи, то я бы посмотрел, хотя лучше на словах объяснить в чём фишка.

Ну здесь я боюсь претендовать на оригинальность-я писал простенькие пргорамки, мне был важен лишь рез-т. Карты, например у меня все равнялись числам от 1 до 52, с 1 до 13 одна масть и т.д., номинал карты равнялся остатку от деления на 13, соотв при равенстве остатка двух карт-пара, три остатка равны - тройня. Над оптимизацией для ускорения я особо не парился.

[Профи]

Сообщение от duMka писал(а) ср, 22 декабря 2004 12:42

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

А видел ли ты "лягушатник", написанный авторами Poki?
[Зарегистрироваться?]
Сейчас авторы ботов ходят тестироваться именно к ним.

[duMka]

Hello!

Сообщение от Gump писал(а) ср, 22 декабря 2004 12:59

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

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

Учится можно ведь и на плохих примерах типа "так не делай". Пусть для начала все боты одинаково играют все руки. Через некоторое время обучаемый бот начнёт исключать некоторые руки.... соответственно будет переигрывать необучаемых. Однако если они все будут обучаемы и исключать неперспективные комбинации, то ситуация изменится, правила нужно будет снова пересматривать и.т.д. После множества итераций мы найдём золотую средину.... Лучше конечно если эти боты будут по разному играть и по разному обучатся. Думаю когда напишу покеррум, то приглашу желающих потестировать своих ботов.

[Sfanrod]

Я для тасовки колоды применял след-й алгоритм:
1. Раскидываем в цикле все карты (индексы от 1 до 52) в массиве например A(0..1000)
случайным образом:
i := random(1001);
при попадании на уже устан-е число повторяем опер-ю выбора.
2. Проходим последовательно по массиву A и собираем в массив B(колода) перетасованные карты.

Интересно, а что ты на вход нейросети подавать собираешся, параметров слишком много?

[yras]

самы простой алгоритм тасовки одной колоды:
for (i=1;i<=52;i++) {a[i]=i;};
for (i=52;i>1;i--)
{
k=random(i)+1;
tmp=a[k];
a[k]=a[i];
a[i]=tmp;
}

[duMka]

Hello!

Сообщение от Sfanrod писал(а) ср, 22 декабря 2004 15:15

Я для тасовки колоды применял след-й алгоритм:
1. Раскидываем в цикле все карты (индексы от 1 до 52) в массиве например A(0..1000)
случайным образом:
i := random(1001);
при попадании на уже устан-е число повторяем опер-ю выбора.
2. Проходим последовательно по массиву A и собираем в массив B(колода) перетасованные карты.

Больше всего меня смущает оператор random. Насколько он рандомный? Кто его знает... что-то не совсем я ему доверяю. Если с помощью него перетасовать колоду, то насколько случайный будет результат? Если её перетасовать два раза, то результат улучшится?
Если тасовать каждый раз "новую" колоду то будет хуже или лучше если брать перетасованную с прошлого раза?
Ну и по поводу собственно алгоритма: Скажем последним в колоде у нас будет туз, тогда в "среднем он должен попасть в средину колоды, но так как основная часть колоды (51 карта) у нас уже распределена по массиву, и распределена по своим случайным местам - т.е. может быть так что большая часть колоды в массиве ниже индекса 500, то в этом случае туз попадает "в среднем" ближе к концу колоды. Иными словами позиция туза в колоде определяется не только его случайным числом, но и в некоторой степени теми числами что выпали раньше. (В общем туз в хорошей, последней позиции, когда все карты уже распределены ) Не будет ли в таком случае некоторой корреляции в положении карт в перетасованной колоде в зависимости от начального положения?
Это и к алгоритму Yras кстати тоже относится. ИМХО по его алгоритму у самой первой карты в колоде вероятность быть перемещёной несколько раз выще, чем у последней.

!

Сообщение от Sfanrod писал(а) ср, 22 декабря 2004 15:15

Интересно, а что ты на вход нейросети подавать собираешся, параметров слишком много?

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

[Appl]

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


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

[pokerchatko]

Сообщение от duMka писал(а) чт, 23 декабря 2004 11:04

Это и к алгоритму Yras кстати тоже относится. ИМХО по его алгоритму у самой первой карты в колоде вероятность быть перемещёной несколько раз выще, чем у последней.

Ты просто случайным образом тянешь по одной карте из колоды. И если выбор действительно случаен, то какая разница, как при этом перемещаются карты собствнно в остатке колоды?

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

[korovin]

ну не знаю, если не можеш написать простую фкнкцию анализа руки из 5-6-7 карт, на выходе номер комбинации, то о каких нейросетях может идти речь?

[aprisobal]

Сообщение от Korovin писал(а) чт, 23 декабря 2004 20:19

ну не знаю, если не можеш написать простую фкнкцию анализа руки из 5-6-7 карт, на выходе номер комбинации, то о каких нейросетях может идти речь?

имхо. В точку! =)

Сообщение от duMka писал(а)

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

Данная проблема будоражит ум еще со времен Чапека, впервые употребившего термин "робот" ещё рассказы Азимова, свежее - Терминаторы.
Современные НС базируются на очень упрощенной модели, игнорирующей большинство знаний о детальном функционировании мозга. Возможно, для описания систем, имеющих сложность головного мозга, необходимы совершенно новые математические методы. Пока подходов нет, но есть выход!: последовать примеру американских ученых: [Зарегистрироваться?] и культивировать пару тысяч (там 25 000) нейронов домашнего питомца(там крысы) в питательной среде и натренировать играть в покер (там управлять симулятором F22), отталкиваясь (грубо) от того, что управлять F22 так же непросто как играть в покер

[duMka]

Hello!

Сообщение от aprisobal писал(а) пт, 24 декабря 2004 01:44

имхо. В точку! =)

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

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

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

!

Сообщение от aprisobal писал(а) пт, 24 декабря 2004 01:44

[
Данная проблема будоражит ум еще со времен Чапека, впервые употребившего термин "робот" ещё рассказы Азимова, свежее - Терминаторы.
Современные НС базируются на очень упрощенной модели, игнорирующей большинство знаний о детальном функционировании мозга. Возможно, для описания систем, имеющих сложность головного мозга, необходимы совершенно новые математические методы. Пока подходов нет, но есть выход!: последовать примеру американских ученых: [Зарегистрироваться?] и культивировать пару тысяч (там 25 000) нейронов домашнего питомца(там крысы) в питательной среде и натренировать играть в покер (там управлять симулятором F22), отталкиваясь (грубо) от того, что управлять F22 так же непросто как играть в покер

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

[denker]

Я думаю в посте Korovin'а ключевое слово всё же "номер"
Учитывая вышесказанное и используя, т.н. "кеширование" функция действительно будет простой и быстрой 8-)

[duMka]

Hello!

Сообщение от denker писал(а) пт, 24 декабря 2004 13:14

Я думаю в посте Korovin'а ключевое слово всё же "номер"
Учитывая вышесказанное и используя, т.н. "кеширование" функция действительно будет простой и быстрой 8-)

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

[pokerchatko]

Сообщение от duMka:

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

Устраивает тебя random или нет, решать тебе самому. Как по мне, так наоборот - для моделирования подойдет, для игры - неприемлемо.

Понятно, что всевозможных выриантов тасованияч колоды - 52!
С другой стороны, последовательность случайных чисел у встроенной функции random определяется начальным значением ( обычно какая-то функция, зависящая от времени), а это 4 байта. Т.е. вариантов всего 2**32, и это микроскопическая доля от того, что могло бы быть( в 1,88e58 раз, это примерно 47!).
И получается хитрая ситуация. Зная 2 своих карты + 3 карты флопа ( а в стад-покере мы вообще видим куда больше), мы с определенной вероятностью можем "увидеть" карты соперников, поскольку, скорее всего, лишь одна подобная комбинация представлена в подмножестве 2**32 ( т.е. одна из 47!) Оставалось только сидеть и запоминать

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

[Gump]

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

[Профи]

Начни считать, как часто это происходит. Я думаю получится, что не так уж часто, просто запоминается лучше.