Здравствуйте дорогие друзья
Таблица перестановок - схема хеширования, ставящая свой целью обнаружение идентичных позиций в различных частях дерева поиска.
Таблица перестановок - безопасна оптимизация, которая может экономить много времени.
Попробуем и мы организовать такую таблицу.
MainActivity.java
public long GlobalTime = 2*3600L;
public int perft = 1;
public long[][][] ZobristKey=new long[12][2][64];
public long MoveZobKey;
public long DescZobKey;
public long InitZobKey;
public static int TableSizeTotal=10000000;
public static int TableSize=TableSizeTotal/4;
public static long[] Table;
public int KeyHash;
public int Collisions=0;
public int Filling=0;
public int TotalMove=0;
public int LevelMove=0;
public int index=0;
public int[][] Position=new int[65][65];
...
protected void onDrawText(Canvas canvas)
...
canvas.drawText("Старт", 566, 292, paint);
canvas.drawText("Save", 566, 352, paint);
...
case 152:
case 122:
case 132:
case 142:
{
writeFile("perft="+perft+"\n",false);
TotalMove=0;
LevelMove=0;
startGlobalTime1 = System.nanoTime();
depthmov=0L;
desc = MoveGenerator.newPos("8/8/2KQ4/8/8/8/8/7k w");
DescZobKey=Zobrist.returnZobristKeyDesc(desc,ZobristKey,InitZobKey);
//number1=DescZobKey;
number1=0L;
Collisions=0;
Filling=0;
for (int i=0;i<65;i++)
{
for (int j=0;j<65;j++)
{
Position[i][j]=0;
}
}
Table=new long[TableSizeTotal];
Zobrist.clearTable();
InviolableKing(desc,0,perft);
if (resultGlobalTime2>GlobalTime)
{
showAlert(sInstance,"Внимание!", "Превышено время работы кода",null);
} else
{
resultGlobalTime1 = (double)(System.nanoTime() - startGlobalTime1) / 1000000000;
time_count = resultGlobalTime1 + "сек";
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,"Размер таблицы "+TableSize, "Кол.листьев дерева "+depthmov+"\n"+"Коллизии "+Collisions+"\n"+"Заполнено ячеек "+Filling+"\n"+"Позиций "+sum,null);
}
writeFile("---\n"+TotalMove,true);
Table=null;
invalidate();
return true;
}
//неприкосновенный король
public int InviolableKing(Desc d,int col,int depth)
{
if (resultGlobalTime2>GlobalTime)
{
return -1;
}
if((depth==0)|(d.BPiece[0]==0)|(d.WPiece[1]==0))
{
return -1;
}
resultGlobalTime2 = (double)(System.nanoTime() - startGlobalTime1) / 1000000000;
// поз короля или ферзя
long pos=0L;
//атаки короля или ферзя
long attak=0L;
//кол-во атак
int nattak=0;
//ход фигуры
long oneMove=0L;
//массивы лля фмгур
long[] WP = new long[2];
long[] BP = new long[2];
long tempZobKey;
int MinMax1=-1;
int x = Long.numberOfLeadingZeros(d.BPiece[0]);
int y = Long.numberOfLeadingZeros(d.WPiece[1]);
//Position[x][y]=1;
if (((x==3)&(y==5))|((x==26)&(y==40)))
{
greatAlert();
showAlertDesc(dsc);
return 0;
}
switch (col)
{
case 0:
{
attak=MoveGenerator.AttakPiece(d,d.WPiece[1],0);
pos=Long.lowestOneBit(d.WPiece[1]);
break;
}
case 1:
{
attak=MoveGenerator.AttakPiece(d,d.BPiece[0],1);
pos=Long.lowestOneBit(d.BPiece[0]);
break;
}
}//switch
nattak=Long.bitCount(attak);
for (int i=0;i<nattak;i++)
{
oneMove=Long.lowestOneBit(attak);
for (int j = 0; j < 2; j++)
{
WP[j] = d.WPiece[j];
BP[j] = d.BPiece[j];
}
tempZobKey=DescZobKey;
MoveGenerator.moveFromTo(d,dsc,pos,oneMove);
attak^=oneMove;
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;
MoveZobKey=Zobrist.returnZobristKeyMove(dsc,ZobristKey,DescZobKey,pos,oneMove,dsc.returnPiece(Long.numberOfLeadingZeros(oneMove)),dsc.Color);
DescZobKey=MoveZobKey;
KeyHash=Zobrist.PJWHash(DescZobKey,TableSize);
if ((Table[KeyHash]!=0L)&(Table[KeyHash]!=MoveZobKey))
{
Collisions++;
}
MinMax1=MinMax(dsc,false);
if (Table[KeyHash]==0L)
{
Table[KeyHash]=MoveZobKey;
Table[KeyHash+TableSize]=oneMove;
Table[KeyHash+2*TableSize]=depth;
Table[KeyHash+3*TableSize]=MinMax1;
Filling++;
}
index=InviolableKing(dsc,col^1,depth-1);
if (depth==1)
{
LevelMove++;
depthmov++;
}
if (depth==perft)
{
writeFile(""+LevelMove+"\n",true);
TotalMove+=LevelMove;
LevelMove=0;
}
for (int j = 0; j < 2; j++)
{
d.WPiece[j]=WP[j];
d.BPiece[j]=BP[j];
}
DescZobKey=tempZobKey;
}//for
return 0;
}
public int MinMax(Desc d,boolean b)
{
int result;
// горизонталь
int n = 0;
// вертикаль
int k = 0;
//позиция короля
long pos = d.BPiece[0];
int Pol = Long.numberOfLeadingZeros(pos);
n = Pol % 8;
k = Pol / 8;
result=12-Math.abs(n+k-3);
if (b)
{
ShowAlert(""+result);
}
return result;
}
Zobrist.java
public static void clearTable()
{
for (int i=0;i<MainActivity.TableSizeTotal;i++)
{
MainActivity.Table[i]=0L;
}
Конечно, это поднимает вопрос о том, какое значение вы храните в элементе хэша и что вы можете сделать с ним при его извлечении.
Еще один из вопросов когда следует перезаписть значение хеш-таблицы, а когда следует оставить прежнее значение.
Давай в шахматы в уме сыграем
— Давай. Пешка Е2 — Е4
— Конь на F6
— Конь B1 — BЗ
— Ты чего? Конь так не ходит (дает подзатыльник).
— Все, молодец, все шахматы рассыпал.
До встречи
