[Sharky]

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

Если у кого-то подсчеты не верны:
1. Ошибка в программе -- бывает к сожалению.
2. Ошибка в формуле -- учить матчасть.
3. Упрощение формул -- на свой страх и риск.

[xRaven]

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

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

[korovin]

Сообщение от Цитата:

Ты не видишь в этом главную проблему? Ее можно решить задав вопрос разработчику.

Блитц, я хоть и не одобряю манеры Грея вести дискусии, но здесь не могу с ним не согласится: Если твоя программа гоорит что МО обмена 0.1111 а фактически оно 0.1234, то ты не прав. Напиши гденибудь в опмсании что МО обмена счмтается с погрешностью 0.02 (цифры условные) и все! Ничего не имею против твоей программы, наоборот всем рекомендую, кто спрашивает, но эта тема "Почему у всех разные цифры" уже поднадоела. Насчет молока, есть же госты где написано допустимое октлонение жирности. Под "как считают" я имел ввиду "точно или приближенно".

По теме ветки. Почему бы не сделать на форуме сервис: вводиш карты, получаеш МО решения, ТОЧНОЕ. Можно и отдельным проектом, нет желающих?

[Grey]

Сообщение от Korovin писал

я хоть и не одобряю манеры Грея вести дискусии

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

[Grey]

Сообщение от Sharky писал

Вообще не понимаю, о чем тут спорите
1. Брутофорс -- это комбинаторика, перебор, другое название пермутации.

Sharky, ты не прав.
[Зарегистрироваться?]

[Blitz]

Сообщение от Korovin писал вс, 24 сентября 2006 06:21

Если твоя программа гоорит что МО обмена 0.1111 а фактически оно 0.1234, то ты не прав.

Не прав в чем? Допустим нужно определить попадание значений некоторой функции в интервалы 0-10,10-20,20-30 и т.д. Есть алгоритм, который считает значения этой функции с точностью, скажем, до десятых долей. На мой взгляд, этой точности вполне достаточно, чтобы принять правильное решение. Да, бывают изредка попадания на границы диапазонов, которые могут привести к незначительной погрешности, но в общей массе ее не видно. Такая концепция. Но находятся умники, которые громко заявляют, что "алгоритм-то точностью ОСОБОЙ не блещет" ибо считать надо до 20го знака после запятой с абсолютной точностью. Ну объясните мне, для чего? Чтобы потешить свое самолюбие или что? При этом, заметьте, самые активные борцы за "точность" как правило не являются пользователями какого-либо софта, который они походя критикуют.

Почему вы все грубо игнорируете мой аргумент об округлениях в "бумажных" стратегиях? Кто-нибудь спрашивал, по какой методике авторы их "округляют"? Между тем, это имеет реальное и ощущаемое в деньгах влияние на доходность, в отличие от цифры на экране. Если угодно, ее вообще можно не показывать, а только выдавать правильное решение. Я говорю конкретно о своем софте. Если софт выдает значение +1.5 вместо реального +1.1 (к примеру), но при этом это алгоритм позволяет получить ВЕРНОЕ игровое решение, то цифра на экране не влияет абсолютно ни на что! В жизни ты сыграешь правильно и полчишь те деньги, которые должен. С абсолютной точностью.

Блиц.

[korovin]

Сообщение от Цитата:

Да, бывают изредка попадания на границы диапазонов, которые могут привести к незначительной погрешности, но в общей массе ее не видно. Такая концепция. Но находятся умники, которые громко заявляют, что "алгоритм-то точностью ОСОБОЙ не блещет" ибо считать надо до 20го знака после запятой с абсолютной точностью. Ну объясните мне, для чего? Чтобы потешить свое самолюбие или что? При этом, заметьте, самые активные борцы за "точность" как правило не являются пользователями какого-либо софта, который они походя критикуют.

Blitz, Пользователем не яляюсь. Не критикую, а пытаюсь отетить на вопросы "почему так". Кстати, ты так и не отметился в теме про покупку к тройнику. http://forum.cgm.ru/msg?th=7394&start=0

[Sharky]

Сообщение от Grey писал вс, 24 сентября 2006 10:34

Sharky, ты не прав.
[Зарегистрироваться?]

Ну так писал обобщенно.. что брутофорс основан на комбинаторике, а так вообще это способ атаки. Поэтому в покере лучше применять термин перебор или пермутации..

