imagine game of tic-tac-toe if you go firstyou can make one of nine possible moves your opponent can counter with one of eight possible movesand so on each move leads to another group of choices by your opponentwhich leads to another series of choices for youuntil the last square is filled when you are deciding what move to makeone approach is to mentally imagine movethen your opponent' possible responsesthen your responsesand so on you can decide what to do by seeing which move leads to the best outcome in simple games like tic-tac-toe the number of possible moves is sufficiently limited that it' possible to follow each path to the end of the game after you've analyzed the paths completelyyou know which move to make first this can be represented by graph with one node representing your first movewhich is connected to eight nodes representing your opponent' possible responseseach of which is connected to seven nodes representing your responsesand so on all these paths from the beginning node to an end node include nine nodes for complete analysis you'll need to draw nine graphsone for each starting move even in this simple game the number of paths is surprisingly large if we ignore simplifications from symmetrythere are * * * * * * * * paths in the nine graphs this is factorial ( !or , in game like chess where the number of possible moves is much greatereven the most powerful computers (like ibm' "deep blue"cannot "seeto the end of the game they can only follow path to certain depth and then evaluate the board to see if it appears more favorable than other choices the natural way to examine such situations in computer program is to use depthfirst search at each node you decide what move to make nextas is done in the getadjunvisitedvertex(method in the dfs java program (listing if there are still unvisited nodes (choice points)you push the current one on the stack and go on to the next if you find you can' make move (getadjunvisitedvertex(returns - in certain situationyou backtrack by popping node off the stack (which corresponds to taking back moveand see if the resulting position has any unexplored choices you can think of the sequences of moves in game as treewith nodes representing moves the first move is the root in tic-tac-toeafter the first move there are eight possible second moveseach represented by node connected to the root after each of these eight second movesthere are seven possible third moves represented by nodes connected to the second-move nodes you end up with tree with possible paths from the root to the leaves this is called the game tree actuallythe number of branches in the game tree is reduced because the game is often won before all the squares are filled howeverthe tic-tac-toe game tree is still very large and complexand this is simple game compared with many otherssuch as chess