one of the questions I got is as follows;
"Question: The game is called "Vingt-et-un". To set up the game, you write the numbers from 1 to 10 on the blackboard.
There are two players, player A and player B. Player A goes first.
Player A begins the game by crossing out one of the numbers and saying that number out loud.
Then player B crosses out one number at a time, adding up all of the numbers that she crosses out. She continues doing this until the sum of the numbers she has crossed out is GREATER than player A's number. Then it's player A's turn again. Player A crosses out any remaining numbers, adding them to his original number, until his sum is GREATER than player B's sum.
This process continues, each player crossing out more numbers and adding them to his/her total, until that total exceeds the other player's total. The first player to reach or exceed 21 wins.
Here is a sample game:
Player A takes 5.
Player B takes 4.
Player B goes again and takes 9, for a total of 13.
Player A takes 6, for a total of 11.
Player A takes 2, for a total of 13.
Player A takes 8, for a total of 21, and wins.
Question: What is the average branching factor if you wanted to use Minimax to figure out the best move for the first player?
Correct Answer: On average, player A has about 5 choices.
"
Can someone explain to me how this number is derived ? what's the big O notation for it if that's why the "5" came out? and a brief going-through of the proof ?
I would appreciate your help a lot!
Thanks,
|