И на ссылке что ты дал, так и написано:

brute-force search is a trivial but very general problem-solving technique, that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

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

[Grey]

Сообщение от Blitz писал

Но находятся умники, которые громко заявляют, что "алгоритм-то точностью ОСОБОЙ не блещет" ибо считать надо до 20го знака после запятой с абсолютной точностью. Ну объясните мне, для чего? Чтобы потешить свое самолюбие или что? При этом, заметьте, самые активные борцы за "точность" как правило не являются пользователями какого-либо софта, который они походя критикуют.

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

[Grey]

Сообщение от Sharky писал

Ну так писал обобщенно.. что брутофорс основан на комбинаторике, а так вообще это способ атаки. Поэтому в покере лучше применять термин перебор или пермутации..

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

[Это Я]

Сообщение от xRaven писал вс, 24 сентября 2006 00:28

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

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

Это (вложенные циклы до 4 порядка) точно работает быстрее обычного перебора с готовым массивом сил? Там достаточно прогнать 13^4+13^4 раз очень короткий участок кода на все комбинации диллера.

[korovin]

Сообщение от Цитата:

Можно считать абсолютно точно без потери скорости, а то и быстрее.

Можно если нужно. А если не нужно то и незачем. Не вижу никаких противоречий. Кстати, вот идея негрубого перебора: Перебираем карты дилера циклами не в 52 карты, а в 13 номиналов. Скорость реально выше а точность не страдает. Допустим что я вижу как повысить скорость моих расчетов вдвое, но не далаю - стимула нет. Разве это меня как-то дискридитирует? ИМХО каждый делает как считает нужным и не обязан никому ничего доказывать.

[Gramazeka]

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

[KID]

Немножко не понимаю, что вы имеете ввиду под перебором. Предположим, я считаю обмен одной карты, цикл из 46 прогонов(количество оставшихся карт) это перебор? Или имеется ввиду общет только одной конкретной руки.
Немножко оффтопа: вчера измерил скорость обсчета руки, получилось около 2,5 секунд на миллион. Это на атлоне 3000+(2000Мг).Это мало, много или нормально? Причем определение силы отдельной комбинации из пяти карт, это отдельная функция, возможности оперативной памяти не позволяют загружать массив из файла.
Да, и про точность вычислений: я стараюсь добиться абсолютности. Уже год как не играю серьезно и программа для меня стала очень важна чисто теоретически, смогу или не смогу. Навящивая идея так сказать. А играть я научился на демке Блица, спасибо ему большое, для практического применения его прога подходит весьма неплохо.

[xRaven]

Сообщение от Это Я писал вс, 24 сентября 2006 13:54

Это (вложенные циклы до 4 порядка) точно работает быстрее обычного перебора с готовым массивом сил? Там достаточно прогнать 13^4+13^4 раз очень короткий участок кода на все комбинации диллера.

13^4+13^4 не совсем понял что значит. Упрощенный перебор комбинаций дилера?
я сравнивал по скорости перебор 52^4 дилеру с массивом сил, далее сравнение с силой игрока.... Соответсвенно получал абс. точное мо.
И использовал комбинаторный метод,в нем участвовала часть кода что я выложил и определение количества нет игры у дилера. Дальше думаю понятно как мо получалось.
Разница по скорости была на порядок(несколько сот раз). Специально не просчитывал сколько занимает в секунду обработка одной руки,т.к. не доводил оптимизацию по полной. Если даже используется сокращенный вариант перебора карт дилера(без мастей, только ранг), все равно комбинаторика быстрей мне кажется будет.

[Sharky]

Может начнем потихоньку вносить ясность?

Что такое перебор карт в контексте покера? В данном случае перебором считается генерация к-элементного подмножества из n-множества. Будем говорить о колоде из 52 карт состоящей из 13 рангов по 4 масти, тогда n-множества это есть наша колода карт, а k-элементное подмножество -- количество карт необходимое для выборки. Используя формулу комбинаторики C(n,k) можно посчитать общее количество таких выборок с сохранением одинаковой вероятности для каждой возможной выборки (каждая выборка появится ровно 1 раз). Символом (n,k) называют биноминальным коэффициентом. Например, сделаем выборку по 5 карт из полной колоды. Подставим числа в формулу, получим C(52,5) = 52!/5!(52-5)! Не будем сами расписывать формулу и возьмем Excel, функция "ЧИСЛКОМБ". Получим число 2598960.

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

