Programming: Learning how to find optimal strategy in C(++)

Threads: 29
Posts: 5602

Joined: Jul 22, 2014

July 1st, 2015 at 2:01:17 PM permalink

Hey Kalel... I've been programming for over a decade, starting out in C++. It sounds like you should look at a different approach to save yourself hundreds of hours reinventing the wheel. If you want to program basic strategy for blackjack, then all you would need to do is define the rules of the game, then simply program in basic strategy per any given engine. I.E. In your program, if the player has a two card total of 9 and the dealer has an upcard of a 6, you double... You don't need to run the millions of hands simulation to find out that's the answer, it's been done millions of times over by millions of people.

So what my advice would be: Add parameters to your program (game or simulation) to give the user an ability to define the "house rules" such as Stand/Hit soft 17, etc. Then, when they click "Play" or "Simulate" you can reference the proper basic strategy for the rules selected. Again, no need to run millions of hands simulations to find out the best play =P.

If you're just curious about how to find the correct basic strategy, the wizard posted a video of how to do so in excel in about 30 minutes. I'm sure you could translate this to C++ programming if you really wanted to. I'm actually slightly surprised your google (or WoV site search) didn't already turn up code files for basic strategy.

Playing it correctly means you've already won.

RS

Threads: 62
Posts: 8626

Joined: Feb 11, 2014

July 1st, 2015 at 2:10:51 PM permalink

He's interested in programming, not the strategy...

Romes

Threads: 29
Posts: 5602

Joined: Jul 22, 2014

July 1st, 2015 at 2:18:37 PM permalink

Quote: RS
He's interested in programming, not the strategy...

Quote: Kalel
...I have found a couple of articles but still a little confused about how to kick things off. My understanding is that each possible hand needs to simulate each possible decision millions of times to find which decision gives the best outcome,...

Sounds like he's trying to write a program to find basic strategy for every given decision.

Kalel - the best place to start with any programming project is at the foot of the mountain. Take the big task and break it down in to smaller manageable steps. For example, if you wanted to program a blackjack game you'd need to first define the rules. So I'd write a user interface that kicks off the background when the user clicks "play" or "simulate." ...I'm actually finishing (any day lol) my blackjack simulation where I do just this. After defining the house rules you should know the basic strategy, but what comes next? Well, in a real game the house has a shoe of shuffled cards. So I would create a class for a deck, then I would add the number of decks specified by the user to an array or vector. I would call a randomizing function to shuffle each deck and the shoe several times to ensure it's as random as you can make it. Now I have the rules, and the shoe, so then what? Well next comes the players. How many and they must place bets. After the shoe is set, and the bets are placed, you start dealing cards one at a time (popping one off the back end of the vector). This is how you deal cards and can keep track of player hands. Each player could be its own class if you wanted too, with properties such as bet, bankroll, wins/losses/pushes statistics, cards, etc. Find the maximum number of cards any one hand could contain and program that array in to the player class... etc.

Essentially pretend you're at a live casino playing whatever game you want to program and just take it step by step like you would in real life. Break it down and it's much, much easier =).

Playing it correctly means you've already won.

Kalel

https://wizardofodds.com/games/video-poker/methodology/

Threads: 2
Posts: 17

Joined: May 5, 2015

July 1st, 2015 at 2:23:35 PM permalink

Hi Romes,

Thanks for the response, I wasn't aware of that video by Mike so i'll check it out. RS is correct however in that it is the programming I am interested in as opposed to the strategy. I have already had success with coding in a strategy and asking the console to play it out x billion times, but what I want to achieve now is take a game that I essentially may not know anything about, and ask the console to configure the best strategy for me. Essentially what the Wizard does every time he finds a new game!

X~GAMMA(15, 6)

RS

Threads: 62
Posts: 8626

Joined: Feb 11, 2014

July 1st, 2015 at 2:24:37 PM permalink

Romes

Threads: 29
Posts: 5602

Joined: Jul 22, 2014

