To follow up on this thread, I have been playing with
psuedo liberties a bit, and here is my solution.
* I use 2 vectors of values. The first is used for
storing the pseudo liberty values. The second lists has
all 1*, 2*, 3*, and 4* the values, which are sorted.
Binary search will show whether the value is for
a single liberty or not. Division is still a pretty
expensive op. This uses 2 additional memory lookups.
* For liberty values, I use the following equation:
values[i] = 250000000 + (160000 * (i+1)) + ((i+1) * (i+1));
Some bits are constant, some are linear, and some
are quadratic, which guarantees that the sum of
up to 4 values will only be in the set if they
are from the same liberty. I have more confidence
in an equation than in random numbers.
* These numbers are small enough that they fit in
32 bits. Unfortunately they are so large that
the sum of say 20 liberties takes more than 32 bits.
One solution is to use 64 bits for pseudo liberties.
Another solution is keep a count of PLs, and also
a 32 bit unsigned PL value, igoring overflow, and
only check the PL value when the PL count is less
than 5.
-- Michael Wing
// --- code for initializing and checking pseudoliberties ---------------
package go_core_2;
import java.util.Arrays;
public class PseudoLiberties {
public static int values[] = new int[19*19];
public static int possible[] = new int[4*19*19];
static {
for(int i = 0; i < 19 * 19; i++) {
values[i] = 250000000 + (160000 * (i+1)) + ((i+1) *
(i+1));
}
for(int j = 0; j < 4; j++) {
for(int i = 0; i < 19 * 19; i++) {
possible[19 * 19 * j + i] = (j + 1) * values
[i];
}
}
Arrays.sort(PseudoLiberties.possible);
}
public static boolean atari(int liberties) {
int left = 0;
int right = possible.length - 1;
for(;;) {
if(left > right) {
return false;
}
int mid = (left + right) / 2;
if(liberties < possible[mid]) {
right = mid - 1;
continue;
}
if(liberties > possible[mid]) {
left = mid + 1;
continue;
}
return true;
}
}
}
// --- unit test code ---------------------------------------------------
package go_core_2_test;
import go_core_2.PseudoLiberties;
import java.util.Arrays;
import junit.framework.TestCase;
public class PseudoLibertiesTest extends TestCase {
public void testAtariBasic() {
// ensure that everything on the list is true
for(int i = 0; i < PseudoLiberties.values.length; i++) {
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 1));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 2));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 3));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 4));
}
for(int i = 0; i < PseudoLiberties.possible.length; i++) {
assertTrue(PseudoLiberties.atari
(PseudoLiberties.possible[i]));
}
}
public void testAtariIndividuals() {
// ensure that all numbers not on the list are false
boolean problemFound = false;
for(int i = 0; i < 400000000; i++) {
int slot = Arrays.binarySearch
(PseudoLiberties.possible, i);
if(PseudoLiberties.atari(i) != (slot >= 0)) {
System.out.println("pairs failed on " + i);
problemFound = true;
}
}
assertFalse(problemFound);
}
public void testAtariPairs() {
// ensure that all pairs of numbers work
boolean problemFound = false;
for(int i = 0; i < PseudoLiberties.values.length; i++) {
for(int j = 0; j < PseudoLiberties.values.length;
j++) {
int liberties = PseudoLiberties.values[i]
+ PseudoLiberties.values[j];
if(PseudoLiberties.atari(liberties) != (i ==
j)) {
System.out.println("pairs failed
on " + i + "," + j);
problemFound = true;
}
assertTrue(PseudoLiberties.atari(liberties)
== (i == j));
}
}
assertFalse(problemFound);
}
public void testAtariTriplets() {
// ensure that all triplets of numbers work
boolean problemFound = false;
for(int i = 0; i < PseudoLiberties.values.length; i++) {
for(int j = 0; j < PseudoLiberties.values.length;
j++) {
for(int k = 0; k <
PseudoLiberties.values.length; k++) {
int liberties =
PseudoLiberties.values[i]
+
PseudoLiberties.values[j]
+
PseudoLiberties.values[k];
if(PseudoLiberties.atari(liberties) !
= (i == j && j == k)) {
System.out.println("triplets
failed on " + i + "," + j + "," + k);
problemFound = true;
}
assertTrue(PseudoLiberties.atari
(liberties) == (i == j && j == k));
}
}
}
assertFalse(problemFound);
}
public void testAtariFoursomes() {
// ensure that all foursomes of numbers work
boolean problemFound = false;
for(int i = 0; i < PseudoLiberties.values.length; i++) {
System.out.println("loop " + i);
for(int j = 0; j < PseudoLiberties.values.length;
j++) {
for(int k = 0; k <
PseudoLiberties.values.length; k++) {
for(int l = 0; l <
PseudoLiberties.values.length; l++) {
int liberties =
PseudoLiberties.values[i]
+
PseudoLiberties.values[j]
+
PseudoLiberties.values[k]
+
PseudoLiberties.values[l];
if(PseudoLiberties.atari
(liberties) != (i == j && j == k && k == l)) {
System.out.println
("foursomes failed on " + i + "," + j + "," + k + "," + l);
problemFound = true;
}
// assertTrue
(PseudoLiberties.atari(liberties) == (i == j && j == k && k ==l));
}
}
}
}
assertFalse(problemFound);
}
}
> On 11/14/07, Chris Fant <[EMAIL PROTECTED]> wrote:
> > Based on more recent emails, this may not be useful anymore, but I
> > have a list of 361 32-bit numbers that satisfy these properties in
> > case anyone is interested.
>
> I'd be interested in your implementation tricks. Where did the number
> 17 come from?
>
> Other stuff...
>
> John and Jason's optimization suggestions are both good, but they
> point in different directions. (Of course, John had a complete
> solution to begin with.) I have a 64-bit machine, and in that case I
> think that the bitmask approach, with Jason's addition, is the clear
> choice, creating some pretty tight code:
>
> /** @return true iff the input value is either zero or the sum of
> at most mMaxRepetitions of a single code() value. */
> bool operator()(uint64_t codeSum) const {
> return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) &
mMask);
> }
>
> I wrote a class for this that, for lack of a less ugly solution (I
> need to get some more web page space), I have appended to this email.
> There are three files -- a .cpp file, a .hpp file, and another .cpp
> file just for testing and illustrating how to use it. It could use
> more thorough tests and more comments, and the class name is lame, but
> hopefully it works.
>
> #ifndef _IsOneSum_hpp
> #define _IsOneSum_hpp
>
> #include <stdint.h>
> #include <vector>
>
> // Based on ideas of John Tromp, Jason House, and me (Eric Boesch).
>
> class IsOneSum {
> public:
>
> /** @param codeCnt: all inputs to the code() method must be
> strictly less than this value.
>
> @param maxRepetitions: create codes that can be used to detect
> up to maxRepetitions repetitions of the same value. Larger
> numbers of repetitions will not be distinguishable from sums
> of multiple different code values. */
> IsOneSum(int codeCnt, int maxRepetitions);
>
> /** @return true iff the input value is either zero or the sum of
> at most mMaxRepetitions of a single code() value. */
> bool operator()(uint64_t codeSum) const {
> return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) &
mMask);
> }
>
> /** @return the code corresponding to the input value i. */
> uint64_t code(int i) const {
> return mCodes[i];
> }
>
> protected:
> int const mCodeCnt;
> int const mMaxRepetitions;
>
> // These values should be constant too.
> uint64_t mThreshold;
> uint64_t mDivisor;
> uint64_t mMask;
> std::vector<uint64_t> mCodes;
> };
>
> #endif
>
> ----
>
> // IsOneSum.cpp
>
> #include "IsOneSum.hpp"
>
> IsOneSum::IsOneSum(int iCodeCnt, int iMaxRepetitions)
> : mCodeCnt(iCodeCnt), mMaxRepetitions(iMaxRepetitions),
> mCodes(iCodeCnt) {
>
> // Let codeBit equal the least power of two exceeding
> // mMaxRepetitions.
> int codeBitsPerBit = 0;
> int codeBit;
> for (codeBit = 1;
> codeBit <= mMaxRepetitions;
> codeBit<<=1, ++codeBitsPerBit)
> ; // do nothing
>
> // Per Jason House's suggestion, this bottom part of the mask
> // obviates the (codeSum % (codeSum/mDivisor)) == 0 test.
> mMask = codeBit - 1;
>
> for (int bit = 1;
> bit < mCodeCnt;
> bit<<=1, codeBit<<=codeBitsPerBit) {
> // This part of the mask verifies that this
> // base-(1<<codeBitsPerBit) digit of the quotient (codeSum /
> // (codeSum/mDivisor)) equals 0 or 1.
> mMask |= ((1 << codeBitsPerBit) - 2) * codeBit;
> for (int i = 1; i < mCodeCnt; ++i) {
> if (i & bit) {
> mCodes[i] += codeBit;
> }
> }
> }
>
> mDivisor = codeBit;
> for (int i = 0; i < mCodeCnt; ++i) {
> mCodes[i] += mDivisor;
> }
> mThreshold = (mMaxRepetitions + 1) * mDivisor;
> }
>
> ------
>
> // IsOneSumTest.cpp
>
> #include <iostream>
> #include <iomanip>
> #include <stdint.h>
> #include "IsOneSum.hpp"
>
> using namespace std;
>
> int main(int argc, char**argv) {
> IsOneSum is1(361, 4);
>
> cout << hex;
> for (int i = 0; i < 20; ++i) {
> cout << i << " -> " << is1.code(i) << endl;
> }
> cout << 360 << " -> " << is1.code(360) << endl;
>
> uint64_t sum;
> sum = is1.code(1) + is1.code(2) + is1.code(3);
> cout << "1,2,3 -> " << sum << " : " << is1(sum) << endl;
> sum = is1.code(360) + is1.code(360) + is1.code(360);
> cout << "360,360,360 -> " << sum << " : " << is1(sum) << endl;
> sum += is1.code(360);
> cout << "360,360,360,360 -> " << sum << " : " << is1(sum) << endl;
> sum = is1.code(0) + is1.code(0) + is1.code(0) + is1.code(0) + is1.code
(0);
> cout << "0,0,0,0,0 -> " << sum << " : " << is1(sum) << endl;
> }
> _______________________________________________
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
--
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