Разобьем наше множества (колоду карт) на ранги и масти получим 13 рангов и 4 масти. Берем любую одну масть, это C(4,1) и умножим на выборку 5 нужных старших карт, это C(5,5) поделим на общие число комбинаций и найдем вероятность всех рояля.
P = C(4,1) * C(5,5) / C(52,5) = 4 / 2598960 = 1/649740

Аналогично можно просчитать все другие комбинации не используя перебор. Для каждой комбинации своя функция.

P.S. Сейчас еще про обмены накатаю..

[Gramazeka]

Вчера гонял прогу Миалана и Блица- получил в одной раздаче большое отличие МО в этих прогах.
Имеем-
У диллера 9 :d:
У игрока В :d: В :c: В :s: 8 :s: 7 :s:
Соседние боксы- К :s: 6 :s: 7 :d: 7 :c: 6 :c: и
5 :d: 6 :d: Д :c: 2 :d: 3 :h:
МО у Блица- Рэйс- 4.0445 Обмен одной- 4.1533 Обмен пяти- -1.0919
У Миалана соответственно- 4.4522 4.4863 -1.0617
Почему такие разбросы результатов?Где правильно?

[Mariner]

Приветствую!

2 Gramazeka

В последней демке Блитца выплаты за комбинации не стандарные.
Это было учтено при сравнении?

[Gramazeka]

А как это учитывать?И там же вроде косяк начинается от стрита?Или я не прав в чем то...

[Sharky]

Итак, в качестве примера стандартный Оазис с 1 обменом на 1 боксе. Требуется найти оптимальное решение Bet, Fold, Draw.

Имеем известных карт: 5 на руке и 1 у дилера. 46 неизвестных в колоде. Опять используем принцип комбинаторики и рассчитаем общее число требуемых решений. Так как можно менять любую карту из 5, мы оставляем себе только 4 карты, это значит выборка 4 из 5 и записываем как C(5,4) = 5. Далее можем получить любую из неизвестных 46 карт, это C(46,1) = 46. Далее для оценки понадобится сравнить силу нашей комбинации с комбинацией дилера, которая не известна. Посчитаем и ее используя все вероятности на оставшихся картах. Для этого сделаем выборку 4 недостающих карт из оставшихся 45 (одну мы взяли себе). Получим C(1,1) * C(45,4) = 148995. Далее вычисляем предпочтительное действие Bet или Fold для каждой конечной выборки. Прибавляем оплату или вычитаем потерю находим EV (ценность) данного действия.

Теперь посчитаем сколько требуется просчитать вариантов решений для обмена карт: C(5,4) * C(46,1) * C(1,1) * C(45,4) = 5 * 46 * 1 * 148995 = 34,268,850 решений. Прибавим оценку принятия решения без обмена C(46,4) = 163185. Сложим все вместе и получим: 34,432,035 вариантов требующих вычислений для полной так сказать картины.

Уверен, все согласятся, что вычисления полными переборами с генерацией подмножеств займет много времени. Но вычисления при этом абсолютно верные. Встает задача сократить время перебора, и вот тут уже каждый использует свои трюки и хитрости. У одних теряется точность у других нет и т.п. Поэтому на вопрос почему прога X показывает резултат отличный от проги Y нужно задавать производителям этих прог... Не знаю, кто что использует в оптимизации, поэтому дальше пишу только про свое ПО. Я использую формулы для подсчета вероятностей руки дилера. Таким образом, что обмена 1 карты занимает теперь C(5,4) * C(46,1) = 230 решений. Результат вычислений при этом остается абсолютно точным! Это основная причина, по которой пошел именно по этому пути оптимизации. Минус: сложные формулы и требующие длительной проверки. Но это не единственная оптимизация всего процесса. Очень много хитростей используется для достижения минимального времени расчета. Но о них уже писать не буду. Скажу только, что любая оптимизация не влияет на точность, и это считаю правильным. И между тем постоянно возникают еще идеи, как еще больше сократить время расчетов. Для меня это является чем-то вроде хобби, пока не начал поставки своего ПО в коммерческих целях. Цель -- самый быстрый и точный анализ плюс огромное количество правил. 8-)