[Grey]

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

Мде, отстал я от жизни.. И все-таки Grey, как ты считаешь? Если 143K заготовок, то это одно, и сравнивать тесты так как мы имхо нельзя, или все пересчитываешь?

Не совсем понял про 143K, но считаю все честно

[Шамсутдинов]

Сообщение от Sharky

2 Шамсутдинов: Абсолютно точную покупку игры уже я делал, и алгоритм был описан на страницах форума + демка была..

У вас 888 постов. Поиск займет время. Хотя много интересного.

[korovin]

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

Я получаю количества всех комбинаций у дилера (AK, 2, 2+2, 3, S, F, 3+2, 4, FS, FR). Получаю количество пустых комбинаций у дилера вычитанием из его общего количества этих. Если у игрока не пустая комбинация, то производится подсчет таких же по достоинству комбинаций у дилера, равных или больших по сравнению всех карт - это наибольшее сложная и большая часть кода по количеству строк.

Так ли делаетcя в вариантах, лучших чем мой? Например, ищется ли количество всех стритов и флеш-стритов по отдельности у делера, если у игрока пара? Или, если у игрока нет игры, может быть сразу ищется в скольких случаях у дилера она есть, то есть хотя бы 2 одного достоинства, флеш или стрит (придется еще искать количество FS).

Если у игрока пустая, мне достаточно знать число пустых рук дилера. Если ТК - пустых и ТК младше/равно, ... Так как подавляющее большинство анализаируемых рук пустые, ТК и пары, экономия в объеме вычислений значаительная. По покупке игря Sharky получил очень интересные результаты, ищите.

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

И еще, не совсем понятно как Вы успеваете анализировать все варианты обменов (Русский покер) без упрощений, ведь один только пятак на первом боксе требует анализа 1370754 вариантов (3 секунды при вашей скорости).

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

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

[Шамсутдинов]

Сообщение от Korovin

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

Так я тоже упростил, но несущественно, см. pkr.doc:
Допущения при покупке игры.
1) Если у дилера после покупки (или после повторной покупки) выпал F и у игрока тоже F, то считается, что карта дилера больше, игнорируя старшинство F.
2) Если у дилера после покупки (или после повторной покупки) выпал FS или FR, то считается, что у него S того же старшинства.
Старшинство S учитывается, в том числе возможность stay.

Но отклоненния небольшие, тем более в очень редко встречающихся случаях. В остальном все точно.

Сейчас пишу быстродействующую версию основного алгоритма и тестовую программы, такой же, как у всех. Уже написал 336 строк - подсчет количества "есть игра" у дилера и общепринятый тест. Не успел еще заполнить массив комбинаций у игрока. Пока массивы в сумме занимают 1МБ.

[Шамсутдинов]

Сообщение от Sharky писал ср, 14 марта 2007 16:50

2 Шамсутдинов: Абсолютно точную покупку игры уже я делал, и алгоритм был описан на страницах форума + демка была..

Здесь?
http://forum.cgm.ru/msg?th=8273&prevloaded=1&st= art=160

Интересна с какой скоростью она считалась. Пока не вникал.

Сделал в основном алгоритме расчет количества у дилера "есть игра". Получилось в тесте в 3 раза быстрее, чем у Грея. Так что расчет, когда у игрока пара, можно сделать в 5 раз медленнее для получения такого же результата, как у Грея.

[korovin]

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

Сделал в основном алгоритме расчет количества у дилера "есть игра".

Мне кажется что посчитать число беспарок и отнять число стритов/флешей проще чем считать число "есть игра".

[Grey]

Сообщение от Шамсутдинов писал

Сделал в основном алгоритме расчет количества у дилера "есть игра". Получилось в тесте в 3 раза быстрее, чем у Грея. Так что расчет, когда у игрока пара, можно сделать в 5 раз медленнее для получения такого же результата, как у Грея.

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

[Шамсутдинов]

Сообщение от Korovin писал пт, 16 марта 2007 16:09

Мне кажется что посчитать число беспарок и отнять число стритов/флешей проще чем считать число "есть игра".

Количество, когда есть хотя бы две одного ранга, не считается, а берется, зная количество раных количеств от 0 до 3 (для 4 следует из для 0,1,2,3) свободных карт по рангам. Причем, делаем не многомерный массив [13][13][13][13], а одномерный [13^4] для получения индекса [1820=C(16,4)] для доступа в другие массивы. Тем более, что этот индекc [13^4] легко модифицировать, например, для исключении ранга, например при расчете количества комбинаций туз-король после "парок". При получение "парок" второй индекс массива - количество свободных карт, того же ранга, что и КД (карта дилера).
Количество "есть игра" я считаю, как количество парок + количество туз-король, включая стриты и флеши с тузом и королем + количество стритов, исключая тузовых + количество флешей - количество FS и FR. По-моему, быстрее посчитать уже невозможно.

