0

sorry if I didn't follow the upload rules correctly. This is my first post here. I am currently building a chess engine using C# (Godot game engine), and my transposition table is rarely used. For example, it's only used in 648 out of 29,853 moves. I'm using iterative deepening, null move pruning, move ordering, and killer moves. code:

search.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Runtime.CompilerServices;
using static PieceTable;
using static System.Formats.Asn1.AsnWriter;
public class Search
{
    const int transpositionTableSizeMB = 64;

    List<Moves>[] killerMoves;

    const int immediateMateScore = 100000;
    int depthToSearch;
    public Moves chosenMove;
    public Moves bestMoveThisIteration;
    public MoveGenerator moveGenerator;
   
    private static readonly int[] GamePhases = { 0, 1, 1, 2, 4, 0 };

    public int amountTranspotion = 0;
    public int transpotionStore = 0;
    public static readonly int PAWN_VALUE = 100;
    public static readonly int KNIGHT_VALUE= 3*PAWN_VALUE;
    public static readonly int BISHOP_VALUE = (int)(3.5 * PAWN_VALUE);
    public static readonly int ROOK_VALUE=5*PAWN_VALUE;
    public static readonly int QUEEN_VALUE =9* PAWN_VALUE;
    const int queenEndgameWeight = 45;
    const int rookEndgameWeight = 20;
    const int bishopEndgameWeight = 10;
    const int knightEndgameWeight = 10;
    const int endgameStartWeight = 2 * rookEndgameWeight + 2 * bishopEndgameWeight + 2 * knightEndgameWeight + queenEndgameWeight;
    const int positiveInfinity = 9999999;

    const int milion = 100000;
    const int negativeInfinity = -positiveInfinity;
   public int moveCount = 0;
    public ulong EvulationCount = 0;
    public Board boardToSearch;
    public Moves[] bestMoves;

    public TranspositionTable transpositionTable;

    public Search(int depthToSearch,Board board)
    {

        this.depthToSearch= depthToSearch;
        this.bestMoveThisIteration = Moves.nullMoves;
        this.boardToSearch = board;
        this.moveGenerator = new MoveGenerator();
        this.chosenMove = Moves.nullMoves;

        transpositionTable=new TranspositionTable(board,transpositionTableSizeMB);
        
        bestMoves = new Moves[depthToSearch];
        killerMoves=new List<Moves>[depthToSearch];
        for(int i=0; i<killerMoves.Length; i++)
        {
            killerMoves[i] = new List<Moves>();
        }
       
    }