July 1st, 2015 at 2:27:46 PM permalink

Quote: Kalel
Hi Romes,

Thanks for the response, I wasn't aware of that video by Mike so i'll check it out. RS is correct however in that it is the programming I am interested in as opposed to the strategy. I have already had success with coding in a strategy and asking the console to play it out x billion times, but what I want to achieve now is take a game that I essentially may not know anything about, and ask the console to configure the best strategy for me. Essentially what the Wizard does every time he finds a new game!

Be sure to see my edit above, but to add to what you're referring to there's a couple things. One, almost every game alive has a basic strategy designated for it. So if you're referring to any game then you could of course obtain it. However, for new and very rare games where there isn't one, I'd imagine you would want to do something similar to what mike does in the video I referred to. He takes the player options and runs the math on them to get the expected value (EV). Thus, the option with the highest EV is the most 'correct' play. I think that video will answer some questions you have if you apply the principles of what Mike is doing to what you want to do.

Playing it correctly means you've already won.

Romes

Threads: 29
Posts: 5602

Joined: Jul 22, 2014

July 1st, 2015 at 2:31:13 PM permalink

Here's the video =)

Playing it correctly means you've already won.

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 1st, 2015 at 2:37:42 PM permalink

Thanks very much, it sounds as though this video will answer a lot of questions or at the very least set me on the right path! I have created a similiar outline to what you stated above, in that I have created my playing cards using a class, and then placed them into an array and shuffled them using what I believe is called the Fisher-Yates shuffle.

Blackjack seems like a horrific game to start out with, I thought what I would do is create a simple dice game where there are options to double down maybe, something relatively uncomplicated to get me going!

X~GAMMA(15, 6)

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 1st, 2015 at 2:39:44 PM permalink

Quote: Romes
Here's the video =)

Thanks!

X~GAMMA(15, 6)

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 1st, 2015 at 2:42:00 PM permalink

Quote: RS
https://wizardofodds.com/games/video-poker/methodology/

Thanks!

X~GAMMA(15, 6)

ThatDonGuy

ThatDonGuy

Threads: 117
Posts: 6268

Joined: Jun 22, 2011

July 1st, 2015 at 2:46:37 PM permalink

It depends on the complexity of the game.

For something like 3CP, where there's only one decision point, only two possible choices (as opposed to the 32 in Video Poker - keep all five cards, discard just the first one, discard just the second one,...,discard all but the first one, discard all five), and only six cards involved, going through all the cards shouldn't take too much time to run.

There's a saying in computer science, along the lines of, the hard part isn't doing the coding - the hard part is trying to figure out what exactly to code in the first place.

In the case of 3CP, for each of the three-card player hands - and there are "only" combin(52,3) = 22,100 of them, and not 52 x 51 x 50 = 132,600 - it's easiest to go through all combin(49,3) = 18,424 3-card dealer hands, calculate what you would win (or lose) with each one, add up the amounts, divide by 18,424 to get the "expected" value, and if this is higher than what you would lose if you fold, then you play the hand - otherwise, you fold.
You might find it easier to go through 22,100 3-card dealer hands, then ignore the ones where both hands have the same card.
For example:


