weltyc/ntest — pull request #10 by vladpetric (2014-01-22 04:30:38+00:00)
Title: Massive change to:

a) implement magic multiply within the evaluator.
b) get rid of the pattern state maintained in Pos2, as the evaluator can calculate it efficiently.
c) improve the endgame flipping code as well (convert function array into an array of constants)

Ok, this is getting rid of a lot of code :)

My change comes with a story:

Basically at the beginning of 2013 I was reading a lot of Zebra code and saw that they were creating the pattern indices by chains of multiply by 3 and add. Not particularly efficient ... So I basically try to think of a better way. Believe it or not, I actually came up with magic multiply independently :). I even wrote a blog post about it, only to realize immediately after that that it's been well known, for years really. On the plus side, I got a really good understanding of it.

I added my own implementation of magic multiply - a header file (n64/bitextractor.h) which computes the three quantities via C++ templates (so it's all done at compile time). The template-based code looks ugly - C++ templates and pretty don't go in the same sentence. The resulting code is very efficient though. The macros I use for magic multiply are reasonable, I think: EXTRACT_BITS_U64(quantity, START, COUNT, STEP)

Note that the license I added for bitextractor.h is the 2 clause BSD one (a very permissive license). It's the same one I used on my blog. There's no conflict with GPL, to the best of my knowledge. I can change it to GPL in this place if you prefer just to have the same license throughout.

Regarding the flip code in flips.cpp - I converted it via a python script with regular expressions.

funcre = re.compile(\
"u64 flip([A-H][0-8])\(u64 mover\, u64 enemy\) {\n"
"\s+const int row = ([0-9]);\n"
"\s+const int col = ([0-9]);\n"
"\s*\n"
"\s+u64 flip=0;\n"
"\s*\n"
"\s+const int rowIndex = row0?FlipIndex\((?:row\, )?col\, mover\, enemy\);\n"
"\s+flip \|= rowFlips\[row\]\[rowIndex\];\n"
"(?:\s+const int d9Index = flipIndex\(col\, mover\, enemy\, (0x[0-9a-fA-F]+)\, (0x[0-9a-fA-F]+)\);\n"
"\s+flip \|= d9Flips\[([0-9]+)]\[d9Index\];\n)?"
"\s+const int colIndex = flipIndex\(row\, mover\, enemy\, (0x[0-9a-fA-F]+)\, (0x[0-9a-fA-F]+)\);\n"
"\s+flip \|= colFlips\[col\]\[colIndex\];\n"
"(?:\s+const int d7Index = flipIndex\(col\, mover\, enemy\, (0x[0-9a-fA-F]+)\, (0x[0-9a-fA-F]+)\);\n"
"\s+flip \|= d7Flips\[([0-9]+)]\[d7Index\];\n)?"
"\s*\n"
"\s+return flip;\n"
"}"
, re.MULTILINE)

with open("/home/vlad/pet/ntest/src/n64/flips.cpp", "r+") as f:
data = f.read()
prev = -1
print("struct {\n"
"uint64_t d9mask,\n"
"uint64_t d9mult,\n"
"uint64_t colmask,\n"
"uint64_t colmult,\n"
"uint64_t d7mask,\n"
"uint64_t d7mult,\n"
"uint8_t d9b,\n"
"uint8_t d7b} flipArray[64] = {")
for match in re.findall(funcre, data):
(identifier, row, col, d9mask, d9mult, d9b, colMask, colMult, d7mask, d7mult, d7b) = match
if d9mask == "":
assert d9mult == "" and d9b == ""
d9mask = "0"
d9mult = "0"
d9b = "11"
if d7mask == "":
assert d7mult == "" and d7b == ""
d7mask = "0"
d7mult = "0"
d7b = "11"
assert identifier == chr(ord('A') + int(row)) + col
prev += 1
assert int(row) * 8 + int(col) == prev
print("{", d9mask + "ULL, ", d9mult + "ULL, ", colMask + "ULL, ", colMult + "ULL, ",
d7mask + "ULL, ", d7mult + "ULL, ", d9b + ", ", d7b, "},")