22 November 2010

Open problem

If you have the time to waste, we invite solutions to the following problem:
"Can our algorithm for evaluating 7-card hands be substantially accelerated without increasing the total memory footprint, and/or can the total memory footprint be substantially reduced without slowing the algorithm at all? Or is there another evaluator which is substantially faster with no greater memory footprint or has a substantially smaller memory footprint and is no slower? 
The code must be capable of running on a 32-bit system. All look-up tables must be quick to load prior to evaluation. If we wish to try to quantify all of this, algorithms written in Objective-C, C, C++ or Java that are capable of evaluating 50 million or more randomly generated 7-card hands per second on a top-end early 2010 laptop with a total memory footprint of at most 1Mb, or algorithms that are likewise capable of evaluating say 300 million or more 7-card hands per second with a total memory footprint of at most 10Mb and whose look-up tables (if any) take no more than 5 seconds to load in either case are currently of interest to me. We're particularly interested in reducing the memory footprint."
As far as we're concerned, a 7-card evaluator is formally a (mathematical) function from the set of 7-tuples of pairwise distinct integers modulo 52, such as (0, 51, 4, 12, 8, 16, 20) but not (0, 51, 22, 22, 3, 41, 32), to the natural numbers such that the greater the image, or rank, the better the corresponding Texas Hold'em poker hand and two hands of equal rank always draw. The 7-tuples must not be assumed to be sorted although if you really wish a candidate algorithm is welcome to carry the overhead of sorting its input.

The algorithm may assume that the input is valid, that the responsibility for verifying this rests with the caller. The algorithm must not remember any aspect of its previous evaluations but this is something that can be added at a later stage. The algorithm can be regarded as a block of code, and need not be delayed by making any function or method calls and need not be thread-safe.

All related correspondence, regarding queries and solutions, is welcome here.

No comments:

Post a Comment