I'm currently developing a Chess AI in TypeScript that utilizes negamax with alpha-beta pruning to explore potential moves. The AI incorporates two heuristics: 1) the main heuristic, which assesses leaf nodes during the negamax tree traversal, and 2) a simple yet cost-effective heuristic used for ordering moves to potentially eliminate unnecessary node searches.
In an effort to optimize computation time, I've experimented with implementing a transposition table. While it has significantly reduced processing time, it has also resulted in suboptimal moves being made. I suspect there might be an issue with the implementation of alpha-beta pruning in my code, causing the AI to make incorrect decisions by assuming that certain moves have been pruned. Despite multiple attempts, I am struggling to pinpoint the exact source of the problem. Below is the snippet of the algorithm:
/**
* Depth first search: negamax with a/b pruning
*/
private lookAheadAtMove(
boardState: ChessBoardState,
player: ChessPlayer,
enemy: ChessPlayer,
depthRemaining: number,
alphaPrune: number,
betaPrune: number,
negateMult: number,
transpositionTable: Map<string, iTranspositionTableEntry>
): iLookahedResponse {
// Code snippet here
}
Despite verifying the correctness of the rest of the algorithm, the issues seem to arise only when the transposition table is involved. To address this, I have attempted the following solutions:
- Storing only the heuristic score without additional upperbound/lowerbound types
- Adjusting the mathematical operations for handling negation differently
- Restricting the use of the table to specific depths
- Exchanging "<="" with ">=" in the line that determines whether to utilize the transposition table or not (it should ideally be "<=" to retrieve scores from deeper tree levels, but I tested both scenarios).