|
Базар вокруг игры / Комп в помощь / Скорость и точность вычислений (покер)
|
|
Sharky
Скорость и точность вычислений (покер) [ID=24204]
Вт, 14 марта 2006 23:39 [#]
|
Вопрос скорее к программистам..
1. Сколько нужно пермутаций, что бы сосчитать МО руки, для обмена 1-, 2-, 3-, 4- и 5-ти карт.. (только один обмен на одном боксе).
2. Сколько требуется на это время?
3. Какая точность при этом?
Если потраченное время зависит в основном от скорости процессора, то 1 и 3 вопрос актуальны..
Я получил следующий результат:
1.
52 – (5 +1) = 46 // неоткрытое число карт
C{4,46} = 163 185 // требуется на просчет всех комбинаций дилера
C{1,5} * C{1,46} * C{4,45} = 5 * 46 * 148 995 = 34 268 850 // обмен 1 карты + оценка руки дилера
C{2,5} * С{2,46} * C{4,44} = 10 * 1 035 * 135 751 = 1 405 022 850 // обмен 2 карт + оценка руки дилера
C{3,5} * С{3,46} * C{4,43} = 10 * 15 180 * 12 341 = 1 873 363 800 // обмен 3 карт + оценка руки дилера
С{4,5} * C{4,46} * C{4,42} = 5 * 163 185 * 111 930 = 91 326 485 250 // обмен 4 карт + оценка руки дилера
С{5,5} * C{5,46} * C{4,41} = 1 * 1 370 754 * 101 270 = 138 816 257 580 // обмен 5 карт + оценка руки дилера
Итого все слаживаем вместе:
163 185 +
34 268 850 +
1 405 022 850 +
1 873 363 800 +
91 326 485 250 +
138 816 257 580 = 233 455 561 515!!!
2. Скорость просчета всех событий (по условию) не превышает 40 секунд на AMD Athlon XP 2000+. Что говорит о 233 455 561 515 / 40 =~ 5 836 389 038 пермутаций в секунду.
3. Точность вычислений абсолютная*.
Может, кто сможет чтонить сказать. Может у меня крышу снесло или перепил...
* -- Абсолютная на столько, на сколько позволяет 8-байтовая мантисса в диапазоне 5.0*10^–324..1.7*10^308. Не исключаю вероятность ошибки, но если таковая имеется – это будет не логическая а синтаксическая, не влияющая на скорость вычислений...
И вот еще что, теоретически скорость можно оптимизировать в 1.5 (2.0) раза, но это максимум имхо, без потери точности..
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24205] [ответ на 24204 ()]
Ср, 15 марта 2006 00:52 [#]
|
|
5 миллиардов в секунду, это полтакта процессора на анализ? За эти полтакта нужно получить тип руки игрока и дилера, сравнить их, изменить значения счетчиков ну и сами команды циклов нужны. Не верится что-то.
|
|
|
Sharky
Re: Скорость и точность вычислений [ID=24206] [ответ на 24204 ()]
Ср, 15 марта 2006 01:21 [#]
|
Эээ.. Ну на сколько я помню, 1 такт процессора позволяет выполнять <= 6 микроопераций, причем оптимально будет схема 4+1+1 (4-микроопераций на сложный декодер и по 1 микрооперации на 2 простых декодера)... Количество тактов в единицу времени зависит от его частоты, ну и +/- всякие дополнительные конвейеры и предсказатели... Ну это к слову о полтакте процессора 
Ну и плюс, я уже говорил, что использую комбинаторику + теорию вероятности, за счет этого и скорость. Причем скорость еще можно увеличить в раза 2.
|
|
|
Фартовый
Re: Скорость и точность вычислений [ID=24207] [ответ на 24204 ()]
Ср, 15 марта 2006 07:16 [#]
|
|
Хотел спросить тех кто пишет софт сам - перебор всех возможных комбинаций осущесвляеться циклом по всем мастям, рангам и.т.д.? Т.е. к примеру чтобы оценить какова вероятность определенной пары у дилера при заданной КД - нужно в проге перебрать все его варианты?
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24208] [ответ на 24204 ()]
Ср, 15 марта 2006 07:24 [#]
|
|
Т.е ты считаеш с такой точностью, но без переборов всех этих циклов напрямую? Я решаю ту-же задачу за пару секунд, если точно и за доли секунды с достаточным для меня приближением.
|
|
|
Фартовый
Re: Скорость и точность вычислений [ID=24209] [ответ на 24204 ()]
Ср, 15 марта 2006 11:25 [#]
|
| Korovin писал ср, 15 марта 2006 07:24 | | Т.е ты считаеш с такой точностью, но без переборов всех этих циклов напрямую? Я решаю ту-же задачу за пару секунд, если точно и за доли секунды с достаточным для меня приближением. |
Наверное с ипользованием формул комбинаторики? Пренебрегая тем что частьь карт уже вышло
|
|
|
Sharky
Re: Скорость и точность вычислений [ID=24210] [ответ на 24204 ()]
Ср, 15 марта 2006 15:05 [#]
|
|
Перебор есть. И формулы тоже. Так какая скорость у вас для обмена 5 карт и погрешность на точность?
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24211] [ответ на 24204 ()]
Ср, 15 марта 2006 16:22 [#]
|
|
Я считаю так: варианты карт игрока полным переборои без потери точности либо по упрощенноиу алгоритму сжатия мастей (полный так и не сделал). Для каждого варианта руки игрока точно считается число игр дилера выше/ниже/равно по формулам комбинаторики. Скорость расчетов миллион рук игрока в секунду. Для вашего примера нужно просчитать 1 500 000 рук игрока, на что требуется 1.5 сек. Результат будет АБСОЛЮТНО точным.
|
|
|
Sharky
Re: Скорость и точность вычислений [ID=24212] [ответ на 24204 ()]
Ср, 15 марта 2006 17:07 [#]
|
|
Ага, пнятно. А проц какой? И не мешало бы какнить точность сверить..
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24213] [ответ на 24204 ()]
Ср, 15 марта 2006 20:56 [#]
|
|
Проц пень 3.2 Сверяли уже, поищи на форуме. Это_Я в ноябре тему поднимал и по скорости и по точности.
|
|
|
Sharky
Re: Скорость и точность вычислений [ID=24214] [ответ на 24204 ()]
Чт, 16 марта 2006 11:17 [#]
|
|
Вах. это я забыл дебаг-функции выключить.. Теперь для всех переборов (1--5) карт время ~ 9 сек. После оптимизации думаю выйду на 3-4 сек. И если вычисления раскинуть по thread'ам то возможно приближу к 0,3-0,4с.. Нормально, как считаешь?
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24215] [ответ на 24204 ()]
Чт, 16 марта 2006 11:47 [#]
|
|
Нормально для чего? Главное чтобы тебя устраивало, остальным помоему это фиолетого.
|
|
|
Sharky
Re: Скорость и точность вычислений [ID=24216] [ответ на 24204 ()]
Чт, 16 марта 2006 12:17 [#]
|
|
Не только для себя любимого делаю... Уже скоро демка созреет.
|
|
|
Anucint
Re: Скорость и точность вычислений [ID=24224] [ответ на 24204 ()]
Сб, 15 апреля 2006 14:24 [#]
|
А подскажите , если не трудно, сколько комбинаций должно получиться для набора из 5 карт ?
вот тут: http://www.gamblecraft.com/ru/review...pok/basics.htm называют 134 459 комбинаций. У меня по расчётам получается аж 1 132 235. Это на сайте ошибка или у меня алгоритм неправильный ?
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24225] [ответ на 24204 ()]
Сб, 15 апреля 2006 14:53 [#]
|
| Цитата: | | А подскажите , если не трудно, сколько комбинаций должно получиться для набора из 5 карт ? |
Смотря из скольки возможных. Для 52-х карт 52*51*50*49*48/5/4/3/2/1= 2 598 960
|
|
|
Anucint
Re: Скорость и точность вычислений [ID=24226] [ответ на 24204 ()]
Сб, 15 апреля 2006 15:12 [#]
|
вот цитата с сайта , ссылку на который я дал выше :
"Сколько же всего комбинаций может выпасть при игре? При игре без джокера первая карта выбирается из 52 карт, вторая - из 51, третья - из 50 и так далее. Таким образом, всего получается 52*51*50*49*48 = 311 875 200 вариантов! Однако, если учесть, что порядок появления карт не имеет значения (то есть 10,J,Q,K,A тоже самое что и A,K,Q,J,10), то эту цифру можно уменьшить в 120 раз - получаем 2 598 960 комбинаций. Также нам не важен порядок появления мастей: 2,3,8,A,10 червей и 2,3,8,A,10 треф абсолютно аналогичные комбинации с точки зрения стратегии. <font color="red"> Это условие позволяет уменьшить количество комбинаций до 134 459.</font> "
вот я убирая одинаковые с точки зрения стратегии комбинации получил вместо 2 598 960 комбинаций - 1 132 235, как ещё можно сократить кол-во комбинаций до 134 459 я не могу сообразить
|
|
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24228] [ответ на 24204 ()]
Сб, 15 апреля 2006 17:57 [#]
|
|
Это называется сжатием мастей. Я например для расчета МО покера упростилвсе до 7 462 вариантов.
|
|
|
Anucint
Re: Скорость и точность вычислений [ID=24229] [ответ на 24204 ()]
Сб, 15 апреля 2006 20:26 [#]
|
|
7 462 варианта, это я так понимаю, не только за счёт мастей, но и за счёт отбрасывания мусорных комбинацмй. А сколько реально остаётся после сжатия мастей?
|
|
|
korovin
Re: Скорость и точность вычислений [ID=24230] [ответ на 24204 ()]
Сб, 15 апреля 2006 21:01 [#]
|
|
Посчитай отдельно каре, фулы, тройки, 2 пары, пары и беспарки (разномастные и одномастные).
|
|
|
