Software update with new split EVs

ericfarmer said:

With a lot of useful input from Colin, I am working on revising my CA to (1) provide more options, and (2) be more accurate with splits. As an initial step in that direction, I have an updated release in the usual locations:

1. A zip archive with pre-compiled executables for Windows on my web site:
https://sites.google.com/site/erfarmer/downloads

2. The latest 5.3 tag of the code repository at:
https://bitbucket.org/possiblywrong/blackjack/

The most visible change to most of you is the option in the strategy calculator to compute split EVs allowing strategy to differ "post-split". (See the first few posts in this recent thread: http://www.blackjackinfo.com/bb/showthread.php?t=22385) Years ago I had provided code snippets that you could plug in to do this, but it is now a more easily configurable run-time option.

You can now more easily generate split EVs that agree with other reference sources (Cacarulo, etc.)-- at least for no resplitting; that is my next project . (I seem to be in the minority with the opinion that "pre-split" is still an interesting and more practically realizable specification of strategy... that is actually slightly more of a pain to compute. But I left both in as options, so you can choose what you like.)

There are other changes that are probably less immediately interesting, such as configuring the payoff for blackjack (previously hard-wired at 3:2), and more cleanly specifying "mixed" strategies that are a combination of things like "always stand on 10,2" and "do whatever maximizes EV." I also did a more thorough code review after Colin had identified several potential divide-by-zero bugs for "pathological" shoes.

Click to expand...

k_c said:

When I cd to files on my computer and try hg clone... I get the following - 'hg' is not recognized as an internal or external command,
operable program or batch file.

I don't know how to make the files downloadable to others.

Click to expand...

k_c said:

I made some changes to Eric's version 5.3 to compute resplits more accurately using the program's existing "pre-split" fixed strategy. The method I used is recursive and is pretty accurate. It gives marginally different results than the method I presently use in my programs but it is close enough that there appears to be virtually no difference in the overall EVs generated by using the fixed "pre-split strategy.

Click to expand...

iCountNTrack said:

I know it looks pathetic when compared to MGP's CA, but it does have a couple of extra things mainly calculating probabilities of the net outcome on the round, variance on the round, and ev calculations using post-split optimal strategies.
for 3 splits ( split to 4 hands) it runs really slow for a full deck, it will take 2-3 days of computational time if your computer is robust enough to handle it, 2 splits (split to 3 hands) are calculated within 1-2 hours with a moderately powerful computer. You can also deplete the deck to half or less for faster results.


I am working on a faster multi-threaded version to get some reasonable execution time.
the code was compiled with VS 2010 so you might get an error about some missing libraries. Best is to install Microsoft Visual C++ 2010 Redistributable Package (x86)
http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=5555

PM me for password to open rar file.
(Dead link: http://www.mediafire.com/?9gi0nqb0jjq9b3i)
Cheers,

ICNT

Click to expand...

# pragma omp parallel for // create a parallel for loop over all features
for (int f = 0; f < F; ++f)
{
     // do some stuff in parallel

    # pragma omp critical
    {
         // write to a shared variable which can't be done in parallel
    }
}

#include <omp.h>
int main(int argc, char *argv[])
{
	#pragma omp parallel
	{
		printf("Hello from thread %d (%d total)\n", omp_get_thread_num(), omp_get_num_threads());
        }
}

assume_R said:

Some tips:

You can make multithreading really easy by using omp. For example, here is a "for" loop which is now parallelized:

Code:

# pragma omp parallel for // create a parallel for loop over all features
for (int f = 0; f < F; ++f)
{
     // do some stuff in parallel

    # pragma omp critical
    {
         // write to a shared variable which can't be done in parallel
    }
}

Then, you compile it using the openmp option, which is /openmp by the command line, or in Configuration Properties --> C/C++ --> Language

You can test it using the following code:

Code:

#include <omp.h>
int main(int argc, char *argv[])
{
	#pragma omp parallel
	{
		printf("Hello from thread %d (%d total)\n", omp_get_thread_num(), omp_get_num_threads());
        }
}

Finally, my other tip, is if you don't want people to have to download the redistributable, just compile your program with the visual studio static libraries. This can be done using the /Mt command line switch, or by changin Configuration Properties --> C/C++ --> Runtime Library from "Multi-threaded DLL" to "Multi-threaded"

Click to expand...

iCountNTrack said:

Thanks for the tips mostly the first one, it makes multithreading looks so simple, the example with the for loop is exactly what i am working on, that is the only way i can see an easy application of multithreading, so instead of running the outermost loops(that deal the first card) sequentially, I will do it in parallel. Thanks very much.

Click to expand...

for (int i = 0; i < 20; ++i)
{
  for (int j = 0; j < 1000; ++j)
  {
     // do something
  }
}

assume_R said:

You're welcome. Just an FYI multithreading works best the more "outer" your threaded loop is.

If you have this:

Code:

for (int i = 0; i < 20; ++i)
{
  for (int j = 0; j < 1000; ++j)
  {
     // do something
  }
}

It is much better to parallelize the outer loop. This is a silly, obvious, example, but in general just try very hard to parallelize as outside your logic you can. This way the inside of your logic can just fly through the CPU without the overhead of starting new threads too often.

As for the second tip, with the way compilers (especially Visual Studio) can really trim down file size, and the way that data storage these days is so cheap, I find compiling as many libraries into my program statically as I can (including the runtimes, as well as external libraries). In the old days, it was much more important to use shared libraries to cut down on file size, but these days I find it so much more of a hassle dealing with dependencies (and versions, conflicts, etc. etc.) than just turning my 2 MB executable into a 10 MB executable with no worries about dependencies. Just my personal preference.

Click to expand...

MGP said:

Glad it's helping. I really wish the split values from the old BJMath would disappear. Cacarulo and I got the exact values (he beat me by a hair) after a discussion started there and Cacarulo had them published in BJA3. The old values only cause confusion.

Click to expand...

iCountNTrack said:

BTW i remember you mentioning once that the pre-increment operator is faster than the post-increment operator is this true, shouldnt the compiler automatically optimize that?

Click to expand...

int I = 5;
for (int i = 0, j = 0; i < I; j = ++i)
    printf("%d\n", j);
printf("\n");
for (int i = 0, j = 0; i < I; j = i++)
    printf("%d\n", j);

assume_R said:

The difference is that with the post-increment, a temporary may be created.

Click to expand...

London Colin said:

And I guess the subtle point is that a compiler cannot optimize this away for a non-primitive type, because there is no guarantee that the overloaded pre- and post-increment operators both have exactly the same semantics (aside from the pre and post-ness of them), though it would be poor programming practice for them not to have.

Click to expand...

// Timer was shown to me by Eric Farmer
#include <ctime>
struct Timer
{
    Timer(double& elapsed) : elapsed(elapsed), tic(std::clock()) {}
    ~Timer()
    {
        elapsed = static_cast<double>(std::clock() - tic) / CLOCKS_PER_SEC;
    }
    double& elapsed;
    std::clock_t tic;
};

int main(int argc, char* argv)
{

	double elapsed = 0, temp;
	const int I = 2000, J = 2000, K = 3000;
	printf("Post-increment...");
	{
		Timer t(elapsed);
		for (int i = 0; i != I; i++)
			for (int j = 0; j != J; j++)
				for (int k = 0; k != K; k++)
					temp = i + j + k;
	}
	printf("done in %f seconds.\n%d\n", elapsed, temp);

	elapsed = 0;
	printf("Pre-increment...");
	{
		Timer t(elapsed);
		for (int i = 0; i != I; ++i)
			for (int j = 0; j != J; ++j)
				for (int k = 0; k != K; ++k)
					temp = i + j + k;
	}
	printf("done in %f seconds.\n%d\n", elapsed, temp);
}

assume_R said:

Yeah, that sounds like another reason the compiler can't optimize it.

Click to expand...

assume_R said:

But even with primitive types, it doesn't optimize the post-increment, but with int's, the creation of a temporary int takes almost no time.

However, we can see how it can change the efficiency of a program on a large scale:

....

Result:

So with 2000 * 2000 * 3000 = 12 billion operations, pre-increment of "int" saved 1.7 seconds.

Click to expand...

... based on this quick experiment, there is no difference between pre-increment and post-increment for int types when using the Visual Studio 2008 C++ compiler with optimizations enabled or disabled.

Click to expand...

assume_R said:

Some tips:

You can make multithreading really easy by using omp. For example, here is a "for" loop which is now parallelized:

Code:

# pragma omp parallel for // create a parallel for loop over all features
for (int f = 0; f < F; ++f)
{
     // do some stuff in parallel

    # pragma omp critical
    {
         // write to a shared variable which can't be done in parallel
    }
}

Click to expand...

London Colin said:

Thanks for posting about this. I hadn't come across OpenMP before.

I have a question, though. How is the assignment of threads to processor cores managed by default?

For this sort of for-loop example I guess we ideally want just one thread executing per core, with tasks (i.e. the loop iterations) being assigned to each thread as they become free.

What I mean is if we parallelize a 1-to-10 loop on a dual-core machine we wouldn't really want five threads kicked off on each, since the execution times of each loop iteration might vary considerably, meaning one core might run out of things to do while the other is still busy. (Moreover, with a triple-core, there would have to be an unequal number of threads assigned to each.)

I had a brief look at the specs at http://openmp.org/wp/openmp-specifications/ and at Wikipedia http://en.wikipedia.org/wiki/OpenMP. It looks like you might be able to explicitly control this kind of thing, but I couldn't really get an overview; there's a lot of detail to wade through.

On the same theme, it looks like maybe on a single-core machine, unless you build against a 'stub' version of OpenMP which does nothing, you may end up with a multithreaded loop that might actually execute a bit more slowly than the sequential version, thanks to the overheads that omp must add.

Click to expand...

London Colin said:

On the same theme, it looks like maybe on a single-core machine, unless you build against a 'stub' version of OpenMP which does nothing, you may end up with a multithreaded loop that might actually execute a bit more slowly than the sequential version, thanks to the overheads that omp must add.

Click to expand...

assume_R said:

If you look at my "Hello world" example, you can try it out.

But essentially it defaults to the number of cores (including hyperthreaded virtual cores!) available on the machine.

I'm not actually sure if that's computed runtime or compile-time (but I would assume runtime, but you should try out the hello world program on different machines to confirm). You can specify it yourself though if you want by using the omp_set_num_threads(int) function in the omp.h file.

Click to expand...

assume_R said:

Eh, I'm not actually even sure that's true. Let's say you load up 3 threads on a single core machine. And your machine has 1000 other threads running. Now, you are using 3/1003 of the processing power instead of 1/1001 . But I'm not sure that would make any difference, especially with the overhead.

Click to expand...