Здравствуйте дорогие друзья
Итак позицию мы описываем с помощью zobrist ключей.
Для того чтобы хранить эти ключи в таблице или проще говоря в массиве нужна хеш-функция на вход которой подается ключ и на выходе получаем значение (индекс массива), куда положим ключ.
Ясно, что позиций и соответственно ключей будет ну очень много.
А таблица будет ограниченного размера и соответственно для разных ключей можно получить одно и то же значение.
Это называется коллизией.
Простор для экспериментов с разными хеш-функциями широчайший.
Бене на глаза попалась PJW-32 (hashpjw) —хеш-функция , разработанная Питером Вэйнбергером (Peter J. Weinberger).
Zobrist.java
public static int PJWHash(long key,int size)
{
int hash=0;
int test=0;
for (int i = 0; i < 8; i++)
{
hash=(hash<<4)+(byte)(key);
if ((test = hash & 0xf0000000) != 0) {
hash = ((hash ^ (test >>> 24)) & (0xfffffff));
}
key>>>=8;
}
return hash % size;
}
public static void clearTable()
{
for (int i=0;i<MainActivity.TableSize;i++)
{
MainActivity.Table[i]=0L;
}
}
MainActivity.java
...
public static int TableSize=1000000;
public static long[] Table;
public int KeyHash;
public int Collisions=0;
public int Filling=0;
...
case 152:
case 122:
case 132:
case 142:
startGlobalTime1 = System.nanoTime();
depthmov=0L;
desc = MoveGenerator.newPos("8/8/2KQ4/8/8/8/8/7k w");
DescZobKey=Zobrist.returnZobristKeyDesc(desc,ZobristKey,InitZobKey);
number1=0L;
Collisions=0;
Filling=0;
Table=new long[TableSize];
Zobrist.clearTable();
InviolableKing(desc,0,perft);
if (resultGlobalTime2>GlobalTime)
{
showAlert(sInstance,"Внимание!", "Превышено время работы кода",null);
} else
{
resultGlobalTime1 = (double)(System.nanoTime() - startGlobalTime1) / 1000000000;
time_count = resultGlobalTime1 + "сек";
showAlert(sInstance,"Результат", "Число ходов "+depthmov+"\n"+"Коллизии "+Collisions+"\n"+"Заполнено ячеек "+Filling,null);
}
Table=null;
invalidate();
return true;
...
//неприкосновенный король
public long InviolableKing(Desc d,int col,int depth)
...
KeyHash=Zobrist.PJWHash(DescZobKey,TableSize);
if ((Table[KeyHash]!=0L)&(Table[KeyHash]!=MoveZobKey))
{
Collisions++;
}
if (Table[KeyHash]==0L)
{
Table[KeyHash]=MoveZobKey;
Filling++;
}
InviolableKing(dsc,col^1,depth-1);
На самом деле PJW-32 не идеальная функция и число коллизий может достигать несколько тасяч для данного примера.
Число заполнения ячеек массива у меня колебалось от 1316 до 1320.
Над этим моментом нужно поразмыслить.
До встречи.
PS
увеличил массив до 10 миллионов
public int[][] Position=new int[65][65];
Так как белый король не двигается то различных позиций может быть (64-9)*63
Возьмем с избытком 65x65
for (int i=0;i<65;i++)
{
for (int j=0;j<65;j++)
{
Position[i][j]=0;
}
}
Table=new long[TableSize];
Zobrist.clearTable();
...
int sum=0;
for (int i=0;i<65;i++)
{
for (int j=0;j<65;j++)
{
if (Position[i][j]==1)
{
sum++;
}
}
}
showAlert(sInstance,"Результат", "Число ходов "+depthmov+"\n"+"Коллизии "+Collisions+"\n"+"Заполнено ячеек "+Filling+"\n"+"Позиций "+sum,null);
}
...
if (!dsc.mov)
{
for (int j = 0; j < 2; j++)
{
d.WPiece[j]=WP[j];
d.BPiece[j]=BP[j];
}
continue ;
}
x = Long.numberOfLeadingZeros(dsc.BPiece[0]);
y = Long.numberOfLeadingZeros(dsc.WPiece[1]);
Position[x][y]=1;