Сообщение от Grey

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

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

[Grey]

Сообщение от Шамсутдинов писал

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

Какой может быть массив? При произвольном количестве и составе "мертвых" карт??? Для полной колоды, я понимаю, можно сделать.

[Шамсутдинов]

Сообщение от Grey писал пт, 16 марта 2007 18:41

Какой может быть массив? При произвольном количестве и составе "мертвых" карт??? Для полной колоды, я понимаю, можно сделать.

Как же вы достигли такого быстродействия, если не использовали эту идею?
1. Считаем количества свободных карт по рангам - это числа 0..4.
2. Считаем количества среди этих чисел, не включая ранга карты дилера отдельно 0, отдельно 1, 2 и 3 (остальные - 4). Пусть эти количества -r0,r1,r2,r3. r0+r1+r2+r3<=12 (нет ранга карты дилера). Таких наборов (r0,r1,r2,r3) всего С(12+4,4)=1820.
3. Делаем массив перехода от числа 0..13^4-1 к числу 0..1820-1. Кстати, можно не хранить r0,r1,r2,r3, а сразу вычислять r0+r1*13+r2*13^2+r3*13^3, все время добавляя 13^s. Но в моем новом коде этого пока нет. Такая же сумма, но не по всем рангам, а только до третьей карты в паре понадобится при подсчете количества меньших пар у дилера (я сейчас этим занимаюсь).
4. Для каждого набора (r0,r1,r2,r3) однозначно определно количество комбинаций 2, 2+2, 3, 3+2, 4, а также их общее количество ("парок"). Получаем для каждого числа 0..1820-1 массив структур, составленных из этих чисел. Кроме того, при получении количества пар у дилера, младших пары игрока по старшинству пары, потребуется массив [1820][5], где второй индекс указывает на количество свободных карт в ранге, для которого узнается количество пар этого ранга у дилера. Первый индекс - тот же, что и исходный (для определения "парок").

Для оптимизации я все циклы развернул в полный код без циклов. Для флешей сделал массив [13][2^12], где первый индекс - ранг карты дилера (КД), а второй - занятость карт масти открытой КД, исключая ранга КД в двоичной системе счисления.

Компилятор Microsoft Visual Studio (MVS) может оказаться быстрее компилятора Builder6, который я использую, поэтому можно будет вычислительную часть теста сделать как dll на MVS. Также можно будет в основной моей программе импортировать функцию подсчета комбинаций у дилера. Таким образом, можно будет разным оболочкам присоединять вычислительный модуль как dll. Что можно использовать для отладки, сравнения результатов и т.п.

[Шамсутдинов]

Написал и отладил код основной процедуры для случая "нет игры" и "пара" (подсчет младших и равных пар). Если в случаях, когда не "пара" считать как нет игры, а когда "пара" считать полностью, то мой тест дает время лучше, чем у Грея в 3,03 раза.
Доля пар к общему количеству комбинаций: 0,4226.
Время подсчета "нет игры" без оболочки теста / время оболочки теста = 2,02.
Чистое время подсчета старшинства пары / подсчет "нет игры" = 0,57 (исключается время оболочки теста).

[Sharky]

Как я понимаю, у нас новый лидер... 8-)
Моя последняя демка обгоняет более чем на 2 сек. с полной колодой демку Грея (на моем железе). Чем больше карт выкинуть, тем быстрее обгоняет (странно)..

[Sharky]

Файл обновил, в старом млин деление на нуль c неполной колодой было Извиняюсь, не проверил как следует...

[korovin]

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

[Grey]

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

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

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

[ёжик]

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

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

За клубный взялся?!

[Fabrica]

В клубном уже почти все есть.

[Gramazeka]

Сообщение от ёжик писал сб, 24 марта 2007 12:04

За клубный взялся?!

А он с Маринером списался

[Sharky]

Сообщение от Korovin писал сб, 24 марта 2007 03:01

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

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

[Sharky]

Насчет обменов: нашими тестами не получится, имхо. Неизбежно переполнение даже Int64 для Value, и уж очень долго будет считать.. В наших тестах просчитываются игры: C{52,1} * C{51,5} * C{46,4} = 52 * 2349060 * 163185 = 19,933,230,517,200
Если добавить обмен 1 карты, то считать уже надо: C{52,1} * C{51,5} * (C{46,4} + C{5,4} * C{42,1} * C{41,4}) = 52 * 2349060 * (163185 + 5 * 42 * 101270) = 122151120 * 21266700 =
2,597,751,223,704,000
Короче гроб.. В лучшем случае будет в 210 (C{5,4} * C{42,1}) раз дольше Кто интересно будет ждать 3.5 часа? Надеюсь, правильно сосчитал... устал блин.