    public void setBoard (Board board)
    {
        boardToSearch = board;
        transpositionTable.setBoard(board);
    }
    public void itereativeSearch()
    {
        amountTranspotion = 0;
        transpotionStore = 0;


        for (int i=1; i<= depthToSearch; i++)
        {
            negaMax(i, 0);
        }
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int negaMax( int depth, int depthFromRoot,int alpha=negativeInfinity,int beta=positiveInfinity)
    {
        if (depth == 0)
        {
            return evalate(boardToSearch);
        }
        else
        {
           
           int ttVal = transpositionTable.LookupEvaluation(depth, depthFromRoot, alpha, beta);       
            if(ttVal != -1) {
                if ((depthFromRoot) == 0)
                {
                    chosenMove = transpositionTable.TryGetStoredMove();
                }
                amountTranspotion++;
                return ttVal;
            }
            
            
            if (depth >= 3 && !boardToSearch.isCheck)
            {
                int tempEn = boardToSearch.enPassentSquare;
                boardToSearch.enPassentSquare = -1;
                
                boardToSearch.isWhiteTurn = !boardToSearch.isWhiteTurn;
                int cutoffScore = -negaMax(depth - 3, depthFromRoot + 1, -beta, -beta + 1);
                boardToSearch.isWhiteTurn = !boardToSearch.isWhiteTurn;
                boardToSearch.enPassentSquare= tempEn;
                if (cutoffScore >= beta) // If null move failed high, return beta
                    return beta;

            }
            
            

            Moves[] moves = moveGenerator.generateMoves(boardToSearch, false).Result;
           moves= moves.OrderByDescending(move => moveScoreGuess(boardToSearch,move,depthFromRoot)).ToArray(); 
            if (moves.Length == 0)
            {
                if (boardToSearch.isCheck)
                {
                    return int.MinValue;
                }
                else
                {
                    return 0;
                }
            }
            else
            {

                int evalStoreType =TranspositionTable.UpperBound;
                    for (int i = 0; i < moves.Length; i++)
                {

                    moveCount++;
                    bool wasInCheck = boardToSearch.isCheck;
                    Moves move = moves[i];
                    boardToSearch.MakeMove(move);
                    boardToSearch.isWhiteTurn = !boardToSearch.isWhiteTurn;
                    bool isInReduce = i > 5;
                   
                    bool reduced = false;
                    int reduce =0;
                    if (!move.isCapture() && !boardToSearch.isCheck && !wasInCheck && ((depth-1)-depth/3)>=0 &&  depth/3>0 &&  isInReduce)
                    {
                        reduce = depth / 3;
                        reduced=true;
                    }
                    int score = -negaMax( (depth - 1)-reduce, depthFromRoot+1 , -beta,-alpha);
                    if(reduced && score > alpha)
                    {
                         score = -negaMax(depth - 1, depthFromRoot + 1, -beta, -alpha);
                    }
                    boardToSearch.unmakeMove(move);
                    boardToSearch.isWhiteTurn = !boardToSearch.isWhiteTurn;
                    if (score >= beta)
                    {
                        if (!move.isCapture() && !killerMoves[depthFromRoot].Contains(move))
                        {
                            killerMoves[depthFromRoot].Add(move);
                        }
                        transpositionTable.StoreEvaluation(depth, depthFromRoot, beta, TranspositionTable.LowerBound, moves[i]);
                        transpotionStore++;
                        return score;
                    }

                    if (score > alpha)
                    {
                        alpha = score;
                        bestMoves[depthFromRoot] = move; 
                        bestMoveThisIteration = move;
                        if (depthFromRoot==0)
                        {
                            chosenMove = bestMoveThisIteration;
                            evalStoreType = TranspositionTable.Exact;

                        }
                    }
                 
                   

                }
                transpositionTable.StoreEvaluation(depth,  depthFromRoot,alpha, evalStoreType, chosenMove);
                transpotionStore++;
                return alpha; // Return the maximum value after evaluating all moves
            }
        }
    }

    public int evalate(Board boardToSearch)
    {
        

        int whoTurn =boardToSearch.isWhiteTurn ? 1 : -1;
        int whiteMaterial = materialValue(boardToSearch, 0);
        int blackMaterial = materialValue(boardToSearch, 1);
        int whiteEval = whiteMaterial + evulatePieceScores(boardToSearch, Piece.White);
        int whiteBlack = blackMaterial + evulatePieceScores(boardToSearch, Piece.Black);
        return whoTurn * (whiteEval - whiteBlack);

       
    }
    public int materialValue(Board board,int color)
    {
        
        PieceList pawns = board.pieceLists[color][Piece.Pawn - 1];
        PieceList knights = board.pieceLists[color][Piece.Knight - 1];
        PieceList bishops = board.pieceLists[color][Piece.Bishop - 1];
        PieceList rooks = board.pieceLists[color][Piece.Rook - 1];
        PieceList queens = board.pieceLists[color][Piece.Queen - 1];
        int numQueens = queens.Count;
        int numBishops = bishops.Count;
        int numKnights = knights.Count;
        int numRooks = rooks.Count;
        int numPawns = pawns.Count;

        int pawnValue= numPawns * PAWN_VALUE;
        int knightValue = numKnights * KNIGHT_VALUE;
        int bishopValue = numBishops * BISHOP_VALUE;
        int rookValue = numRooks * ROOK_VALUE;
        int queenValue = numQueens * QUEEN_VALUE;
        return pawnValue + knightValue + bishopValue + rookValue + queenValue;
    }


    
   
    public int evulatePieceScores(Board board,int color)
    {
        int sum = 0;
        int colorIndex= color==Piece.White ? 0 : 1;
        PieceList pawns = board.pieceLists[colorIndex][Piece.Pawn-1];
        PieceList knights= board.pieceLists[colorIndex][Piece.Knight - 1];
        PieceList bishops = board.pieceLists[colorIndex][Piece.Bishop - 1];
        PieceList rooks = board.pieceLists[colorIndex][Piece.Rook - 1];
        PieceList queens = board.pieceLists[colorIndex][Piece.Rook - 1];
        int numQueens = queens.Count;
        int numBishops = bishops.Count;
        int numKnights = knights.Count;
        int numRooks = rooks.Count;
        
        int endgameWeightSum = numQueens * queenEndgameWeight + numRooks * rookEndgameWeight + numBishops * bishopEndgameWeight + numKnights * knightEndgameWeight;
        float endgameT = 1 - System.Math.Min(1, endgameWeightSum / (float)endgameStartWeight);
        sum += sumPieceScore(Piece.Pawn,pawns, pawns.Count, endgameT);
        sum += sumPieceScore(Piece.Knight, knights, knights.Count, endgameT);
        sum += sumPieceScore(Piece.Bishop, bishops, bishops.Count, endgameT);
        sum += sumPieceScore(Piece.Rook, rooks, rooks.Count, endgameT);
        sum += sumPieceScore(Piece.Queen, queens, queens.Count, endgameT);

        ulong kingBitboard = board.getPieceBitboard(Piece.King | color);
        int kingSquare = BitboardHelpers.PopLSB( ref kingBitboard);
        sum+= (int)(pieceSquareArray(color | Piece.King, false, kingSquare) * (1 - endgameT));
        sum += (int)(pieceSquareArray(color | Piece.King, true, kingSquare) * (endgameT));


        return sum;
    }

    private int sumPieceScore(int pieceType,PieceList piece, int count, float endgameT)
    {
        int sum = 0;
        for(int i=0; i< count; i++)
        {
            sum += (int)(pieceSquareArray(pieceType, false, piece.occupiedSquares[i])* (1-endgameT));
            sum += (int)(pieceSquareArray(pieceType, true, piece.occupiedSquares[i]) * (endgameT));
        }
        return sum;
    }

  
    public  int moveScoreGuess(Board board,Moves move,int depth)
    {
        if (bestMoves.Contains(move))
        {
            return positiveInfinity;
        }
        if (killerMoves[depth].Contains(move))
        {
            return 8*milion;
        }
        int val = 0;
        int movePiece = board.squares[move.startSquare];
        int movePieceType = Piece.pieceType(movePiece);
        int moveCaptureType = Piece.pieceType( move.capturedPiece);
        if (moveCaptureType != 0)
        {
            val += 10 * (getPieceValue(moveCaptureType) - getPieceValue(movePieceType));
        }
        if (move.isPromotion())
        {
            val += getPieceValue(PiecePromotionType(move));
        }
        if (BitboardHelpers.doesContain(board.pawnAttackMap,move.endSquare)) 
        {
            val -= getPieceValue(movePieceType);
        
        }
        val += getPieceSquareValue(move.endSquare, movePiece, board);
        val-=  getPieceSquareValue(move.startSquare, movePiece, board); 
        return val;

    }

    private  int getPieceSquareValue(int endSquare, int piece, Board board)
    {
        int colorIndex = Piece.isColor(piece,Piece.White)  ? 0 : 1;
        PieceList knights = board.pieceLists[colorIndex][Piece.Knight - 1];
        PieceList bishops = board.pieceLists[colorIndex][Piece.Bishop - 1];
        PieceList rooks = board.pieceLists[colorIndex][Piece.Rook - 1];
        PieceList queens = board.pieceLists[colorIndex][Piece.Rook - 1];
        int numQueens = queens.Count;
        int numBishops = bishops.Count;
        int numKnights = knights.Count;
        int numRooks = rooks.Count;

        int endgameWeightSum = numQueens * queenEndgameWeight + numRooks * rookEndgameWeight + numBishops * bishopEndgameWeight + numKnights * knightEndgameWeight;
        float endgameT = 1 - System.Math.Min(1, endgameWeightSum / (float)endgameStartWeight);

        int earlyGameVal = (int) ((1-endgameT)* pieceSquareArray(piece,false,endSquare));
        int endGameVal = (int)((endgameT) * pieceSquareArray(piece, true, endSquare));
        return earlyGameVal + endGameVal;
    }

    public static int getPieceValue(int pieceType)
    {
            switch (pieceType)
        {
            case Piece.Queen:
                return QUEEN_VALUE;
            case Piece.Rook:
                return ROOK_VALUE;
            case Piece.Knight:
                return KNIGHT_VALUE;
            case Piece.Bishop:
                return BISHOP_VALUE;
            case Piece.Pawn:
                return PAWN_VALUE;
            default:
                return 0;
        }
    }

    public static int PiecePromotionType(Moves move)
    {
       switch(move.flag)
        {
            case MoveFlag.PROMOTETOQUEEN:
                return Piece.Queen;
            case MoveFlag.PROMOTETOBISHOP:
                return Piece.Bishop;
            case MoveFlag.PROMOTETOKNIGHT:
                return Piece.Knight;
            case MoveFlag.PROMOTETOROOK:
                return Piece.Rook;
            default:
                throw new Exception("didn't  find  piece for promotion");

                

            
        }
    }
    public static bool IsMateScore(int score)
    {
        if (score == int.MinValue)
        {
            return false;
        }
        const int maxMateDepth = 1000;
        return Math.Abs(score) > immediateMateScore - maxMateDepth;
    }


}

TranspositionTable.cs

using Godot;
using System;

public  class TranspositionTable 
{

