bug-gnubg
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Bug-gnubg] PositionKey. Can we think of something better?


From: Øystein Johansen
Subject: [Bug-gnubg] PositionKey. Can we think of something better?
Date: Thu, 27 Aug 2009 10:46:26 +0200

Hi, Jon and others.

I see your changes to PositionKey and it is indeed an speed improvement. However, I've done some profiling, and to me it seems like PositionKey is still the bottleneck when constructing the movelist. Then I think to my self: Is it possible to get rid of key, of define an other key that can be constructed faster? I think it will speed up many common operations in GNU Backgammon, not just the playing and rollouts, but also importing, analysing and deeper ply searches.

Pros and Cons for the PositionKey:

Pros: It's small (only 80 bit) and takes a small amount of memory. It's uniqe (not a hash) so it can be used both ways board<->key. It can easily be converted into a string (and back) with base64 (Well that applies for any key we may use.) and this has been a standard for many years now.

Cons: It's really slow to calculate! It's also really slow calculating back to board from the key. The size does not fit into a whole number of 32-bit registers, (nor 64-bit registers nor 128-bit registers), which makes it harder to bit operations on it. It is also "static", in the way that you can not move checkers in the key. You must follow the key->board->apply_move->board->key line to make a move based on a key. It is also unusable for calculating any of the neural network inputs, which is the slow part of our evaluator.

My question is: Can we think of something better?

Just to clearify: The Position ID (or gnubg ID as it's called now) can be kept as a interfacing string, even if we find a better key for the board.

-Øystein


reply via email to

[Prev in Thread] Current Thread [Next in Thread]