Herself’s Artificial Intelligence

All games and all competitions can be represented by trees. Each node represents a place to make a decision, each edge represents a decision that can be made from that node. One of the simplest games we all know is tic-tac-toe. The game tree for tic-tac-toe has an root node with 9 edges. Each edge represents one of the 9 positions you can play if you are player one. The second level of nodes each have 8 edges. Each edge represents one of the remaining 8 positions open to player 2. The paths through the game tree for tic-tac-toe = 9! or 362,880 possible ways to play the game through to completion. So while tic-tac-toe is with in the realm of games the computer can fully solve while playing most games are not. One method used in artificially intelligent games to solve this problem is backward induction.

For example: You get a job transfer to Mars for 10 years. There are two possible jobs on Mars open to your spouse. One job pays $60/year, one job pays $100/year. You know that at the end of 10 years you will both be shipped back to Earth.

A lottery is held every year for the job openings, 1/2 are for the $60/year job, half are for the $100 a year job. Once you commit, that is your job until the trip home. At which point in time should your spouse stop holding out for the $100/year job and take the $60/job?

In year 10 the possibilities are $100/$60/$0 so the $60 job should be accepted.

In year 9 the possibilities are $200 for the $100/year job; $120 for the $60 year job. But if the spouse holds out there is a 50% chance of either. So 50%( $100 + $60 ) = $80. We have then $200/$120/$80. Take the bad job.

In year 8 we have possible earnings of $300/$180 or ( 50% * ($200 + $120 ) = $160 ). The bad job is a better choice than holding out.

In year 7 we have possible earnings of $400/$240 or ( 50% ( $300 + $180 ) = $320 ). Since the $320 is higher than the $240 we should hold out.

In year 6 and earlier it will be better to hold out and hope to do better in next years job lottery, in year 8 on it is better to take either job.

Now there are some big assumptions here. One is that everyone has all the information needed to make the decision. And two that your spouse won’t go stir crazy sitting on Mars with nothing to do. Another assumption which can lead to trouble is that backward induction assumes the players do not collude with each other.

In games you would use the final payoffs for each player to do your backward induction. In business backward induction is commonly used to guess what the competition will do in response to your moves in the market. While backward induction has been very successful in AI and in politics it won’t solve all game tree problems because we don’t always have all the information and there’s more to life than a paycheck.

Papers:
Is good algorithm for computer players also good for human players?