Re: computer-go: Super-Ko

[John Tromp <tromp@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Jul 13, 2001 at 05:16:15PM +0200, Vlad Dumitrescu wrote:
> Hi,
> 
> A sideline question:
> >   oldboards.add(board.zobristHash()) == false
> 
> where can I learn more about this hash function? I remember finding some 
> article, but forgot where. An example implementation would be also nice :-)

here you go:

class Zobrist
{   
  private final Random rand = new Random();
  private Vector zob;
  
  public Zobrist(int capacity)
  { 
    zob = new Vector(capacity);
  }
  
  public void ensure(int newsize)
  { 
    int zsize = zob.size();
    if (newsize > zsize)
    {
      zob.ensureCapacity(newsize);
      while (zsize++ < newsize)
      {
        long pair[] = new long[2];
        for (int i = 0; i < 2; i++)
          pair[i] = rand.nextLong();
        zob.addElement(pair);
      }
      }
    }
  }

  public long hash(int i, int c)   // only allows c=1 or 2
  {
    return ((long [])zob.elementAt(i))[c-1];
  }
}

your board should have some fields like

  final static Zobrist zob = new Zobrist(20*21);
  HashSet oldhashes;
  long hash = 0L;

then whenever you change point i on the board from empty (0) to c (1 or 2)
or back, you do

      hash ^= zob.hash(i,c);

Note that you need to convert these longs to Objects when you store them
in the HashSet, e.g.

oldhashes.add(new Long(hash));

regards,
-John