algorithm design techniques passing an extra variablewhich indicates whose turn it is to move this does make the code somewhat less readableso we have stayed with separate routines we leave supporting routines as an exercise the most costly computation is the case where the computer is asked to pick the opening move since at this stage the game is forced drawthe computer selects square total of , positions were examinedand the calculation took few seconds no attempt was made to optimize the code when the computer moves secondthe number of positions examined is , if the human selects the center square , when corner square is selectedand , when noncorner edge square is selected for more complex gamessuch as checkers and chessit is obviously infeasible to search all the way to the terminal nodes in this casewe have to stop the search after certain depth of recursion is reached the nodes where the recursion is stopped become terminal nodes these terminal nodes are evaluated with function that estimates the value of the position for instancein chess programthe evaluation function measures such variables as the relative amount and strength of pieces and positional factors the evaluation function is crucial for successbecause the computer' move selection is based on maximizing this function the best computer chess programs have surprisingly sophisticated evaluation functions neverthelessfor computer chessthe single most important factor seems to be number of moves of look-ahead the program is capable of this is sometimes known as plyit is equal to the depth of the recursion to implement thisan extra parameter is given to the search routines the basic method to increase the look-ahead factor in game programs is to come up with methods that evaluate fewer nodes without losing any information one method which we have already seen is to use table to keep track of all positions that have been evaluated for instancein the course of searching for the first movethe program will examine the positions in figure if the values of the positions are savedthe second occurrence of position need not be recomputedit essentially becomes terminal position the data structure that records this is known as transposition tableit is almost always implemented by hashing in many casesthis can save considerable computation for instancein chess endgamewhere there are relatively few piecesthe time savings can allow search to go several levels deeper pruning - probably the most significant improvement one can obtain in general is known as pruning figure shows the trace of the recursive calls used to evaluate some - hypothetical position in hypothetical game this is commonly referred to as game tree (we have avoided the use of this term until nowbecause it is somewhat misleadingno we numbered the squares starting from the top left and moving right howeverthis is only important for the supporting routines it is estimated that if this search were conducted for chessat least positions would be examined for the first move even if the improvements described later in this section were incorporatedthis number could not be reduced to practical level