import SearchEngine from '../SearchEngine' ; import Board from '../../common/Board' ; import Move from '../../common/Move' ; import HistoryHeuristic from '../HistoryHeuristic' ; import { ENTRYTYPE , Item , TranspositionTable } from '../TranspositionTable' ; import { mergeSort } from '../../common/tools' ; export default class IterativeDeepeningNegaScout_TT_HH extends SearchEngine { private TT : TranspositionTable ; private HH : HistoryHeuristic ; constructor ( ) { super ( ) ; this . TT = new TranspositionTable ( 20 ) ; this . HH = new HistoryHeuristic ( ) ; } searchAGoodMove ( board , timeLimit ) { let timeStart = new Date ( ) . getTime ( ) ; console . log ( board . toString ( ) ) ; this . bestMove = null ; this . HH . clear ( ) ; this . TT . hash ( board ) ; this . currentBoard = board . clone ( ) ; let score = this . negascout ( this . maxDepth , this . evaluator . LOST , this . evaluator . WIN ) ; this . setStatus ( score ) ; console . log ( "score:" + score ) ; console . log ( "time:" + ( new Date ( ) . getTime ( ) - timeStart ) . toString ( ) + "ms" ) ; console . log ( "timeLimit:" + timeLimit + "ms" ) ; return this . bestMove ; } private negascout ( depth , alpha , beta ) { let isOwn = ( ( this . maxDepth - depth ) % 2 == 0 ) ; let score = this . quickEvaluate ( this . maxDepth - depth ) ; if ( score != 0 ) return score ; let item = this . TT . lookup ( alpha , beta , depth , isOwn ) ; if ( item != null ) return item . score ; if ( depth <= 0 ) { score = this . evaluator . evaluate ( this . currentBoard ) ; this . TT . update ( ENTRYTYPE . Exact , score , depth , isOwn ) ; return score ; } let possible = this . generator . getPossibleMoves ( this . currentBoard ) ; if ( possible . length == 0 ) { return this . stalemate ( this . maxDepth - depth ) ; } mergeSort ( possible , ( a , b ) => this . HH . get ( a ) > this . HH . get ( b ) ) ; let isFirstNode = true ; let entryType = ENTRYTYPE . UpperBound ; for ( let move of possible ) { let piece = this . currentBoard . at ( move . from ) ; if ( piece == null ) throw Error ( "Invalid Move!" ) ; let target = this . currentBoard . at ( move . to ) ; this . TT . hashMove ( move , piece , target ) ; this . doMove ( move ) ; if ( isFirstNode ) { score = - this . negascout ( depth - 1 , - beta , - alpha ) ; isFirstNode = false ; } else { score = - this . negascout ( depth - 1 , - ( alpha + 1 ) , - alpha ) ; if ( alpha < score && score < beta ) { score = - this . negascout ( depth - 1 , - beta , - score ) ; entryType = ENTRYTYPE . Exact ; } } this . TT . hashUndoMove ( move , piece , target ) ; this . undoMove ( ) ; if ( score > alpha ) { alpha = score ; if ( depth == this . maxDepth ) { this . bestMove = move . clone ( ) ; } } if ( alpha > beta ) { entryType = ENTRYTYPE . LowerBound ; } } this . TT . update ( entryType , alpha , depth , isOwn ) ; if ( this . bestMove != null ) { this . HH . update ( this . bestMove , depth ) ; } return alpha ; } }