int p1, p2, p3, d1, d2, d3;
for (p1 = 2; p1 < 52; p1++)
{
    for (p2 = 1; p2 < p1; p2++)
    {
        for (p3 = 0; p3 < p2; p3++)
        {
            for (d1 = 2; d1 < 52; d1++)
            {
                if (d1 != p1 && d1 != p2 && d1 != p3)
                {
                    for (d2 = 1; d2 < d1; d12+)
                    {
                        if (d2 != p1 && d2 != p2 && d2 != p3)
                        {
                            for (d3 = 0; d3 < 32; d3++)
                            {
                                if (d3 != p1 && d3 != p2 && d3 != p3)
                                {
                                    // p1, p2, p3 are the player's cards
                                    // d1, d2, d3 are the dealer's cards
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

One thing you would have to do is, find a way to convert a three-card hand to a "ranking" of some sort, so you could tell if the player's hand was higher than the dealer's.

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 1st, 2015 at 3:06:29 PM permalink

Quote: ThatDonGuy

One thing you would have to do is, find a way to convert a three-card hand to a "ranking" of some sort, so you could tell if the player's hand was higher than the dealer's.

What I did in my simulation was assign an integer ranking to each possible "made hand". That is, Jack high = 1, Queen high = 2 .... Pair 2s = 5, Pair 3s = 6 etc etc until I had Royal flush as the highest ranking. That way after declaring the decisions all I had to do was


            if(playerhandrank == 1)
            {
                bankroll += loss;
            }

            else if ((playerhandrank > 1) && (dealerhandrank == 0))
            {
                bankroll += win;
            }

            else if ((dealerhandrank > playerhandrank) && (playerhandrank > 1))
            {
                bankroll += loss*2;
            }

            else if ((playerhandrank > dealerhandrank) && (dealerhandrank > 0))
            {
                bankroll += win*2;
            }

            else
            {
                //NO CHANGE
            }

Where 0 was the rank of a no qualify.

Quote: ThatDonGuy
it's easiest to go through all combin(49,3) = 18,424 3-card dealer hands, calculate what you would win (or lose) with each one

I'll be honest reading that scares the hell out of me, how do you go through that many combinations and record the results for each ?!

X~GAMMA(15, 6)

MathExtremist

MathExtremist

Threads: 88
Posts: 6526

Joined: Aug 31, 2010

July 1st, 2015 at 4:12:03 PM permalink

http://web.archive.org/web/20150113045550/http://codingthewheel.com/archives/poker-hand-evaluator-roundup

This will save you months of time.

"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563

ThatDonGuy

ThatDonGuy

Threads: 117
Posts: 6268

Joined: Jun 22, 2011

July 1st, 2015 at 5:06:09 PM permalink

Quote: Kalel
I'll be honest reading that scares the hell out of me, how do you go through that many combinations and record the results for each ?!

Well, for 3-card poker, the hands are ranked Straight Flush, 3 Of A Kind, Straight, Flush, Pair, Other.
If the cards are numbered 0-51, with 0-3 being aces, 4-7 being 2s, 8-11 being 3s, and so on, with 48-51 being kings, and within each group, the numbers mod 0, 1, 2, 3 are spades, hearts, diamonds, clubs, then you can have a function that converts three cards to a ranking value - something like:


int ThreeCardPokerRank (int c1, int c2, int c3)
{
    int[14]  ranks;
    int      flush;
    int      n;
    
    int      r = 0;
    
    /*
        Return values:
        Straight Flush - 5000000 + high card rank (e.g. 5000013 for a Royal Flush)
        3 Of A Kind - 4000000 + card rank (e.g. 5000012 for three Kings)
        Flush - 3000000 + high card rank * 10000 + middle card rank * 100 + low card rank
                (e.g. 3131109 for an A-Q-10 flush)
        Straight - 2000000 + high card rank (e.g. 5000006 for a 7-6-5 straight)
        Pair - 1000000 + pair rank * 100 + third card rank
        Other - high card rank * 10000 + middle card rank * 100 + low card rank
    */
    
    flush = 0;
    if (c1 % 4 == c2 % 4 && c1 % 4 == c3 % 4)
    {
        flush = 1;
    }
    for (n = 0; n < 14; n++)
    {
        ranks[n] = 0;
    }
    ranks[c1 / 4]++;
    ranks[c2 / 4]++;
    ranks[c3 / 4]++;
    // Copy ranks[0] to ranks[13]; it makes checking 32A and AKQ straights easier
    ranks[13] = ranks[0];
    
    // Check for straight / straight flush
    for (n = 13; n >= 2  && (ranks[n] != 1 || ranks[n-1] != 1 || ranks[n-2] != 1); n--);
    // if n >= 2, that is the high card of a straight
    if (n > 2)
    {
        r = 2000000 + n + (3000000 * flush);      
        return r;
    }
    
    // Check for 3 of a kind
    for (n = 1; n <= 13 && ranks[n] != 3; n++);
    if (n <= 13)
    {
        r = 4000000 + n;
        return r;
    }

    // Check for pair
    for (n = 1; n <= 13 && ranks[n] != 1; n++);
    if (n <= 13)
    {
        r = 1000000 + n * 100;
        for (n = 13; n >= 1 && ranks[n] != 1; n--);
        r += n;
        return r;
    }   

    // At this point, either you have a flush, or nothing
    // Get the ranks of the three cards, from highest to lowest
    r = 3000000 * flush;
    for (n = 13; n >= 1 && ranks[n] == 0; n--);
    r += (10000 * n);
    n--;
    while (n >= 1 && ranks[n] == 0)
    {
        n--;
    }
    r += (100 * n);
    n--;
    while (n >= 1 && ranks[n] == 0)
    {
        n--;
    }
    r += n;
    return r;
}

This will return a value for each 3-card hand; each value is greater than all hands that it beats, and less than all hands that beat it.

charliepatrick

charliepatrick

Threads: 39
Posts: 2946

Joined: Jun 17, 2011

July 1st, 2015 at 5:50:59 PM permalink

As has been said, with 3CP it's quite easy to go through all the possible hands the dealer can have using brute force. On the other hand one might say what's the chances of all the different hands (e.g. AKQ sf, KQJ sf etc) - I'm not sure which is easiest, but essentially it's do-able.

However suppose, for simplicity, you are looking at a strange/new Blackjack Game. Personally I'd try out using an infinite deck. But I think the OP wants to go further.

Let's assume the OP already has logic to shuffle decks, deal out cards and, given a known strategy, work out the results for various counts, numbers of decks, penetrations etc. (Indeed that's where I am, but I don't know how to use C++.) Using that logic, assuming you can stick to a fixed strategy, you can look at Baccarat or Blackjack or a simple game - using that to analyse countability etc. The simulation can also estimate, given your preferred counting method, how the House Edge goes up and down and Eliot's profit index.

I'm guessing the OP now wants to go the next step.

How does one evaluate a strategy?
(A) In Blackjack how does one evaluate the correct strategy given ones own cards and the cards that have gone - in other words what is the perfect strategy.
(B) You're trying to analyse a new game or perhaps one of the couple of games currently being discussed on the forum -
(i) https://wizardofvegas.com/forum/gambling/tables/22549-new-table-game-in-dublin-ireland/#post469299
(ii) https://wizardofvegas.com/forum/gambling/blackjack/22454-your-way-blackjack/5/
The strategy isn't obvious - and I guess it is what methods one might try out to determine it.

How often does one have to work it out?
What is the correct method, say whether you hit your 15 vs 10.
(1) Trial and error (presumably this is how computers learn chess, but I don't know how they do it.) - try out both and remember the result. However what do you do when you get an Ace and now get 16? It seems very recursive.
(2a) Evaluate the exact result for each time you see a 15v10 at a count you haven't seen before (essentially you will develop a strategy at each count by working it our once and remembering it for next time - you may even do it for combinations of cards rather than just 15s).
(2b) In 3CP you could work out the strategy (and EV) for every type of hand you see and remember the decision for next time - for instance Qs9c8d is the same as Qh9d8c but not Qs9s8d.
(3) Evaluate it for every hand. Basically similar to above except you always work it out - you'd need a really fast computer, but even so this could take ages and so some short cut is needed.

teliot

Threads: 43
Posts: 2871

Joined: Oct 19, 2009

July 1st, 2015 at 5:58:00 PM permalink

Quote: MathExtremist
http://web.archive.org/web/20150113045550/http://codingthewheel.com/archives/poker-hand-evaluator-roundup

This will save you months of time.

Agree.

Climate Casino: https://climatecasino.net/climate-casino/

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 3rd, 2015 at 10:49:49 AM permalink

Quote: MathExtremist
http://web.archive.org/web/20150113045550

This will save you months of time.

Thank you very much for that link, and thanks to everyone else for there input, I should have enough here to get started. I will bump this thread after trying some stuff out and hopefully be able to recreate some of the results as given by Mike/Eliot/JG.

X~GAMMA(15, 6)

teliot

Threads: 43
Posts: 2871

Joined: Oct 19, 2009

July 3rd, 2015 at 12:03:16 PM permalink

Quote: Kalel
Thank you very much for that link, and thanks to everyone else for there input, I should have enough here to get started. I will bump this thread after trying some stuff out and hopefully be able to recreate some of the results as given by Mike/Eliot/JG.

The poker style games with multiple decision points (UTH, THB, MS) require reverse induction, which is something you shouldn't try and figure out right away. Games with one decision point (like 3CP) are good to start with. Nothing about such games require simulations -- everything is computed exactly by iterating through every possibility. I use simulations for collusion and card counting only. Carnival games, hole-card analysis, edge sorting, baccarat, video poker, slots, etc., are all combinatorial.

The first game I ever did was 3CP (back in 2002). Basic strategy and hole-carding I worked out combinatorially (cpp program), along with simulations for hole-carding RoR. Just take it one game at a time. Each new game you figure out will make the next one easier.

Climate Casino: https://climatecasino.net/climate-casino/

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 3rd, 2015 at 12:14:47 PM permalink

Quote: teliot
The poker style games with multiple decision points (UTH, THB, MS) require reverse induction, which is something you shouldn't try and figure out right away. Games with one decision point (like 3CP) are good to start with. Nothing about such games require simulations -- everything is computed exactly by iterating through every possibility. I use simulations for collusion and card counting only. Carnival games, hole-card analysis, edge sorting, baccarat, video poker, slots, etc., are all combinatorial.

The first game I ever did was 3CP (back in 2002). Basic strategy and hole-carding I worked out combinatorially (cpp program), along with simulations for hole-carding RoR. Just take it one game at a time. Each new game you figure out will make the next one easier.

I'm glad you mentioned avoiding UTH, thats the game I have spent the last week wondering about! I will take your advice and try 3CP first, hopefully to some degree of success. Thus far everything I have played around with has been through simulation only, so i'm looking forward to the fresh challenge.

X~GAMMA(15, 6)

Wizard
Administrator

Wizard

Threads: 1493
Posts: 26489

Joined: Oct 14, 2009

July 3rd, 2015 at 12:32:06 PM permalink

Mississippi Stud would be a good game to try recursive programming on because the number of combinations is in the low millions and it is faster scoring a five-card hand as opposed to seven.

"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)

teliot

Threads: 43
Posts: 2871

Joined: Oct 19, 2009

July 3rd, 2015 at 12:44:14 PM permalink

Quote: Wizard
Mississippi Stud would be a good game to try recursive programming on because the number of combinations is in the low millions and it is faster scoring a five-card hand as opposed to seven.

Agree with your comment about MS. It's pretty fast. I only score the hands once to start the program, then just store that information in an array (or other data structure). My Linux computer has no problem with an integer array score5Hand[52][52][52][52][52]. For 7 card hands, well, things do get a bit slower.

Climate Casino: https://climatecasino.net/climate-casino/

Kalel

Threads: 2
Posts: 17

Joined: May 5, 2015

July 3rd, 2015 at 2:12:03 PM permalink

How do you guys go about scoring hands? For my 3CP simulator I was essentially asking the console to deal out the 3 cards, and then using a lot of 'if' and 'else if' statements, i.e:


//THREE OF A KIND
if((pcard1.value == pcard2.value) && (pcard1.value == pcard3.value))
{
     if(pcard1.value == 2)
     {
         playerrank = 30
     }
    
     else if(pcard1.value == 3)
     {
          playerrank = 31
     }

      .....

}

Not entirely sure whether this is the most efficient way to go about it though to be honest.

X~GAMMA(15, 6)

teliot