Re: Game Theory (possibly redundant)
This is a simple deterministic game, a classic AI game tree problem.
Given perfect play in a game like this the player who goes first is destined to win or the player who goes second is destined to win or it's destined to be a tie. The parameters of the game determine who this is.
The most famous of these games is tic-tac-toe. If both players play pefect it will be a tie every game, but not everyone plays perfect (ie retards). You can build a tree showing every possible move/result though.
I will give a simple example.
I say a number 1-3, you say a number 1-3, we keep a running sum and whoever makes the total 5 or more wins.
In this scenario you can build a tree
Player ONE has 3 intial moves: resulting in
1, 2, 3
Player TWO has of couse 3 responses to each of these
2,3,4 3,4,5 4,5,6
As you can see if player ONE selects 1 or 2 as his first choice then player TWO can choose a move leading to a win, thus assuming player TWO plays perfect it's clear player ONE should not choose 2 or 3 initially.
that leaves 2,3,4 going back to player ONE after player TWO's choice.
No matter what of these 3 numbers happen, player ONE may choose a number leading to a win.
This tree is relatively small but it can be clearly seen player 1 is determined to always win if he plays perfectly.
The problem can be inverted such that player 1 always loose
Say if hte total has to be 4 or greater...
We as humans can do these small ones easily, however computers can build these trees in nano-seconds.
So if I said, same number game.....
We go back and forth selecting numbers between 1-62 and first one to make the running sum either divisibile by 100 or totalling greater than or equal to 500 wins.
Now can you play perfect? A computer program can easily build this entire tree in less than a second.
|