the aalgorithm finds an optimal solution in this example because it gives up on two paths that are getting too long according to the heuristic plus total cost so far of course the optimality of the solution depends on the heuristic and the total cost for instancethe heuristic should be good enough to return as the cost of getting from the goal to the goal the heuristic cannot over-estimate the cost of getting to the goal from the current node the aalgorithm was used to solve problem in the infinite mario ai competition in this competition programmers from around the world were given the task of writing code that would guide mario through programmable version of the nintendo game mario brothers the idea was that machine learning techniques would be employed to teach mario to make good decisions while navigating the game' world instead of using machine learningrobin baumgarten solved the problem of getting mario through the game by implementing the aalgorithm in robin' solution mario makes choices based on the path length so far plus heuristically computed cost to get to the goal the aimplementation solved the problem and was hit on the internet you can read more about robin' solution and how he developed it at aigamedev com/open/interviews/mario-ai minimax revisited in chap tictactoe was presented as demonstration of two dimensional arrays the outline of the minimax algorithm was presented the minimax algorithm is used by computer games to provide computer opponent minimax only applies in two person games of what is called perfect information these are games where everyone can see everything poker is not game of perfect information tic tac toe is game of perfect information the game of tic tac toe is small enough that adults can generally look far enough ahead so they never loseunless they make careless mistake children on the other hand sometimes can' get enoughif you don' have children or younger brothers and sisterssomeday you will understand tic tac toe is also small enough to be solvable by computer the minimax algorithm can play the game to its conclusion to insure that it never losesjust like an adult the game of connect four is bit different in this gameblack and red checkers are dropped down slots in vertically positioned board the board is seven checkers wide by six checkers tall checkers always drop as far down as possible so there are at most seven choices at each turn in the game the goal is to get four of your checkers in rowa columnor on diagonal in fig the computer has won with the four black checkers on the diagonal playing connect four is not as easy as playing tic tac toe with branching factor of approximately seven at each turnthe number of possible boards quickly grows past what can be considered exhaustively in reasonable amount of time in these situations heuristic must be added to the minimax algorithm to cut off the search the algorithm is not repeated here see sect for complete description of the this copy belongs to 'acha