Блог «Розв’язання покеру»

    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Коли пан буде мати час та натхнення, то буде у цьому блозі писати різні цікаві речі. Оскільки у сферу моїх зацікавлень входять ігри [математика] взагалі, покер [теорія ігор] зокрема, то переважно це будуть пости, пов’язані з цією тематикою.

      Коротко про себе: зараз живу у Швеції, місто Växjö, працюю програмістом. Покер більше хобі: граю небагато, заради задоволення. Також граю у шахи, поточний рейтинг 2071.
  • 1326 ответов
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Правила гри AKQJj

      Для того, зоб розібратися, як працює теорія ігор, нам треба приклад гри. Покер це дуже складна гра. Знайти розв’язок для нього дуже важко. «Камінь-ножиці-бумага», навпаки, дуже проста гра. На її прикладі деякі аспекти, які виникають у покері, будуть призовані. Таким чином, наша гра, яку ми покладемо на анатомічний столик, має буди простою та нагадувати покер. Для цього я придумав таку гру, під мнемонікою AKQJj:

      1. Колода карт складається з тузів, королів, дам та валетів. Порядок карт звичайний. Для цікавості, додамо у цю колоду два джокера, який буде бити туза, але програвати усім іншим картам.

      2. Перед початком гри у кожного гравця буде STACK фішок. На початку перший гравець кладе у банк SB фішок, другий гравець BB фішок. Потім кожному гравцю з колоди роздають по одній карті. Кожен бачить свою карту, але не бачить карту противника.

      3. Перший гравець вибирає одну з двох можливостей, сказати «pass», або «all-in». Якщо перший гравець каже «pass», то банк виграє другий гравець. Якщо перший гравець каже «all-in», то він має додати у банк всі свої фішки.

      4. Якщо перший гравець зіграв «all-in», то другий гравець вибирає одну з двох можливостей, сказати «pass», або «call». Якщо другий гравець каже «pass», то банк виграє перший гравець. Якщо другий гравець каже «call», то він має додати у банк всі свої фішки, після чого карти гравців відкриваються. Той, хто виграв порівняння, забирає увесь банк.

      Пояснення: Я не знаю, чи це гарний приклад, чи ні. Спробуємо розв’язати та подивитися. Додавання джокерів робить гру більш азартною, та не схожою на Holdem, де є чарівна комбінація :Ax: :Ax: . Але мені так цікавіше, подивимося, чи це вдалий хід чи ні.

      P. S. Було б добре додати смайл «джокер».
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Стратегії у грі AKQJj

      Спробуємо перекласти нашу гру на математичну мову. З точки зору теорії ігор, антагоністична гра двох осіб це набір стратегій для кожного гравця та матриця гри, де рядки відповідають стратегіям першого гравця, стовпчики відповідають стратегіям другого гравця, а на перехресті розташовано виграш першого гравця, який дорівнює програшу другого гравця, у разі, якщо гравці вибрали відповідні стратегії. Виграш може бути від від’ємним, програш це виграш з протилежним знаком. Якщо перший гравець отримав виграш у -10 фішок, це просто означаю, що він програв +10 десять фішок, або суперник виграв +10 фішок, або суперник програв -10 фішок. Може трохи незвично, але математично.

      Таким чином стратегія це набір правил для кожного з гравців, котрі однозначно визначають його дії в будь-якій ігровій ситуації. А у нас таких ситуацій дві: слово першого гравця на початку, слово другого гравця, якщо перший сказав «all-in». У нашій грі стратегія для першого гравця це буде набір карт, з якими він буде казати «all-in». Таку стратегію просто позначити просто перерахувавши всі карти, з якими він буде казати «all-in». Якщо ми умовимося позначати джокер маленької літерою j, то прикладом стратегії може бути AKQj: кажемо «all-in» у разі, якщо ми отримали туза, короля, даму або джокер. У разі валетів кажемо «pass». Аналогічно для другого гравця стратегія це набір карт, з якими він відповідає «call», наприклад AKj.

      Оскільки в нашій грі масті ніяк не впливають на результат, то ми можемо виділити 2^5 = 32 стратегії для кожного гравця. Це кількість різних підмножин з п’яти-елементної множини { A, K, Q, J, j }.

      Таким чином для нашого випадку, матриця гри має розмір 32x32. Якщо аналогічно підійти до Holdem Heads Up, де перед відкриттям флопа перший гравець може тільки піти «all-in», то стратегій буде 2 ^ (13^2) = 2^169 = 7.48 · 10^50.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Порівняння

      Припустимо, що перший гравець вибрав стратегію AKQj, а другий гравець стратегію AKj. Що кожний з гравців отримає у результаті? Зрозуміло, що це випадкова величина, яка залежить від того, які карти випали гравцям. Логічно домовитися, що відповідний елемент матриці гри має містити математичне сподівання цієї випадкової величини. Як його обчислити?

      Щоб відповісти на це запитання, нам потрібно проаналізувати усі варіанти роздачі карт, та обчислити EV за усім відомою формулою

      де I це множина усіх можливостей, p(i) це ймовірність можливості, x(i) це значення нашої випадкової величіні (виграш першого гравця).

      Добре, а які можливості та їх ймовірності можливі? Тут дуже просто. Перший гравець може отримати п’ять різних карт, другий гравець може отримати п’ять різних карт, тобто усього 25 можливостей. Тепер порахуємо ймовірності для цих можливостей. У нас усього 18 карт, або 18 * 17 = 306 варіантів роздати по одній карті двом гравцям. З них обидва гравці отримають джокер у 2 варіантах (перший отримає один з двох джокерів, а другий отримає що лишилося), джокер проти туза буде у 8 варіантах (два джокера, чотири туза), тут проти короля буде у 16 варіантах (чотири на чотири), тут проти туза 12 варіантів (чотири туза для першого гравця, іншому лишається лише три). Усі значення парні, знаменних також парний, так що можна скоротити усе на 2, що я зробив у таблиці нижче. Перевіряємо, чи все зійдеться. AK, AQ, AJ, KA, KQ, KJ, QA, QK, QJ, JA, JK, JQ це 12 можливостей по 16 варіантів кожне. AA, KK, QQ, JJ це 4 можливості по 12 варіантів кожне, Aj, Kj, Qj, Jj, jA, jK, jQ, jJ це 8 можливостей по 8 варіантів кожне, jj це одна можливість з двома варіантами. Тепер
      12*16 + 4*12 + 8*8 + 1*2 = 192 + 48 + 64 + 2 = 240 + 66 = 306, усе зійшлося. Крок зроблено у вірному напрямку.

      Тепер будемо використовувати ці дані щоб порахувати математичне сподівання порівняння стратегій AKQj vs AKj. Припустимо, що SB = ½, BB = 1, STACK = 10. Для кожної можливості легко обчислити результат порівняння. Наприклад, A vs K. Перший гравець грає «all-in», другий відповідає «call», перший виграє при відкритті карт 10 фішок противника. Або J vs j, перший гравець грає «pass», другий забирає SB.

      П’ятий стовпчик це результат перемноження третього та четвертого. Якщо знайти його суму, то ми отримаємо математичне сподівання виграшу першого гравця. Воно дорівнює -83/153 або -0.542483660131. Тобто на дистанції, якщо перший гравець буде притримуватися стратегії AKQj, а другий буде відповідати йому за стратегією AKj, то перший гравець буде програвати у середньому трохи більше ніж пів великого блайнду кожну роздачу.

      code:
                            Таблиця 1: порівняння стратегій AKQj vs AKj
      -----------------------------------------------------------------
      
      Гравець I    Гравець II   Ймовірність   Результат       P*X   
      -----------------------------------------------------------------
           A          A            6 / 153          0     
           A          K            8 / 153        +10      +80 / 153
           A          Q            8 / 153         +1       +8 / 153
           A          J            8 / 153         +1       +8 / 153
           A          j            4 / 153        -10      -40 / 153
      -----------------------------------------------------------------
           K          A            8 / 153        -10      -80 / 153
           K          K            6 / 153          0  
           K          Q            8 / 153         +1       +8 / 153
           K          J            8 / 153         +1       +8 / 153
           K          j            4 / 153        +10      +40 / 153
      -----------------------------------------------------------------
           Q          A            8 / 153        -10      -80 / 153
           Q          K            8 / 153        -10      -80 / 153
           Q          Q            6 / 153         +1       +8 / 153
           Q          J            8 / 153         +1       +8 / 153
           Q          j            4 / 153        +10      +40 / 153
      -----------------------------------------------------------------
           J          A            8 / 153         -½       -4 / 153
           J          K            8 / 153         -½       -4 / 153
           J          Q            8 / 153         -½       -4 / 153
           J          J            6 / 153         -½       -3 / 153
           J          j            4 / 153         -½       -2 / 153
      -----------------------------------------------------------------
           j          A            4 / 153        +10      +40 / 153
           j          K            4 / 153        -10      -40 / 153
           j          Q            4 / 153         +1        4 / 153
           j          J            4 / 153         +1        4 / 153
           j          j            1 / 153          0
      -----------------------------------------------------------------
                                                  Сума:    -83 / 153 = -0.542483660131
      
    • iva123
      iva123
      Модератор
      Модератор
      На форуме с: 29.05.2008 Сообщения: 57.126
      Будемо дуже раді якщо пан таки матиме час та натхнення для цікавих речей в блозі.


      Оригинал пользователя mustitz
      Було б добре додати смайл «джокер».
      Цей схожий:
    • Doomi4ka
      Doomi4ka
      Бронза
      На форуме с: 09.12.2007 Сообщения: 2.336
      Боюсь, якби я прочитала всю цю писанину, мій мозок вибухнув би :deadhappy:
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Оригинал пользователя iva123Будемо дуже раді якщо пан таки матиме час та натхнення для цікавих речей в блозі.
      Цікаве це відносне поняття.

      Оригинал пользователя Doomi4ka
      Боюсь, якби я прочитала всю цю писанину, мій мозок вибухнув би
      Коли я пробую читати деякі книжки з просунутої математики , зі мною трапляється схоже. Рятує лише те, що читати їх необов'язково.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Будуємо матрицю гри

      Тепер ми готові для обчислення матриці гри. Для цього на треба повторити попередній крок 1023 рази. Робити це руками у той час, коли вже розшифрований чоловічій геном, це збочення. Я пішов шляхом написання програми на мові програмування C. Тут я мушу розчарувати тих читачів, котрі програмують виключно під Windows: я сам зі світу Linux. До того ж не дуже переймаюся, якщо мій код не портується під компілятори Microsoft. Я розумію, що програмістів на цьому сайті небагато, тих, хто працює з Linux ще менше, але все-таки трохи прокоментую сирцевий код програми, який можна отримати за посиланням step-001.tar.bz2.

      Якщо викинути все зайве, пов’язане з парсингом командного рядка та виводом матриці гри, то текст програми скоротиться до наступного вигляду:

      code:
      /* Constants */
      
      #define COUNT_CARD             5
      #define COUNT_STRATEGY  (1 << COUNT_CARD)
      
      #define ACE     4
      #define KING    3
      #define QUEEN   2
      #define JACK    1
      #define JOKER   0
      
      #define FREQUENCY_FACTOR   (1.0 / 153.0)
      
      double bb = 1.0;
      double sb = 0.5;
      double stack = 10.0;
      double ante = 0.0;
      
      /* Tables */
      
      double game_table[COUNT_STRATEGY][COUNT_STRATEGY];
      double frequency[COUNT_CARD][COUNT_CARD] = {
          { 1, 4, 4, 4, 4 },
          { 4, 6, 8, 8, 8 },
          { 4, 8, 6, 8, 8 },
          { 4, 8, 8, 6, 8 },
          { 4, 8, 8, 8, 6 }
      };
      
      /* Calculations */
      
      static double simulation(int s1, int s2, int n1, int n2)
      {
          int mask1 = 1 << n1;
          if ((s1 & mask1) == 0) return -sb - 2*ante;
      
          int mask2 = 1 << n2;
          if ((s2 & mask2) == 0) return +bb + 2*ante;
      
          if (n1 == n2) return 0.0;
          if (n1 == ACE && n2 == JOKER) return -stack;
          if (n1 == JOKER && n2 == ACE) return +stack;
          return n1 > n2 ? +stack : -stack;
      }
      
      static void death_match(int s1, int s2)
      {
          double result = 0.0;
      
          for (int n1 = 0; n1 < COUNT_CARD; ++n1)
          for (int n2 = 0; n2 < COUNT_CARD; ++n2)
              result += frequency[n1][n2] * simulation(s1, s2, n1, n2);
      
          game_table[s1][s2] = FREQUENCY_FACTOR * result;
      }
      
      int main()
      {
          for (int s1 = 0; s1 < COUNT_STRATEGY; ++s1)
          for (int s2 = 0; s2 < COUNT_STRATEGY; ++s2)
              death_match(s1, s2);
          return 0;
      }


      Тут все досить просто. Кожна стратегія це бітова маска з п’яти елементів, де кожен біт відповідає за те, чи буде грати гравець з цією картою (біт дорівнює одиниці), або скаже «pass». Метод death_match виконує порівняння стратегій, обчислює математичне сподівання та зберігає його у матриці гри game_table. Метод simulation повертає детермінований результат у разі якщо гравці притримуються обраних стратегій s1, s2 у разі розкладу n1/n2. Масив frequency містить кількість варіантів кожній можливості розкладу.

      Програма може приймати декілька аргументів командного рядку. У приведеному нижче сценарії роботи друкується матриця гри у форматі, зручним для читача:

      code:
      $ ./poker-001 -h
      ./poker-001 [OPTIONS]
      Output maxtrix of the game.
        -h, --help                print this screen.
        -s, --sb, --small-blind   set double value for small blind.
        -b, --bb, --big-blind     set double value for big blind.
        -a, --ante                set double value for ante.
        -k, --stack               set double value for stack.
        -p, --pretty-print        pretty output style.
      $ ./poker-001 -p -d4
                 |       -       j       J      Jj       Q      Qj      QJ     QJj       K      Kj      KJ     KJj      KQ     KQj     KQJ    KQJj       A      Aj      AJ     AJj      AQ     AQj     AQJ    AQJj      AK     AKj     AKJ    AKJj     AKQ    AKQj    AKQJ   AKQJj
      -----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
        1.     - | -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000 -0.5000
        2.     j | -0.3333 -0.3399 -0.6209 -0.6275 -0.6209 -0.6275 -0.9085 -0.9150 -0.6209 -0.6275 -0.9085 -0.9150 -0.9085 -0.9150 -1.1961 -1.2026 -0.0980 -0.1046 -0.3856 -0.3922 -0.3856 -0.3922 -0.6732 -0.6797 -0.3856 -0.3922 -0.6732 -0.6797 -0.6732 -0.6797 -0.9608 -0.9673
        3.     J | -0.1667  0.0686 -0.2059  0.0294 -0.7418 -0.5065 -0.7810 -0.5458 -0.7418 -0.5065 -0.7810 -0.5458 -1.3170 -1.0817 -1.3562 -1.1209 -0.7418 -0.5065 -0.7810 -0.5458 -1.3170 -1.0817 -1.3562 -1.1209 -1.3170 -1.0817 -1.3562 -1.1209 -1.8922 -1.6569 -1.9314 -1.6961
        4.    Jj |  0.0000  0.2288 -0.3268 -0.0980 -0.8627 -0.6340 -1.1895 -0.9608 -0.8627 -0.6340 -1.1895 -0.9608 -1.7255 -1.4967 -2.0523 -1.8235 -0.3399 -0.1111 -0.6667 -0.4379 -1.2026 -0.9739 -1.5294 -1.3007 -1.2026 -0.9739 -1.5294 -1.3007 -2.0654 -1.8366 -2.3922 -2.1634
        5.     Q | -0.1667  0.0686  0.3039  0.5392 -0.2059  0.0294  0.2647  0.5000 -0.7418 -0.5065 -0.2712 -0.0359 -0.7810 -0.5458 -0.3105 -0.0752 -0.7418 -0.5065 -0.2712 -0.0359 -0.7810 -0.5458 -0.3105 -0.0752 -1.3170 -1.0817 -0.8464 -0.6111 -1.3562 -1.1209 -0.8856 -0.6503
        6.    Qj |  0.0000  0.2288  0.1830  0.4118 -0.3268 -0.0980 -0.1438  0.0850 -0.8627 -0.6340 -0.6797 -0.4510 -1.1895 -0.9608 -1.0065 -0.7778 -0.3399 -0.1111 -0.1569  0.0719 -0.6667 -0.4379 -0.4837 -0.2549 -1.2026 -0.9739 -1.0196 -0.7908 -1.5294 -1.3007 -1.3464 -1.1176
        7.    QJ |  0.1667  0.6373  0.5980  1.0686 -0.4477  0.0229 -0.0163  0.4542 -0.9837 -0.5131 -0.5523 -0.0817 -1.5980 -1.1275 -1.1667 -0.6961 -0.9837 -0.5131 -0.5523 -0.0817 -1.5980 -1.1275 -1.1667 -0.6961 -2.1340 -1.6634 -1.7026 -1.2320 -2.7484 -2.2778 -2.3170 -1.8464
        8.   QJj |  0.3333  0.7974  0.4771  0.9412 -0.5686 -0.1046 -0.4248  0.0392 -1.1046 -0.6405 -0.9608 -0.4967 -2.0065 -1.5425 -1.8627 -1.3987 -0.5817 -0.1176 -0.4379  0.0261 -1.4837 -1.0196 -1.3399 -0.8758 -2.0196 -1.5556 -1.8758 -1.4118 -2.9216 -2.4575 -2.7778 -2.3137
        9.     K | -0.1667  0.0686  0.3039  0.5392  0.3039  0.5392  0.7745  1.0098 -0.2059  0.0294  0.2647  0.5000  0.2647  0.5000  0.7353  0.9706 -0.7418 -0.5065 -0.2712 -0.0359 -0.2712 -0.0359  0.1993  0.4346 -0.7810 -0.5458 -0.3105 -0.0752 -0.3105 -0.0752  0.1601  0.3954
       10.    Kj |  0.0000  0.2288  0.1830  0.4118  0.1830  0.4118  0.3660  0.5948 -0.3268 -0.0980 -0.1438  0.0850 -0.1438  0.0850  0.0392  0.2680 -0.3399 -0.1111 -0.1569  0.0719 -0.1569  0.0719  0.0261  0.2549 -0.6667 -0.4379 -0.4837 -0.2549 -0.4837 -0.2549 -0.3007 -0.0719
       11.    KJ |  0.1667  0.6373  0.5980  1.0686  0.0621  0.5327  0.4935  0.9641 -0.4477  0.0229 -0.0163  0.4542 -0.5523 -0.0817 -0.1209  0.3497 -0.9837 -0.5131 -0.5523 -0.0817 -1.0882 -0.6176 -0.6569 -0.1863 -1.5980 -1.1275 -1.1667 -0.6961 -1.7026 -1.2320 -1.2712 -0.8007
       12.   KJj |  0.3333  0.7974  0.4771  0.9412 -0.0588  0.4052  0.0850  0.5490 -0.5686 -0.1046 -0.4248  0.0392 -0.9608 -0.4967 -0.8170 -0.3529 -0.5817 -0.1176 -0.4379  0.0261 -0.9739 -0.5098 -0.8301 -0.3660 -1.4837 -1.0196 -1.3399 -0.8758 -1.8758 -1.4118 -1.7320 -1.2680
       13.    KQ |  0.1667  0.6373  1.1078  1.5784  0.5980  1.0686  1.5392  2.0098 -0.4477  0.0229  0.4935  0.9641 -0.0163  0.4542  0.9248  1.3954 -0.9837 -0.5131 -0.0425  0.4281 -0.5523 -0.0817  0.3889  0.8595 -1.5980 -1.1275 -0.6569 -0.1863 -1.1667 -0.6961 -0.2255  0.2451
       14.   KQj |  0.3333  0.7974  0.9869  1.4510  0.4771  0.9412  1.1307  1.5948 -0.5686 -0.1046  0.0850  0.5490 -0.4248  0.0392  0.2288  0.6928 -0.5817 -0.1176  0.0719  0.5359 -0.4379  0.0261  0.2157  0.6797 -1.4837 -1.0196 -0.8301 -0.3660 -1.3399 -0.8758 -0.6863 -0.2222
       15.   KQJ |  0.5000  1.2059  1.4020  2.1078  0.3562  1.0621  1.2582  1.9641 -0.6895  0.0163  0.2124  0.9183 -0.8333 -0.1275  0.0686  0.7745 -1.2255 -0.5196 -0.3235  0.3824 -1.3693 -0.6634 -0.4673  0.2386 -2.4150 -1.7092 -1.5131 -0.8072 -2.5588 -1.8529 -1.6569 -0.9510
       16.  KQJj |  0.6667  1.3660  1.2810  1.9804  0.2353  0.9346  0.8497  1.5490 -0.8105 -0.1111 -0.1961  0.5033 -1.2418 -0.5425 -0.6275  0.0719 -0.8235 -0.1242 -0.2092  0.4902 -1.2549 -0.5556 -0.6405  0.0588 -2.3007 -1.6013 -1.6863 -0.9869 -2.7320 -2.0327 -2.1176 -1.4183
       17.     A | -0.1667 -0.4542  0.3039  0.0163  0.3039  0.0163  0.7745  0.4869  0.3039  0.0163  0.7745  0.4869  0.7745  0.4869  1.2451  0.9575 -0.2059 -0.4935  0.2647 -0.0229  0.2647 -0.0229  0.7353  0.4477  0.2647 -0.0229  0.7353  0.4477  0.7353  0.4477  1.2059  0.9183
       18.    Aj |  0.0000 -0.2941  0.1830 -0.1111  0.1830 -0.1111  0.3660  0.0719  0.1830 -0.1111  0.3660  0.0719  0.3660  0.0719  0.5490  0.2549  0.1961 -0.0980  0.3791  0.0850  0.3791  0.0850  0.5621  0.2680  0.3791  0.0850  0.5621  0.2680  0.5621  0.2680  0.7451  0.4510
       19.    AJ |  0.1667  0.1144  0.5980  0.5458  0.0621  0.0098  0.4935  0.4412  0.0621  0.0098  0.4935  0.4412 -0.0425 -0.0948  0.3889  0.3366 -0.4477 -0.5000 -0.0163 -0.0686 -0.5523 -0.6046 -0.1209 -0.1732 -0.5523 -0.6046 -0.1209 -0.1732 -0.6569 -0.7092 -0.2255 -0.2778
       20.   AJj |  0.3333  0.2745  0.4771  0.4183 -0.0588 -0.1176  0.0850  0.0261 -0.0588 -0.1176  0.0850  0.0261 -0.4510 -0.5098 -0.3072 -0.3660 -0.0458 -0.1046  0.0980  0.0392 -0.4379 -0.4967 -0.2941 -0.3529 -0.4379 -0.4967 -0.2941 -0.3529 -0.8301 -0.8889 -0.6863 -0.7451
       21.    AQ |  0.1667  0.1144  1.1078  1.0556  0.5980  0.5458  1.5392  1.4869  0.0621  0.0098  1.0033  0.9510  0.4935  0.4412  1.4346  1.3824 -0.4477 -0.5000  0.4935  0.4412 -0.0163 -0.0686  0.9248  0.8725 -0.5523 -0.6046  0.3889  0.3366 -0.1209 -0.1732  0.8203  0.7680
       22.   AQj |  0.3333  0.2745  0.9869  0.9281  0.4771  0.4183  1.1307  1.0719 -0.0588 -0.1176  0.5948  0.5359  0.0850  0.0261  0.7386  0.6797 -0.0458 -0.1046  0.6078  0.5490  0.0980  0.0392  0.7516  0.6928 -0.4379 -0.4967  0.2157  0.1569 -0.2941 -0.3529  0.3595  0.3007
       23.   AQJ |  0.5000  0.6830  1.4020  1.5850  0.3562  0.5392  1.2582  1.4412 -0.1797  0.0033  0.7222  0.9052 -0.3235 -0.1405  0.5784  0.7614 -0.6895 -0.5065  0.2124  0.3954 -0.8333 -0.6503  0.0686  0.2516 -1.3693 -1.1863 -0.4673 -0.2843 -1.5131 -1.3301 -0.6111 -0.4281
       24.  AQJj |  0.6667  0.8431  1.2810  1.4575  0.2353  0.4118  0.8497  1.0261 -0.3007 -0.1242  0.3137  0.4902 -0.7320 -0.5556 -0.1176  0.0588 -0.2876 -0.1111  0.3268  0.5033 -0.7190 -0.5425 -0.1046  0.0719 -1.2549 -1.0784 -0.6405 -0.4641 -1.6863 -1.5098 -1.0719 -0.8954
       25.    AK |  0.1667  0.1144  1.1078  1.0556  1.1078  1.0556  2.0490  1.9967  0.5980  0.5458  1.5392  1.4869  1.5392  1.4869  2.4804  2.4281 -0.4477 -0.5000  0.4935  0.4412  0.4935  0.4412  1.4346  1.3824 -0.0163 -0.0686  0.9248  0.8725  0.9248  0.8725  1.8660  1.8137
       26.   AKj |  0.3333  0.2745  0.9869  0.9281  0.9869  0.9281  1.6405  1.5817  0.4771  0.4183  1.1307  1.0719  1.1307  1.0719  1.7843  1.7255 -0.0458 -0.1046  0.6078  0.5490  0.6078  0.5490  1.2614  1.2026  0.0980  0.0392  0.7516  0.6928  0.7516  0.6928  1.4052  1.3464
       27.   AKJ |  0.5000  0.6830  1.4020  1.5850  0.8660  1.0490  1.7680  1.9510  0.3562  0.5392  1.2582  1.4412  0.7222  0.9052  1.6242  1.8072 -0.6895 -0.5065  0.2124  0.3954 -0.3235 -0.1405  0.5784  0.7614 -0.8333 -0.6503  0.0686  0.2516 -0.4673 -0.2843  0.4346  0.6176
       28.  AKJj |  0.6667  0.8431  1.2810  1.4575  0.7451  0.9216  1.3595  1.5359  0.2353  0.4118  0.8497  1.0261  0.3137  0.4902  0.9281  1.1046 -0.2876 -0.1111  0.3268  0.5033 -0.2092 -0.0327  0.4052  0.5817 -0.7190 -0.5425 -0.1046  0.0719 -0.6405 -0.4641 -0.0261  0.1503
       29.   AKQ |  0.5000  0.6830  1.9118  2.0948  1.4020  1.5850  2.8137  2.9967  0.3562  0.5392  1.7680  1.9510  1.2582  1.4412  2.6699  2.8529 -0.6895 -0.5065  0.7222  0.9052  0.2124  0.3954  1.6242  1.8072 -0.8333 -0.6503  0.5784  0.7614  0.0686  0.2516  1.4804  1.6634
       30.  AKQj |  0.6667  0.8431  1.7908  1.9673  1.2810  1.4575  2.4052  2.5817  0.2353  0.4118  1.3595  1.5359  0.8497  1.0261  1.9739  2.1503 -0.2876 -0.1111  0.8366  1.0131  0.3268  0.5033  1.4510  1.6275 -0.7190 -0.5425  0.4052  0.5817 -0.1046  0.0719  1.0196  1.1961
       31.  AKQJ |  0.8333  1.2516  2.2059  2.6242  1.1601  1.5784  2.5327  2.9510  0.1144  0.5327  1.4869  1.9052  0.4412  0.8595  1.8137  2.2320 -0.9314 -0.5131  0.4412  0.8595 -0.6046 -0.1863  0.7680  1.1863 -1.6503 -1.2320 -0.2778  0.1405 -1.3235 -0.9052  0.0490  0.4673
       32. AKQJj |  1.0000  1.4118  2.0850  2.4967  1.0392  1.4510  2.1242  2.5359 -0.0065  0.4052  1.0784  1.4902  0.0327  0.4444  1.1176  1.5294 -0.5294 -0.1176  0.5556  0.9673 -0.4902 -0.0784  0.5948  1.0065 -1.5359 -1.1242 -0.4510 -0.0392 -1.4967 -1.0850 -0.4118  0.0000


      Нам треба лише переконатися, то на перехресті рядку AKQj та стовпчика AKj розташоване вже обчислене значення -0.542483660131. Йдемо та пересвідчуємося, що відповідний елемент матриці дорівнює -0.5425. Таким чином є шанс, що й цей крок зроблений у вірному напрямку.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Як розв’язуються ігри

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

      З курсу теорії ігор нам відомо, як розв’язувати такі ігри. Є теорема фон Неймана, яка говорить, що для будь якої матричної гри можна побудувати пряму та двоїсту задачі лінійного програмування, де розв’язок першої задачі буде відповідати оптимальній стратегії першого гравця, а розв’язок двоїстої задачі буде відповідати оптимальній стратегії другого гравця. У цьому розділі я просто розповім, як це робиться, не поглиблюючись у математичні докази.

      По-перше, для кожної матричної гри є поняття ціни гри. Це значення, яке у середньому буде вигравати перший гравець, якщо обидва притримуються оптимальної стратегії. Візьмемо, наприклад, шахи. Більшість сильних шахістів схильні вважати, що початкова позиція нічийна. Тобто, якщо гравці не будуть припускатися помилок, то гра повинна закінчитися у нічию. Якщо це так, то ціна шахів це нуль.

      Для нашої гри AKQJj також є ціна, але вона зараз невідома. Оскільки гравці в нерівних умовах, то ціна цієї гри не обов’язково нуль. Вона може буде додатною, тоді перший гравець буде у середньому трохи вигравати. Або від’ємної, тоді вигідніше сидіти на великому блайнді. Проблема у тому, що запропонований метод розв’язку гри працює лише у разі, коли ціна гри додатна. Але це не проблема, ми завжди можемо додати до всіх елементів матриці гри певну константу, щоб не змінюючи гри. Наприклад, у грі AKQJj ми побудували матрицю гри, яка містить виграш першого гравця. Якщо до усіх елементів цієї матриці додати розмір стеку (10), то матриця буде містити кількість фішок першого гравця після гри. Це ніяк не впливає на оптимальну стратегію, але робить ціну гру додатною - стратегія «pass» забезпечить першому гравцю 9.5 фішок у будь якому разі після гри.

      Добре, припустимо що ціна гри додатна. Тоді, якщо A це матриця гри, розмір матриці m×n, де рядки (i=1..m) відповідають стратегіям першого гравця, а стовпчики j=1..n відповідають стратегіям другого гравця. Тоді оптимальну стратегію першого гравця можна отримати з розв’язку задачі

      А оптимальну стратегію другого гравця можна отримати з розв’язку задачу


      Якщо p* та q* це розв’язки даних задач (їх ще називають оптимальними планами), то ймовірності, з якою треба обирати стратегії першому x* та другому y* гравцю дорівнюють

      Це і є оптимальні стратегії для гравців.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Розв’язання AKQJj

      1. Перенос матриці гри до MATLAB.
      Ось й настав час, коли ми можемо розв’язати нашу гру AKQJj. Розв’язати означає знайти оптимальні стратегії. Для цього скористуємося середою MATAB. По-перше, нам треба перенести до MATLAB матрицю гри. Це зробити нескладно, спочатку треба згенеруємо матрицю гри за допомогою нашої програми:
      code:
      $ ./poker-001 -d8 >AKQJj-10-1-½.txt

      А тепер прочитаємо його у MATLAB, та переконаємося, що матриця гри прочитана вірно:
      code:
      >> G = dlmread('/шлях/до/файлу/.../AKQJj-10-1-½.txt');
      >> G(30,26)
      ans =
         -0.5425


      Як і слід очікувати, на перехресті рядку 30 (стратегія AKQj), та стовпчика 26 (стратегія AKj) розташоване обчислене нами значення -0.542483660131.

      2. Гарантуємо, що ціна гри буде додатна.
      Як я і пропонував вище, треба додати розмір стеку до усіх елементів матриці гри. Зробити у MATLAB це дуже просто:
      code:
      >> A = G + 10.0;


      3. Розв’язуємо пряму задачу лінійного програмування.

      Тепер подивимося, які засоби пропонує MATLAB для розв’язання задач лінійного програмування. Це функція linprog, яка знаходиться у наборі інструментів з назвою Optimization Toolbox. Ретельно ознайомимося з документацією. Зазначимо, що функція linprog розв’язує трохи іншу задачу лінійного програмування, яку можна записати у вигляді:




      Нагадаємо, що нам треба розв’язати задачу


      Спробуємо їх порівняти:
      • Знак нерівності треба змінити на протилежний. Це зробити досить легко:
      • Сума у MATLAB йде по другому індексу, а не по першому. Тобто матрицю треба транспонувати.
      • Рівностей у обмеженнях ми не бачимо, так що їх треба пропустити.
      • Треба додати обмеження зверху в умовах. Для цього треба використати спеціальне значення Inf
      .

      Ми готові до розв’язку. Є дві чудові функції ones та zeros, які створююсь матриці різних розмірів, заповнені одиницями та нулями відповідно. Використаємо їх. Також додамо чаклунську строку з вказівкою метода розв’язку. За замовчуванням використовується більш швидкий на великих задачах метод, але трохи менш точний. Уперед!
      code:
      >> f = ones(1,32);
      >> b = -ones(32,1);
      >> lb = zeros(1,32);
      >> ub = Inf * ones(1,32);
      >> options = optimset('Algorithm', 'simplex', 'Simplex', 'on', 'LargeScale', 'off');
      >> [p, fval1] = linprog(f, -A', b, [], [], lb, ub, [], options);
      Optimization terminated.
      >> fval1
      fval1 =
          0.1010
      >> p
      p =
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
          0.0895
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
         -0.0000
               0
               0
          0.0115

      Поздоровляю, щось ми отримали.

      4. Розв’язуємо двоїсту задачу лінійного програмування.

      Для тих, хто хоче спробувати розв’язати самому, сховаю під спойлер

      code:
      >> f = -ones(1,32);
      >> b = ones(32,1);
      >> lb = zeros(1,32);
      >> ub = Inf * ones(1,32);
      >> [q, fval2] = linprog(f, A, b, [], [], lb, ub, [], options);
      Optimization terminated.
      >> fval2
      fval2 =
         -0.1010
      >> q
      q =
         -0.0000
          0.0011
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
          0.0999
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0


      5. Отримуємо оптимальні стратегії

      Тут мають працювати останні дві формули з попереднього запису:


      Обчислюємо:

      code:
      >> C = 1 / fval1 - 10
      C =
         -0.1003
      >> x = p / sum(p)
      x =
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
          0.8864
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
         -0.0000
               0
               0
          0.1136
      >> y = q / sum(q)
      y =
         -0.0000
          0.0114
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
          0.9886
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0
               0


      6. Відповідь

      Ціна гри -0.1. Тобто при правильній грі обох гравців, другий гравець має вигравати у середньому 0.1 блайнда за одну гру
      Оптимальна стратегія першого гравця це вибір між Aj (88.6%), та AKQJj (11.4%).
      Оптимальна стратегія другого гравця це вибір між Aj (98.9%) та j (1.2%).
    • Krab43
      Krab43
      Бронза
      На форуме с: 19.04.2010 Сообщения: 5.265
      а рейк враховуэш в розрахунках?
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Ні, з рейком все трохи складніше. Це все не буде грою з нульової сумою.
    • Krab43
      Krab43
      Бронза
      На форуме с: 19.04.2010 Сообщения: 5.265
      так ніодна гра не проходить без рейка((( рахувати те що не знадобиться для катки думаю не досить умісно((( треба щоб хочаб ми порівну платили рейк з регом мб?
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Якщо цікаво, то я спробую оцінити впливання рейку не прикладі цієї гри. Але після деякої медитації над отриманими результатами. Який рейк брати? 5%?
    • Krab43
      Krab43
      Бронза
      На форуме с: 19.04.2010 Сообщения: 5.265
      я не знаю який рейк в кеші(((
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Будуємо чарти

      Ми отримали, що оптимальна стратегія першого гравця в грі AKQJj це вибір стратегій
      Гравець I:
      Aj - 88.6%
      AKQJj - 11.4%
      Гравець II:
      Aj - 98.9%
      j 1.2%


      Що це означає? Розглянемо на прикладі другого гравця. Це означає, що він має запустити перед грою генератор випадкових чисел, який видає число з інтервалу від нуля до одиниці. Якщо випаде число, більше за 0.012, то він має сказати «call» лише з тузом та джокером. Якщо випадає число, менше за 0.012, то «call» можна казати лише з джокером.

      Але користуватися таким трохи незручно. Спробуємо зробити з цих даних чарт:

      Гравець II
      A - 98.9% «call», 1.2% «fold»
      K - «fold»
      Q - «fold»
      J - «fold»
      j - «call»
      Те ж саме для першого гравця

      Гравець I
      A - «all-in»
      K - 11.4% «all-in», 88.6% «pass»
      Q - 11.4% «all-in», 88.6% «pass»
      J - 11.4% «all-in», 88.6% «pass»
      j - «all-in»
      Цікаво, що в цій грі джокер видався сильнішим за туза, це єдина карта, яка має розігруватися обома гравцями без виключень.

      Далі спробуємо розібратися, який смисл у цих оптимальних стратегіях.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Чому саме валет?

      Чи вас не здивувало, що у отриманій стратегії першого гравця валет грається рівно стільки, скільки й король? Хоча валет слабкіше за короля. Що зміниться, якщо ми будемо розігрувати короля 22.8%, а валет скидати? Це зробить наші руки тільки сильнішими, чому ні?

      Відповідь дає оптимальна стратегія першого гравця. Там немає ні королів, ні дам, ні валетів. Тобто нас влаштує будь яка карта, яка б’є джокер. Валет/король - різниці немає. Якщо з нашої стратегії викреслити валета, але збільшити у два рази розігрування короля, стратегія лишиться оптимальною. Тобто оптимальних стратегій може бути декілька. Як у шахах, до виграшу може призвести декілька ходів.

      Тоді виникає питання, яка з оптимальних стратегій буде неприємніше для суперника. Продовжимо аналогію з шахами. Розглянемо позицію на наступній діаграмі:

      FEN: 8/8/3k4/8/2KB4/8/6r1/4R3 w - - 0 1

      Ця позиція нічийна, будь який хід білих не зможе змінити цю оцінку. Ви зможете переконатися у цьому, якщо використаєте таблиці Налімова, наприклад тут. Припустимо, що ми запустили складний алгоритм, який повертає довільно вибраний оптимальний хід білих. На цій діаграмі це може бути будь який хід. Наприклад, 1. Тe1-e7. З чоловічої точки зору це трохи несподівано. Білі мали певні шанси виграти партію, якщо суперник припуститься помилки у захисті. Замість цього вони віддають туру і мають самі рятуватися точною грою. Але з точки зору комп’ютера що так нічия, що так.

      Повернемося до покеру. При розв’язку гри ми отримали довільно обрану оптимальну стратегію. Одну з множини оптимальних стратегій. Виникає питання, як з цієї множини вибрати найбільш неприємну для людини стратегію? Це досить складне питання. Людину неможливо формалізувати. Спочатку я думав, що краще викинути дам та валетів, а лишите лише 34.2% королів. Ідея зрозуміла, якщо людина буде помилятися та зіграє «call» з королем, то я не програю порівняння. Але після певної кількості ігор суперник зрозуміє, що я граю з джокером та тузом, та нечасто з королем. Тобто казати «call» з королем йому невигідно. У результаті швидко обидва гравці будуть грати майже оптимально. Але якщо інколи грати з валетом, то інколи валет буде бити джокер суперника, що буде доводити його до білого каління. Йому буде здаватися, що він грає з рибою, буде частіше грати з королем щоб піймати нашого валета, інколи це буде йому вдаватися, але у цілому лише збільшить наш виграш. Так що є певні доводи за короля, а є доводи й за валета. Лише експеримент зможе знайти найбільш неприємну для людини оптимальну стратегію.
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Коротко про наступні плани. Другого березня моя дружина з донькою повернуться до Києва, щоб витратити певну суму грошей. Тобто у мене будуть 25 днів, які, за винятком робочого часу, можна буде використати за власним бажанням. Плани великі. Це й медитація на книгою “The joy of the cats”. Це й робота над чорним шаховим репертуаром на 1. e2-e4 (Берлін). Це й написання програми для гри у російські шашки.

      Але обіцяю не забувати про покер. З теорією ігор трохи розібралися. Може гра AKQJj трохи й нагадує покер, але це все ж таки більше полігон для вивчення математики. Так, лишилося ще декілька тем: як буде впливати рейк у цій грі на оптимальні стратегії, порівняння оптимальної стратегії проти неоптимальної, та експлуатаційної. Це цікаві теми, але вони не пов’язані безпосередньо з покером.

      Проглядаючи форум, я знайшов цікаву роздачу, яка мене наштовхнула на низку думок:

      Стек гравців 200BB.
      SB raise 2.5bb
      BB call 2bb

      Flop: А 2 9
      Bank = 6 bb
      SB raise 3 bb, BB call 3bb.

      Turn: А 2 9 5
      Bank = 12bb
      SB raise 6 bb, BB call 6bb.

      River: А 2 9 5 J
      Bank = 24 bb
      SB check
      ??????????
      Я спробую розібрати цю задачу математично. Чесно попереджаю, що з роботами на цю тему я не знайомий. Тобто це буде спроба порахувати з нуля. Також, можливі помилки, так що не треба ідеї відразу перевіряти на практиці. Просто мені подобається трохи напружувати мозок.

      На цій ноті спробую написати низку постів, об’єднаних темою «Гра на рівері». А у фоні має грати наступний кліп AKB48 “River” (公式):
    • iva123
      iva123
      Модератор
      Модератор
      На форуме с: 29.05.2008 Сообщения: 57.126
      Оригинал пользователя mustitz
      Це й медитація на книгою “The joy of the cats”
      А вже є переклад?
    • mustitz
      mustitz
      Бронза
      На форуме с: 07.01.2008 Сообщения: 3.692
      Оригинал пользователя iva123А вже є переклад?
      Ні, я читаю англійською.