Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: OOPS! Shortening Huffman coding + OT

Author: Ratko V Tomic

Date: 11:09:57 11/04/99

Go up one level in this thread


> But IMHO there are two errors in your calculations that
> compensate each other!

Interesting and correct observation. After typing in the initial part of
the message, I took a calculator to recheck the calculations from the input
numbers as appearing on the screen and found I somehow had an extra factor
of 4 for the optimized case (i.e. optimized case now needed 0.05 more bits
than the unoptimizeded one, even though on a scratch paper where partial
calculations were scattered, the encircled final result was 1.95 bits gain).
So, looking at the screen, I somehow convinced myself, after the few seconds
of glancing at the numbers, that I was missing a divisor 2!*2! from the NBP
instead of the NR factor (where they were actually dropped). So I typed in /4
after all those numbers making up the NBP factor, retyped the divided results
and now the final result agreed exactly with the one on paper, shortcircuiting
thus any need for a final common-sense check.

Thanks for pointing this problem out. (I could have lived the rest of my
life with the wrong bishop placement divisor in my head :)


> F =   (N/2)^2 * (N/2-1)^2  /  (N * (N-1) * (N-2) * (N-3)  /  4)

Yes, that (the "factorial effect") is the source of the main part of
the correction.

> Now:  3812256 / 984064 = 3.874 ==> 1.954 bits
>
> The correct calculation must keep into account pawns and therefore it is
> necessary to follow your procedure, but the result is only a little different.

It's interesting how little the pawn effect (+p) changes the result
(reduces the gain):

Gain (+p) = 1.9521
Gain (-p) = 1.9538

So the pawn effect gain reduction is 0.0017 bits, while the gain reduction
due to the factorial effect alone is 0.05 bits (from the 2 bits), i.e. the
pawn effect reduces the gain by only about 3.4% of the factorial effect
(which itself was only 2.5% gain reduction of the 2 bits bishop gain,
which in turn were only 1.5% reduction of the initial 134 bit code size).
Oddly, for me it was the pawn effect which made your initial 2 bit bishop
gain suggestion look overly optimistic.



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.