Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 11-12-2020, 01:37 AM   #1
Thorware
journeyman
 
Join Date: Apr 2014
Location: Seattle area
Posts: 259
Equilab's mulitway equity algorithm

I am developing an equity calculator and using free Equilab for algorithmic inspiration. I noticed an algorithmic quirk in Equilab that I cannot explain and was hoping you guys might have some ideas.

This is using the "Enumerate all" radio button. Start by setting the first range to a particular hand (eg AsKd) and the second range to "random", then click Evaluate. Notice the instant evaluation time. This is clearly using a precalculated lookup table for heads up preflop equity between various hand groups.

There are two easy ways to make Equilab unable to use this lookup table. One is to set a dead card. If you set one dead card (requires View->Dead cards) and click Evaluate, notice that this takes quite a long time, ~25sec on my machine. This makes sense as Equilab must now iterate all 2million+ possible boards and evaluate the ranges on each one.

However, another way to short circuit the lookup table is to add a 3rd range set to a fixed particular hand, say QhJc. Evaluating this scenario is much faster than with dead cards, taking about one second on my machine. It's clearly doing SOME work (compared to using the lookup table), but it's much faster than calculating with a dead card. Adding the dead card back in slows it to a crawl once again. And of course two dead cards are just as slow.

This does not make sense to me. Naively, calculating equities with two dead cards or with two cards used up in a 3rd range should take essentially the same amount of time since you would have to iterate the same boards and ranges in both situations, and yet we see that with Equilab's implementation, these situations have vastly different performance characteristics. This implies that Equilab is using some algorithmic trickery to speed up enumerating a random range against two fixed hands in some way that becomes invalidated as soon as a dead card is introduced. I suspected some sort of further lookup table scheme that still functions mulitway (indeed, setting any number of remaining seats with fixed hands is still fast), but I can't imagine how such a thing might work. Any ideas?

Another idea is that perhaps the developers were just lazy and did not update the dead card code path along the way, so it is missing some key optimizations that were added to the mainline enumeration path during development. I've noticed some odd bugs and quirks in Equilab, so it wouldn't surprise me if this was the explanation. But if some highly optimized multiway equity algorithm really exists that depends on having no dead cards, I want to know about it!
Thorware is offline   Reply With Quote
Old 11-13-2020, 09:41 PM   #2
Thorware
journeyman
 
Join Date: Apr 2014
Location: Seattle area
Posts: 259
Re: Equilab's mulitway equity algorithm

I finally figured this out after banging my head on it for a couple of days.

I'll just share my conclusions without much of the evidence, since it's a lot of tedious detail. You can message me if you really want to know the particular evidence I found.

When you set dead cards, EquiLab uses an alternate code path. This code path is optimized for many dead cards. This is because with many dead cards, few boards need to be enumerated. With my given heads up example, you start getting reasonable performance at about 20 dead cards set. This is not the design direction I would have taken, but there you have it.

Multiway equities are calculated using board suit isomorphism to drastically reduce the number of boards needed to iterate from preflop by something in the 94-98% range. However, this represents a fixed number of board classes to iterate, and so is not improved by setting dead cards (or indeed cards in fixed hands). Perhaps this is why EquiLab chose to use a different code path when considering dead cards, even though that code path does not use board isomorphism at all and is therefore painfully slower for the common cases of only a few dead cards.

So in conclusion, board isomorphism explains the quick multiway equity performance without lookup tables, and dead cards are simply implemented in an alternate and extremely inefficient code path.
Thorware is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 01:49 PM.


Powered by vBulletin®
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright 2008-2020, Two Plus Two Interactive