the analysis of the algorithm involves two factors suppose lines to and to are never executed we can maintain as balanced binary search (or splaytree (this would require code modificationof courseif we never backtrackthere are at most ( operations involving dsuch as deletion and the contains implied at lines and this claim is obvious for deletionssince has ( elements and no element is ever reinserted each call to place uses at most containsand since place never backtracks in this analysisthere can be at most contains thusif there is no backtrackingthe running time is ( log nof coursebacktracking happensand if it happens repeatedlythen the performance of the algorithm is affected this can be forced to happen by construction of pathological case experiments have shown that if the points have integer coordinates distributed uniformly and randomly from [ dmax ]where dmax ( )thenalmost certainlyat most one backtrack is performed during the entire algorithm games as our last applicationwe will consider the strategy that computer might use to play strategic gamesuch as checkers or chess we will useas an examplethe much simpler game of tic-tac-toebecause it makes the points easier to illustrate tic-tac-toe is draw if both sides play optimally by performing careful case-by-case analysisit is not difficult matter to construct an algorithm that never loses and always wins when presented the opportunity this can be donebecause certain positions are known traps and can be handled by lookup table other strategiessuch as taking the center square when it is availablemake the analysis simpler if this is donethen by using table we can always choose move based only on the current position of coursethis strategy requires the programmerand not the computerto do most of the thinking minimax strategy the more general strategy is to use an evaluation function to quantify the "goodnessof position position that is win for computer might get the value of + draw could get and position that the computer has lost would get - position for which this assignment can be determined by examining the board is known as terminal position if position is not terminalthe value of the position is determined by recursively assuming optimal play by both sides this is known as minimax strategybecause one player (the humanis trying to minimize the value of the positionwhile the other player (the computeris trying to maximize it successor position of is any positionps that is reachable from by playing one move if the computer is to move when in some positionpit recursively evaluates the value of all the successor positions the computer chooses the move with the largest valuethis is the value of to evaluate any successor positionps all of ps ' successors are recursively evaluatedand the smallest value is chosen this smallest value represents the most favorable reply for the human player the code in figure makes the computer' strategy more clear lines to evaluate immediate wins or draws if neither of these cases applythen the position is nonterminal recalling that value should contain the maximum of all possible successor