    public const int LookupFailed = -1;

    
    public const int Exact = 0;
    public const int LowerBound = 1;
    public const int UpperBound = 2;

    public Entry[] entries;

    public readonly ulong count;
    public bool enabled = true;
    Board board;
    public TranspositionTable(Board board, int sizeMB)
    {
        this.board = board;

        int ttEntrySizeBytes = System.Runtime.InteropServices.Marshal.SizeOf<Entry>();
        int desiredTableSizeInBytes = sizeMB * 1024 * 1024;
        int numEntries = desiredTableSizeInBytes / ttEntrySizeBytes;

        count = (ulong)(numEntries);
        entries = new Entry[numEntries];
    }
    public ulong Index
    {
        get
        {
            return board.key % count;
        }
    }

    public void setBoard(Board board)
    {
        this.board = board;
    }
    public int LookupEvaluation(int depth, int plyFromRoot, int alpha, int beta)
    {
     
        Entry entry = entries[Index];

        if (entry.key == board.key)
        {
            // Only use stored evaluation if it has been searched to at least the same depth as would be searched now
            if (entry.depth >= depth)
            {
                int correctedScore = CorrectRetrievedMateScore(entry.value, plyFromRoot);
                // We have stored the exact evaluation for this position, so return it
                if (entry.nodeType == Exact)
                {
                    return correctedScore;
                }
                // We have stored the upper bound of the eval for this position. If it's less than alpha then we don't need to
                // search the moves in this position as they won't interest us; otherwise we will have to search to find the exact value
                if (entry.nodeType == UpperBound && correctedScore <= alpha)
                {
                    return correctedScore;
                }
                // We have stored the lower bound of the eval for this position. Only return if it causes a beta cut-off.
                if (entry.nodeType == LowerBound && correctedScore >= beta)
                {
                    return correctedScore;
                }
            }
        }
        return LookupFailed;
    }

