Pages

Sunday, August 26, 2012

Poker 2: Hand Evaluator

I am no poker player, but I know the basic rules (Texas Hold'em), having casually played one to one games against the computer on a friend's iPad. In the process I got interested in how the computer evaluates the strength of the hands as in quite a few cases an exhaustive enumeration of all possibilities is very long / impossible and in almost all cases a hand evaluator must be really fast to have any practical value...

So, perusing the internet, I ran into SpecialK's blog and was instantly admirative. His algorithm is so elegant, so simple, and therefore lightning fast, that the next time I blinked, I saw the allegory of speed and elegance combined... The glorious vision was something like this.



And it is so improbably fitting computers architecture (specifically 32 bit integers) that there is almost a divine touch to it...


Ok, after the emotion following the discovery, here is some information.

Thursday, August 23, 2012

Poker 1: Probabilities

By Poker, I mean its most popular variant: Texas Hold'em.

Below is the table enumerating the frequency of 5 card poker hands, sorted in the 9 hand types, assuming cards are randomly drawn from a 52 card deck (obviously without replacement).

The definition of the 9 hand types and the details of the relatively simple computations leading to the results in the table are very well described in Wikipedia.




Sunday, July 8, 2012

The coconut stack, the greedy monkey, and the thieves

I heard this funny small riddle from Sebastian Thrun on their (very good) Udacity A.I. course.

At sunset, p=5 thieves are on a beach next to a large coconut stack guarded by a monkey. The agree to go to sleep, share the coconut stack the next morning and go their different routes.
But they are all distrustful of one each other.

So little time after everybody is silent, but the monkey which does not and will sleep, and seems to be asleep, the first thieve wakes up, go to the coconut stack, take b=1 coconut to give to the monkey (in effect paying for its silence), takes a fraction s/p (s=fraction of a thieve's subjective fair share of the stack, irrespective of the planned sharing on the next morning=1) from the remaining coconuts and go hide it under a palm tree some way from the beach where everybody is lying. This way, ponders the first thieve, I am certain I will at least get my fair share of the coconuts. And on this pleasant thought, he goes back to sleep with the others.

A little later the second thieve wakes up too, unaware of what the first thieve did. He goes the coconut stack, gives b coconut to the monkey, takes a fraction s/p from the remaining coconuts, and go hide it under another palm tree in the neighborhood.

And so on, one by one, all the other thieves wake up, give b coconuts to the monkey, take and hide a fraction s of the remaining coconuts.  As the coconut stack is large - and humans see better in daytime - and they cannot see that the coconut stack is smaller when they approach it at night as it was at sunset.

At dawn all p thieves wake up and give b coconuts to the monkey and equally share the remaining coconuts.

Coconuts cannot be split (without an axe, and even then their water would be lost..)



Questions:
How many coconuts are there in the stack before the night ?
How many coconut each of the thieves will get away with ?