| Самое быстрое определение покерной комбинации — Часть 2 ID:25243 |
Чт, 25 октября 2007 23:36 [#] [») |
|
|
Эх, мог бы получить баблз за это  Но, сейчас практически не востребован. Пропадет, а жалко...
1. Ненужно бездумно копировать код!
2. Все константы должны совпадать с моими!
3. Все структуры (records) должны совпадать с моими!
4. Дополнительные массивы должны быть явно определены...
Не претендую, что это будет самый-самый оптимальный алгоритм... Но лучшего никогда и нигде в доступном виде не было! Это претендент, по сути... Кто поймет — милости прошу пообщаться.. Будут доп. идеи — вдвойне. Кстати, версия чуть более оптимальная конечно есть, но понятно, из-за личных соображений не буду афишировать...
Алгоритм практически равен извлечению данных из таблицы 13^5 с доп. проверкой на флешь, немного уступает 52^5.. Однако экономия RAM — вверх оптимизации, имхо..
Из всей арифметики(?) — банальные OR-AND-XOR. Стиль программирования конечно стремный... Но чего не сделаешь, лишь бы...
Собственно код:
<div style="margin:20px; margin-top:5px">
<div class="smallfont" style="margin-bottom:2px">Код:</div>
<pre class="alt2" dir="ltr" style="
margin: 0px;
padding: 4px;
border: 1px inset;
width: 640px;
height: 498px;
text-align: left;
overflow: auto">procedure FastEstimateHand(var Hand: THand); register; assembler;
asm
PUSH EBX
PUSH ESI
MOV ESI, EAX
XOR EAX, EAX
MOV EDX, [ESI + THand.Cards] // Pointer on First Card
MOV EBX, [ESI + THand.Cards + 4] // Pointer on Second Card
MOV AX, word ptr [EDX + TCard.Mask]
MOV EDX, EAX // OR Mask
MOV ECX, EAX // XOR Mask
MOV AX, word ptr [EBX + TCard.Mask]
MOV EBX, [ESI + THand.Cards + 8] // Pointer on Third Card
OR DX, AX
XOR CX, AX
MOV AX, word ptr [EBX + TCard.Mask]
MOV EBX, [ESI + THand.Cards + 12] // Pointer on Fourth Card
OR DX, AX
XOR CX, AX
MOV AX, word ptr [EBX + TCard.Mask]
MOV EBX, [ESI + THand.Cards + 16] // Pointer on Fifth Card
OR DX, AX
XOR CX, AX
MOV AX, word ptr [EBX + TCard.Mask]
XOR EBX, EBX
OR DX, AX
MOV BX, word ptr [BIT_COUNT16 + EDX * 2]
XOR CX, AX
JMP @Vector.Pointer[EBX * 4]
@Vector:
DD @Kinds0 // Error
DD @Kinds1 // Error
DD @Kinds2 // Full House, or Four Kinds
DD @Kinds3 // Two Pairs, or Three Kinds
DD @Kinds4 // One Pair
DD @Kinds5 // Blank, AK, Straight, Flush, or Straight Flush
@Kinds0:
@Kinds1:
MOV byte ptr [ESI + THand.Combination], COMBINATION_BLANK
POP ESI
POP EBX
RET
@Kinds2:
MOV ECX, 1
MOV EBX, [ESI + THand.Cards + 12]
TEST word ptr [EBX + TCard.Mask], AX
JZ @M3
INC CX
@M3:
MOV EBX, [ESI + THand.Cards + 8]
TEST word ptr [EBX + TCard.Mask], AX
JZ @M2
INC CX
@M2:
MOV EBX, [ESI + THand.Cards + 4]
TEST word ptr [EBX + TCard.Mask], AX
JZ @M1
INC CX
@M1:
MOV EBX, [ESI + THand.Cards]
TEST word ptr [EBX + TCard.Mask], AX
JZ @M0
INC CX
@M0:
JMP @Kinds2Vector.Pointer[ECX * 4]
@Kinds2Vector:
DD @Kinds0
DD @K1
DD @K2
DD @K3
DD @K4
@K1: //
XOR DX, AX
MOV word ptr [ESI + THand.Detail], AX
MOV word ptr [ESI + THand.Detail + 2], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_FOUR_KIND
POP ESI
POP EBX
RET
@K2: //
XOR DX, AX
MOV word ptr [ESI + THand.Detail], AX
MOV word ptr [ESI + THand.Detail + 2], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_FULL_HOUSE
POP ESI
POP EBX
RET
@K3: //
XOR DX, AX
MOV word ptr [ESI + THand.Detail + 2], AX
MOV word ptr [ESI + THand.Detail], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_FULL_HOUSE
POP ESI
POP EBX
RET
@K4: //
XOR DX, AX
MOV word ptr [ESI + THand.Detail + 2], AX
MOV word ptr [ESI + THand.Detail], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_FOUR_KIND
POP ESI
POP EBX
RET
@Kinds3:
MOV BX, CX
XOR CX, DX
TEST CX, CX
JZ @ThreeKind
XOR DX, BX
MOV word ptr [ESI + THand.Detail], BX
MOV word ptr [ESI + THand.Detail + 2], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_TWO_PAIRS
POP ESI
POP EBX
RET
@ThreeKind:
// MaskOR in EDX
// AX = Last Index
MOV EBX, [ESI + THand.Cards]
MOV CX, word ptr [EBX + TCard.Mask]
XOR AX, CX
TEST AX, CX
JZ @FindKind
MOV EBX, [ESI + THand.Cards + 4]
MOV CX, word ptr [EBX + TCard.Mask]
XOR AX, CX
TEST AX, CX
JZ @FindKind
MOV EBX, [ESI + THand.Cards + 8]
MOV CX, word ptr [EBX + TCard.Mask]
@FindKind:
XOR DX, CX
MOV word ptr [ESI + THand.Detail + 2], CX
MOV word ptr [ESI + THand.Detail], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_THREE_KIND
POP ESI
POP EBX
RET
//—————-
@Kinds4:
XOR DX, CX
MOV word ptr [ESI + THand.Detail], CX
MOV word ptr [ESI + THand.Detail + 2], DX
MOV byte ptr [ESI + THand.Combination], COMBINATION_ONE_PAIR
POP ESI
POP EBX
RET
@Kinds5:
XOR EAX, EAX
MOV AL, byte ptr [CMB_DETECT + EDX]
CMP DX, MASK_STRAIGHT_5A
JNZ @M20
XOR DX, MASK_A
@M20:
MOV [ESI + THand.Detail], EDX
// Recode if Flush detected
MOV EDX, [ESI + THand.Cards]
MOV ECX, [ESI + THand.Cards + 4]
MOV BX, word ptr [EDX + TCard.SuitIndex]
OR BX, [ECX + TCard.SuitIndex]
MOV EDX, [ESI + THand.Cards + 8]
MOV ECX, [ESI + THand.Cards + 12]
OR BX, [EDX + TCard.SuitIndex]
OR BX, [ECX + TCard.SuitIndex]
MOV EDX, [ESI + THand.Cards + 16]
CMP [EDX + TCard.SuitIndex], BX
JNZ @Kinds5E
// Flush is Detect
MOV AL, byte ptr [@CONV_TABLE + EAX]
MOV EDX, [ESI + THand.Detail]
CMP DX, MASK_STRAIGHT_AT
JNZ @Kinds5E
MOV AL, COMBINATION_ROYAL_FLUSH
@Kinds5E:
MOV byte ptr [ESI + THand.Combination], AL
POP ESI
POP EBX
RET
@CONV_TABLE:
DB COMBINATION_FLUSH
DB COMBINATION_FLUSH
DB COMBINATION_ONE_PAIR
DB COMBINATION_TWO_PAIRS
DB COMBINATION_THREE_KIND
DB COMBINATION_FLUSH
DB COMBINATION_FLUSH
DB COMBINATION_STRAIGHT_FLUSH
end;</pre>
</div>
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25244 ответ на 25243 |
Пт, 26 октября 2007 00:22 («] [#] [») |
|
|
Так, мои структуры:
<div style="margin:20px; margin-top:5px">
<div class="smallfont" style="margin-bottom:2px">Код:</div>
<pre class="alt2" dir="ltr" style="
margin: 0px;
padding: 4px;
border: 1px inset;
width: 640px;
height: 178px;
text-align: left;
overflow: auto">type
PHand = ^THand;
THand = packed record
Cards: array [0..6] of PCard;
Count: Word;
Combination: Byte;
Bonus: Byte;
Detail: Longword;
Evaluate: Longword;
end;</pre>
</div>Cards — массив поинтеров на карты (до 7)
Count — бесполезно для этой процедуры
Combination — собственно комбинация
Bonus — бонус комбинация (не учитывается здесь)
Detail — одно из главных полей (кикеры)
Evaluate — флаги для определения комбинаций
В общем, вся структура тянется почти с самого первого моего анализатора, может и зря, но уж как есть...
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25245 ответ на 25243 |
Пт, 26 октября 2007 00:33 («] [#] [») |
|
|
Комбинации:
<div style="margin:20px; margin-top:5px">
<div class="smallfont" style="margin-bottom:2px">Код:</div>
<pre class="alt2" dir="ltr" style="
margin: 0px;
padding: 4px;
border: 1px inset;
width: 640px;
height: 242px;
text-align: left;
overflow: auto">const
COMBINATION_BLANK = 00;
COMBINATION_ACE_KING = 01;
COMBINATION_ONE_PAIR = 02;
COMBINATION_TWO_PAIRS = 03;
COMBINATION_THREE_KIND = 04;
COMBINATION_SKIP_STRAIGHT = 05;
COMBINATION_WRAP_STRAIGHT = 06;
COMBINATION_STRAIGHT = 07;
COMBINATION_FLUSH = 08;
COMBINATION_FULL_HOUSE = 09;
COMBINATION_FOUR_KIND = 10;
COMBINATION_STRAIGHT_FLUSH = 11;
COMBINATION_ROYAL_FLUSH = 12;</pre>
</div>Структура карты:
<div style="margin:20px; margin-top:5px">
<div class="smallfont" style="margin-bottom:2px">Код:</div>
<pre class="alt2" dir="ltr" style="
margin: 0px;
padding: 4px;
border: 1px inset;
width: 640px;
height: 114px;
text-align: left;
overflow: auto">type
PCard = ^TCard;
TCard = packed record
Kind, Suit, Mask, XorMask: Word;
SuitIndex, ID, R1, R2: Word;
end;</pre>
</div>
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25246 ответ на 25243 |
Пт, 26 октября 2007 01:02 («] [#] [») |
|
|
Отдельно про Detail. Все можно было упростить, но эта инфа играет ключевую роль в дальнейших вычислениях... В это поле кодируется информация о топах и кикерах, например: COMBINATION_ONE_PAIR = пара записывается в старшие 16 bit, кикеры в младшие 16 или COMBINATION_FULL_HOUSE = тройка в старших 16 бит, пара в младшие, ну и т.п.
Двойка — нулевой бит, туз соответственно — двенадцатый. Это было удобно для сравнения по старшинству в случае равной комбинации. Раньше кстати использовал только 26 бит, но так как не смог закодировать все комбинации в это число, то отказался от этого. Удобно использовать при мат. сравнениях или для извлечения значений (AND+BSR(F)), не говоря уже о масках... Завтра продолжу...
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25247 ответ на 25243 |
Пт, 26 октября 2007 02:05 («] [#] [») |
|
|
не хочется флудить в такой ветке, всеже спрошу: для рук из 6 и 7 карт все аналогично? массивы 13^X для разных правил формируются на лету или заранее? У меня была идея унификации всех возможных рук в больших таблицах а затем определения параметров руки по ее уникальному ноиеру из маленькой таблицы в зависимоти от правил (круговые стриты, ТК играет, 3 пары, двойные комбинации, . т.п.). На счолько % использование функций на ассемблере повышает производительность против кода на си или паскале? (я пробовал, у меня получается ХУЖЕ).
И еще замечание по подходу вообще. Нам требуется супербыстродействие при многократных вызовах данной функции. Многократные вызовы органеизуются в функциях более высого уровня, и очевидно что это функции перебора карт, в циклах. Используя этот факт мы можем уменьшить число выполняемых операций в данной функции если вынесем формирование адреса в таблице для каждой перебираемой карты за пределы этой функции в те циклы, где эта карта перебирается, там же можно отслеживать и флаг масти (так же поэтапно), в этом случае от самой функции отсанется только выборка значения из таблиц.
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25248 ответ на 25243 |
Пт, 26 октября 2007 12:32 («] [#] [») |
|
|
| Korovin писал пт, 26 октября 2007 02:05 | | не хочется флудить в такой ветке, всеже спрошу: для рук из 6 и 7 карт все аналогично? массивы 13^X для разных правил формируются на лету или заранее? |
Фишка в том, что массивов 13^X я более не использую вообще. Их у меня уже нет. Логика всего алгоритма заключается в подсчете разнотипных карт по рангу, для этого служит маска по OR. То есть, например у нас K282A. Каждому рангу назначен свой бит. Эти биты объединяются по OR и получаем для K282A: 1100001000001. Очевидно, что сумма битов = 4. Значит, это пара. Для суммы в 3 бита — две пары или тройка, для суммы в 2 бита — фулл или коре. Сумма с 1 битом не может быть никогда. Это все справедливо для руки в 5 карт.. Для рук в 6 и 7 используются другие функции, на аналогичном алгоритме, но много сложнее.
Для подсчета количества битов нет ассемблерной команды (по крайней мере документированной), для этого использую таблицу BIT_COUNT16. И еще одна таблица CMB_DETECT нужна для определения AK и стрейтов (их может быть три: тигр-стрейт, круговой и обычный).
| Korovin писал пт, 26 октября 2007 02:05 | | У меня была идея унификации всех возможных рук в больших таблицах а затем определения параметров руки по ее уникальному ноиеру из маленькой таблицы в зависимоти от правил (круговые стриты, ТК играет, 3 пары, двойные комбинации, . т.п.). На счолько % использование функций на ассемблере повышает производительность против кода на си или паскале? (я пробовал, у меня получается ХУЖЕ). |
ASM применил в основном для того, чтобы организовать безифовые переходы (так я их называю).
Например, JMP @Vector.Pointer[EBX * 4]
Это аналог
[code]
case BitCount of
0,1: goto ..
2: goto ..
3: goto ..
4: goto ..
5: goto ..
end;
[/ code]
Естественно, что на ASM это будет и в разы быстрее и меньше кода.. Таких переходов здесь несколько.
| Korovin писал пт, 26 октября 2007 02:05 | | И еще замечание по подходу вообще. Нам требуется супербыстродействие при многократных вызовах данной функции. Многократные вызовы органеизуются в функциях более высого уровня, и очевидно что это функции перебора карт, в циклах. Используя этот факт мы можем уменьшить число выполняемых операций в данной функции если вынесем формирование адреса в таблице для каждой перебираемой карты за пределы этой функции в те циклы, где эта карта перебирается, там же можно отслеживать и флаг масти (так же поэтапно), в этом случае от самой функции отсанется только выборка значения из таблиц. |
Я думаю по другому, применительно к моему методу, можно организовать предобработку и юстировку... Предобработка рассчитывает промежуточные значения (по 4 картам), а юстировка 1 пермутируемую карту с промежуточными значениями. Но это практически не нужно, так как есть более элегантное решение — предсказание (аналог твоего сжатия мастей).
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25249 ответ на 25243 |
Пт, 26 октября 2007 13:15 («] [#] [») |
|
|
|
Если так проще и быстрее то вопросов больше нет.
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25251 ответ на 25243 |
Пн, 29 октября 2007 15:14 («] [#] [») |
|
|
|
Правильно ли я понял, что у тебя определяется только комбинация (например, флеш(=8)) рук (то есть набора 5 или более карт), а не количество комбинаций у делера, "есть игра", меньших и равных? Кстати, какого быстродействия ты достиг в предыдущем тесте (перебор всех комбинаций 5 карт + 1 карты дилера), сделал ли ты ускорение мен и какая скорость у тебя рассчета покупки игры?
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25252 ответ на 25243 |
Пн, 29 октября 2007 16:01 («] [#] [») |
|
|
| Шамсутдинов писал пн, 29 октября 2007 14:14 | | Правильно ли я понял, что у тебя определяется только комбинация (например, флеш(=8)) рук (то есть набора 5 или более карт), а не количество комбинаций у делера, "есть игра", меньших и равных? |
Чета я не понял что ты спросил..?
| Шамсутдинов писал пн, 29 октября 2007 14:14 | | Кстати, какого быстродействия ты достиг в предыдущем тесте (перебор всех комбинаций 5 карт + 1 карты дилера), сделал ли ты ускорение мен и какая скорость у тебя рассчета покупки игры? |
Давно уже ничего не мерил и давно все забросил.. Сейчас рулю Холдем. А достижения — разработка предсказателя, отсекающего все однотипные варианты из перебора.. вычисляются только те расклады, которые уникальны. С подвижкой на обмены.. Оптимизировать перебор была вообще глупая идея...
Ну а код определения руки выложил из последней версии, так как таблицы более не использую, да и в свете идей над Холдемом, может статься, что незачем определять руки.. и перебор не нужен...
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25253 ответ на 25243 |
Вт, 30 октября 2007 14:20 («] [#] [») |
|
|
|
Понятно.
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25274 ответ на 25243 |
Вт, 20 ноября 2007 09:25 («] [#] [») |
|
|
Если я правильно понимаю, то всё уже украдено до нас:
<div style="margin:20px; margin-top:5px">
<div class="smallfont" style="margin-bottom:2px">Код:</div>
<pre class="alt2" dir="ltr" style="
margin: 0px;
padding: 4px;
border: 1px inset;
width: 640px;
height: 498px;
text-align: left;
overflow: auto"> void Combination::Parse(__int64 cards)
{
unsigned int four_mask, three_mask, two_mask;
value_ = 0;
const unsigned int sd = (unsigned short int)cards;
const unsigned int ss = *((unsigned short int *)(&cards)+1);
const unsigned int sh = *((unsigned short int *)(&cards)+2);
const unsigned int sc = *((unsigned short int *)(&cards)+3);
const unsigned int ranks = (sc | sd | sh | ss);// & 0xFFF;
const unsigned int n_ranks = nBitsTable[ranks];
const unsigned int n_dups = ((unsigned int)(7 - n_ranks));
if (n_ranks >= 5)
{
if (nBitsTable[ss] >= 5)
{
if (straightTable[ss] != 0)
{
value_ = HANDTYPE_VALUE_STRAIGHTFLUSH + (unsigned int)(straightTable[ss] << TOP_CARD_SHIFT);
return;
}
else
value_ = HANDTYPE_VALUE_FLUSH + topFiveCardsTable[ss];
}
else if (nBitsTable[sc] >= 5)
{
if (straightTable[sc] != 0)
{
value_ = HANDTYPE_VALUE_STRAIGHTFLUSH + (unsigned int)(straightTable[sc] << TOP_CARD_SHIFT);
return;
}
else
value_ = HANDTYPE_VALUE_FLUSH + topFiveCardsTable[sc];
}
else if (nBitsTable[sd] >= 5)
{
if (straightTable[sd] != 0)
{
value_ = HANDTYPE_VALUE_STRAIGHTFLUSH + (unsigned int)(straightTable[sd] << TOP_CARD_SHIFT);
return;
}
else
value_ = HANDTYPE_VALUE_FLUSH + topFiveCardsTable[sd];
}
else if (nBitsTable[sh] >= 5)
{
if (straightTable[sh] != 0)
{
value_ = HANDTYPE_VALUE_STRAIGHTFLUSH + (unsigned int)(straightTable[sh] << TOP_CARD_SHIFT);
return;
}
else
value_ = HANDTYPE_VALUE_FLUSH + topFiveCardsTable[sh];
}
else
{
unsigned int st = straightTable[ranks];
if (st != 0)
value_ = HANDTYPE_VALUE_STRAIGHT + (st << TOP_CARD_SHIFT);
}
/*
Another win — if there can't be a FH/Quads (n_dups < 3),
which is true most of the time when there is a made mask, then if we've
found a five card mask, just return. This skips the whole process of
computing two_mask/three_mask/etc.
*/
if (value_ != 0 && n_dups < 3)
return;// retval;
}
switch (n_dups)
{
case 0:
/* It's a no-pair mask */
value_ = HANDTYPE_VALUE_HIGHCARD + topFiveCardsTable[ranks]; return;
case 1:
{
two_mask = ranks ^ (sc ^ sd ^ sh ^ ss);
value_ = (unsigned int) (HANDTYPE_VALUE_PAIR + (topCardTable[two_mask] << TOP_CARD_SHIFT));
unsigned int t = ranks ^ two_mask; /* Only one bit set in two_mask */
unsigned int kickers = (topFiveCardsTable[t] >> 4) & ~FIFTH_CARD_MASK;
value_ += kickers;
return;// retval;
}
case 2:
/* Either two pair or trips */
two_mask = ranks ^ (sc ^ sd ^ sh ^ ss);
if (two_mask != 0)
{
unsigned int t = ranks ^ two_mask; /* Exactly two bits set in two_mask */
value_ = (unsigned int) (HANDTYPE_VALUE_TWOPAIR + (topFiveCardsTable[two_mask] & (TOP_CARD_MASK | SECOND_CARD_MASK))
+ (topCardTable[t] << THIRD_CARD_SHIFT));
return;// retval;
}
else
{
//unsigned int t, second;
three_mask = ((sc & sd) | (sh & ss)) & ((sc & sh) | (sd & ss));
value_ = (unsigned int) (HANDTYPE_VALUE_TRIPS + (topCardTable[three_mask] << TOP_CARD_SHIFT));
unsigned int t = ranks ^ three_mask; /* Only one bit set in three_mask */
unsigned int second = topCardTable[t];
value_ += (second << SECOND_CARD_SHIFT);
t ^= (1U << (int)second);
value_ += (unsigned int) (topCardTable[t] << THIRD_CARD_SHIFT);
return;// retval;
}
default:
/* Possible quads, fullhouse, straight or flush, or two pair */
four_mask = sh & sd & sc & ss;
if (four_mask != 0)
{
unsigned int tc = topCardTable[four_mask];
value_ = (unsigned int) (HANDTYPE_VALUE_FOUR_OF_A_KIND + (tc << TOP_CARD_SHIFT)
+ ((topCardTable[ranks ^ (1U << (int)tc)]) << SECOND_CARD_SHIFT));
return;// retval;
}
two_mask = ranks ^ (sc ^ sd ^ sh ^ ss);
if (nBitsTable[two_mask] != n_dups)
{
//unsigned int tc, t;
three_mask = ((sc & sd) | (sh & ss)) & ((sc & sh) | (sd & ss));
//value_ = HANDTYPE_VALUE_FULLHOUSE;
unsigned int tc = topCardTable[three_mask];
value_ += HANDTYPE_VALUE_FULLHOUSE + (tc << TOP_CARD_SHIFT);
unsigned int t = (two_mask | three_mask) ^ (1U << (int)tc);
value_ += (unsigned int) (topCardTable[t] << SECOND_CARD_SHIFT);
return;// retval;
}
//if (value_ != 0) /* flush and straight */
// return;// retval;
//else
if(value_ == 0)
{
/* Must be two pair */
//unsigned int top, second;
//value_ = HANDTYPE_VALUE_TWOPAIR;
unsigned int top = topCardTable[two_mask];
value_ = HANDTYPE_VALUE_TWOPAIR + (top << TOP_CARD_SHIFT);
unsigned int second = topCardTable[two_mask ^ (1 << (int)top)];
value_ += (second << SECOND_CARD_SHIFT);
value_ += (unsigned int) ((topCardTable[ranks ^ (1U << (int)top) ^ (1 << (int)second)]) << THIRD_CARD_SHIFT);
return;// retval;
}
}
}</pre>
</div>Я это использовал для самопального покерстова %), но пришёл к выводу, что сравнивать "в лоб" бесперспективно, и теперь сооружаю совершенно другой алгоритм.
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25280 ответ на 25243 |
Чт, 3 января 2008 17:54 («] [#] [») |
|
|
Что-то с ходу не разберу, 1,2,3,... все кикеры вычисляются или нет?
В первом и втором вариенте? Я писал анналогичную программу. Быстродействие - что-то все комбинации 7 карт за 2 часа перебирала, (могу и наврать но порядок такой).
|
|
|
|
|
странно видеть соревнования в изяществе кода и "крутости" алгоритма там, где важна скорость. самый лучший вариант - это загнать все в таблицы. и тогда функция определения комбинации не важна, ни ее скорость ни ее изящество.
моя функция определяет 140млн 5ти картрочных комбинаций в секунду, и так же способна определить 20 млн в сек мо игры 5ти карточной комбинации против изветсной карты дилера, с учетом вышедших карт.
все строится на выборках из заранее просчитанных таблиц.
|
|
|
|
|
слабовато будет 
еще в прошлом году были результаты около 450 млрд./сек (* 20 млн в сек мо игры 5ти карточной комбинации против изветсной карты дилера *).
а еще один товарищ написал прогу которая считала мо всех 5-рок против дилера, а их примерно 19,9 трлн за 5 сек, считай сам какая скорость и это без таблиц.
и вообще это уже никому не интересно.
а вот сравнить в холдем 5 флоп и 2 пары рук, т.е. две семикарточные комбинации. есть две руки и флоп. перебираем флоп. скока млн сравнений в сек?
у меня если обе руки известны, все 1712304 сравнений за 0,21 сек, без формул, все в лоб (примерно 8 млн/сек). а если обе руки закрыты - чуть больше 6 млн/сек. силу 5-ки определить легко, вот силу 7-ки определи также быстро как 5-ки.
|
|
|
|
|
| fabrica | слабовато будет
еще в прошлом году были результаты около 450 млрд./сек (* 20 млн в сек мо игры 5ти карточной комбинации против изветсной карты дилера *).
а еще один товарищ написал прогу которая считала мо всех 5-рок против дилера, а их примерно 19,9 трлн за 5 сек, считай сам какая скорость и это без таблиц.
и вообще это уже никому не интересно.
а вот сравнить в холдем 5 флоп и 2 пары рук, т.е. две семикарточные комбинации. есть две руки и флоп. перебираем флоп. скока млн сравнений в сек?
у меня если обе руки известны, все 1712304 сравнений за 0,21 сек, без формул, все в лоб (примерно 8 млн/сек). а если обе руки закрыты - чуть больше 6 млн/сек. силу 5-ки определить легко, вот силу 7-ки определи также быстро как 5-ки. |
450млрд? случайных 5ти картрочных комбинаций в сек? не верю.
у меня на определение тратится 6 комманд процессора (выборка из таблицы). как возможно сделать быстрее? вероятно мы говорим о разных вещах.
одно дело перебрать все комбинации (причем с использованием оптимизации), другое дело оценить случайные комбинации.
у меня на полный перебор тоже уйдет меньше 0.0001 сек. за счет оптимизации, но это не значит что она перебрала все миллиарды комбинаций (вместе с обменами). перебор гораздо меньше за счет сжатых таблиц. тут скорее надо сравнивать cкорость расчета мо бокса на заданных условиях. моя программа переберет все возможные пятерки быстрее чем за 5 сек (и это на одном ядре, счас вот работаю над мультитредингом, и использованием map+reduce)
про семь карт не понял чего с чем сравнивать.
у меня счас есть 2карты + флоп - около сек.
но там тупой перебор по таблице из 130млн вариантов.
если будет известно обе руки, то думаю гденть 0.2-0.3 сек и будет. можно распаралелить на 2 ядра, будет в 2 раза быстрее.
только зачем...
|
|
|
|
|
Да, немного про разное.
При больших объемах не выгодно считать в лоб, из таблиц. Выгодней комбинаторно.
А если в лоб, у меня на пне-4, 1.2 ГГц, 30 раз прогон всех 5-ок занимает 2 сек ровно. Т.е. 30*2598960=77968800 за 2 сек. Без таблиц. Это примерно 39 млн./сек.
А вот еще точнее именно скорость определения.
50 циклов занимает 3,36сек. А если выкинуть само определение, оставить только цикл 0,39сек. Т.е. 50 циклов (около 130 млн) за 3 сек. Даже 43 млн получается.
А про 7-ки. Это из Texas Hold'em.
(* у меня счас есть 2карты + флоп - около сек.
но там тупой перебор по таблице из 130млн вариантов. *)
Воооо... 2 карты+флоп - 1 сек? А я 1712304 парных определений комбинаций за 0,21сек. Т.е. определение 5-ти карточной комбинации из 2карты+флоп 16 млн раз в сек (1712304 * 2 /0,21). Причем не просто силу комбинации, а точное ее значение со всеми кикерами. Т.е. чтобы потом можно было сравнить две комбинации, какая сильней простым сравнением.
Пока только в лоб приходится. Не могу пока комбинаторно, нет идей. Мож у кого есть идеи?
|
|
|
|
|
| fabrica | да, немного про разное.
при больших объемах не выгодно считать в лоб, из таблиц. выгодней комбинаторно.
а если в лоб, у меня на пне-4, 1.2 ггц, 30 раз прогон всех 5-ок занимает 2 сек ровно. т.е. 30*2598960=77968800 за 2 сек. без таблиц. это примерно 39 млн./сек.
а вот еще точнее именно скорость определения.
50 циклов занимает 3,36сек. а если выкинуть само определение, оставить только цикл 0,39сек. т.е. 50 циклов (около 130 млн) за 3 сек. даже 43 млн получается.
а про 7-ки. это из texas hold'em.
(* у меня счас есть 2карты + флоп - около сек.
но там тупой перебор по таблице из 130млн вариантов. *)
воооо... 2 карты+флоп - 1 сек? а я 1712304 парных определений комбинаций за 0,21сек. т.е. определение 5-ти карточной комбинации из 2карты+флоп 16 млн раз в сек (1712304 * 2 /0,21). причем не просто силу комбинации, а точное ее значение со всеми кикерами. т.е. чтобы потом можно было сравнить две комбинации, какая сильней простым сравнением.
пока только в лоб приходится. не могу пока комбинаторно, нет идей. мож у кого есть идеи? |
лан, понял что мы говорим на разных языках
про холдем.
давайте определимся с постановкой задачи, а то я чтото не понимаю чего надо вычислить, поэтому и не могу сравнить результаты.
|
|
|
|
|
Да вроде я уже на том языке написал.
цитата - моя программа переберет все возможные пятерки быстрее чем за 5 сек (и это на одном ядре, счас вот работаю над мультитредингом, и использованием map+reduce)
И я про тоже. Я перебрал 30 раз подряд все возможные пятерки за 2 сек. Т.е. "все возможные пятерки" за 2/30сек~0,07сек - тоже быстрей чем за 5 сек. Без массивов, оптимизаций и т.д. "в лоб" именно используя идею Sharky, и тоже самое сделал для холдема. Загоняю 7 чисел и за проход определяю силу максимальной комбинации с кикерами.
Я раньше тоже брал из массива. Но занимает много памяти, и совсем не быстрей. Цикл определения силы комбинации оказалось быстрей, чем вычисление адреса в массиве.
И еще момент, а у тебя пустые комбинации одинаковые или различаются по силе? Т.е. A,D,8,5,3 без масти сильней чем A,D,8,5,2 или тебе всеравно? У меня первая сильней. В соответствие каждой пятерке ставится некое число, которое означает силу комбинации. При сравнении можно узнать какая из них старше.
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25376 ответ на 25243 |
Сб, 4 апреля 2009 13:52 («] [#] [») |
|
|
лан, холдем мне пока не интересен
мне интересно какой рекорд в расчете такой задачи:
есть комбинация, есть карта дилера, есть вышедшие карты. надо расчитать МО руки и МО всех возможных замен(1-2-3-4-5), всего их 31. для самого худшего случая, когда вышедших карт нет, т.е. для первого бокса.
вот и какое лучше время в нахождении этих 31 чисел? я так понял что это 5 секунд?
|
|
|
| Re: Самое быстрое определение покерной комбинации — Часть 2 ID:25377 ответ на 25243 |
Сб, 4 апреля 2009 15:30 («] [#] |
|
|
интересует только точный расчет.
| Fabrica | | И еще момент, а у тебя пустые комбинации одинаковые или различаются по силе? Т.е. A,D,8,5,3 без масти сильней чем A,D,8,5,2 или тебе всеравно? У меня первая сильней. В соответствие каждой пятерке ставится некое число, которое означает силу комбинации. При сравнении можно узнать какая из них старше. |
у меня так же. каждой руке (всего 2598960) сопоставляется ее код (всего 7462), однозначно характеризующий ее старшинство, и применимый для сравнения. в нем учитываются все пять карт, так что AQ853 будет старше AQ852.
|
|
|