    public void StoreEvaluation(int depth, int numPlySearched, int eval, int evalType, Moves move)
    {
        if (!enabled)
        {
            return;
        }
        ulong index = Index;

        //if (depth >= entries[Index].depth) {
        Entry entry = new Entry(board.key, CorrectMateScoreForStorage(eval, numPlySearched), (byte)depth, (byte)evalType, move);
        entries[Index] = entry;
        //}
    }

    int CorrectMateScoreForStorage(int score, int numPlySearched)
    {
        if (Search.IsMateScore(score))
        {
            int sign = System.Math.Sign(score);
            return (score * sign + numPlySearched) * sign;
        }
        return score;
    }

    int CorrectRetrievedMateScore(int score, int numPlySearched)
    {
        if (Search.IsMateScore(score))
        {
            int sign = System.Math.Sign(score);
            return (score * sign - numPlySearched) * sign;
        }
        return score;
    }

    public Entry GetEntry(ulong zobristKey)
    {
        return entries[zobristKey % (ulong)entries.Length];
    }

    public struct Entry
    {

        public readonly ulong key;
        public readonly int value;
        public readonly Moves move;
        public readonly byte depth;
        public readonly byte nodeType;

        //  public readonly byte gamePly;

        public Entry(ulong key, int value, byte depth, byte nodeType, Moves move)
        {
            this.key = key;
            this.value = value;
            this.depth = depth; // depth is how many ply were searched ahead from this position
            this.nodeType = nodeType;
            this.move = move;
        }

        public static int GetSize()
        {
            return System.Runtime.InteropServices.Marshal.SizeOf<Entry>();
        }
    }

    public void Clear()
    {
        for (int i = 0; i < entries.Length; i++)
        {
            entries[i] = new Entry();
        }
 
    }
    public Moves TryGetStoredMove()
    {
        return entries[Index].move;
    }
}

Thanks for any help!

1
  • 1
    You spelled en-passant wrong. Also, have you verified that your Zobrist hashing is completely functional? Another thing, is this copied from chess coding adventure by Sebastian Lague? Commented Apr 15 at 15:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.