import SearchEngine from '../SearchEngine' ; import Board from '../../common/Board' ; import Move from '../../common/Move' ; import { ENTRYTYPE , Item , TranspositionTable } from '../TranspositionTable' ; export default class MTDf extends SearchEngine { private TT : TranspositionTable ; private backupBestMove : Move | null = null ; constructor ( ) { super ( ) ; this . TT = new TranspositionTable ( 20 ) ; } searchAGoodMove ( board , timeLimit ) { let timeCount = ( new Date ( ) ) . getTime ( ) ; this . bestMove = null ; this . TT . hash ( board ) ; this . currentBoard = board . clone ( ) ; let guess = 0 ; let maxDepth = this . maxDepth ; for ( this . maxDepth = 1 ; this . maxDepth <= maxDepth ; this . maxDepth += 1 ) { guess = this . mtdf ( guess , this . maxDepth ) ; } this . setStatus ( guess ) ; console . log ( this . currentBoard . toString ( ) ) ; console . log ( "score:" + guess ) ; console . log ( ( new Date ( ) . getTime ( ) - timeCount ) . toString ( ) + "ms" ) ; console . log ( "time limit:" + timeLimit + "ms" ) ; return this . bestMove ; } private mtdf ( guess , depth ) { let g = guess ; let lowerbound = this . evaluator . LOST ; let upperbound = this . evaluator . WIN ; while ( lowerbound < upperbound ) { if ( this . bestMove != null ) this . backupBestMove = this . bestMove . clone ( ) ; let beta = g ; if ( g == lowerbound ) beta += 1 ; g = this . alphabeta ( depth , beta - 1 , beta ) ; if ( g < beta ) upperbound = g ; else lowerbound = g ; console . log ( "[" + lowerbound + ", " + upperbound + "]" ) ; } return g ; } private alphabeta ( depth , alpha , beta ) { let score = this . quickEvaluate ( this . maxDepth - depth ) ; if ( score != 0 ) return score ; let isOwn = ( this . maxDepth - depth ) % 2 == 0 ; 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 ) ; } let current = this . evaluator . LOST ; 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 ) ; score = - this . alphabeta ( depth - 1 , - beta , - alpha ) ; this . TT . hashUndoMove ( move , piece , target ) ; this . undoMove ( ) ; if ( score > current ) { current = score ; if ( depth === this . maxDepth ) { this . bestMove = move . clone ( ) ; } if ( score > alpha ) { alpha = score ; entryType = ENTRYTYPE . Exact ; } if ( alpha >= beta ) { entryType = ENTRYTYPE . LowerBound ; break ; } } } this . TT . update ( entryType , current , depth , isOwn ) ; return current ; } }