copied from amoung the intersting stuff at http://erikblg.blogspot.com/2007/12/game-theory-and-chess.html
Game theory and chess
I will demonstrate in this posting that neither a person nor a computer needs to do any advanced calculations during chess game in order to win it, or at least force a draw.
1. Players or Colours in a chess game
W= white, B = black
2. Pieces in a chess game
K = king, Q=queen, R=rook, B=bishop, N=knight, P=pawn
3. Locations in a chess game
They go from A1 to H8
4. Situations in a chess game
A situation in a chess game is described by a collection of 3-tuples Situation{(location, colour, piece)}. Empty locations do not appear in the situation. Every possible situation has a unique number, called situationid.
5. Moves in a chess game
A move in a chess game is a collection of 4-tuples Move{(locationFrom,colour,piece,locationTo)}. More than one piece can be moved in one move. That is why a move is a collection. Every possible move has a unique number, called moveid. Note that a move has a colour.
6. Transitions in a chess game
An outgoing transition is a 3-tuple (situation1id, situation2id, moveid), where the colour for moveid, moves a piece from locationFrom to locationTo with which this player pushes the situation from situation1id to situation2id.
For each situation1id, there is a collection of lawful white moves and a collection of lawful black moves, and therefore a collection of lawful {situation2Id}. At the same time, for each situation2id, there is a collection of lawful white moves and a collection of lawful black moves {situation1id} that create situation2id.
7. Situation Payoffs
Each situation in a chess game is a Nash game. The entire chess game is a game of Nash games. The Nash situation player payoffs, consist in one Payoff Status for player White and one Payoff Status for player Black; for the situation.
Each transition in a chess game is a Nash game. The entire chess game is equally well again a game of Nash games. The Nash transition player payoffs, consists in one Payoff Status for player White and one Payoff Status for player Black; for the transition.
8. Player Payoff Status
The Player Payoff Status for the situation or transition is equinash [=] for White, if the best possible chain of transitions for White, countered by the best possible chain of transitions for Black, will lead to a draw for White. Mutatis mutandis for Black.
The Player Payoff Status for the situation or transition is supranash [+] for White, if the best possible chain of transitions for White, countered by the best possible chain of transitions for Black, will lead to a victory for White. Mutatis mutandis for Black.
The Player Payoff Status for the situation or transition is infranash [-] for White, if the best possible chain of transitions for White, countered by the best possible chain of transitions for Black, will lead to a loss for White. Mutatis mutandis for Black.
9. Final Situations
If no transitions are possible out of a particular situationid, the situationid is final. The rules of chess will attribute one of the following three player statuses for the players [White Black] to the final situation: [==] or [-+] or [+-]. Final situations are assumed to always have defined Situation Payoff statuses.
10. Initial and Intermediary Situations
As long as no chain of transitions out of an intermediary situation has reached a final situation, the statuses for the situation remain unknown.
11. Nash Statuses for Incoming Transitions
All incoming transitions adopt the Situation Payoff statuses for the situationid in which they arrive.
12. Nash Statuses for Intermediary Situations
- If at least one outgoing transition from a situationid initiatable by a player is supranash [+], the entire situationid becomes supranash for that player; in other words, if it is that player who is on move in that situation, he will win the game; else;
- If at least one outgoing transition from a situationid initiatable by a player is equinash [=], the entire situationid becomes equinash for that player; in other words, if it is that player who is on move in that situation, the worst outcome from that situation is a draw for him; else;
- If all outgoing transitions from a situationid initiatable by a player are infranash [-], the entire situationid becomes infranash for that player; in other words, whatever that player does in that situation, he will lose unless the other player makes a strategic mistake.
- As long as there are one or more transitions whose status is unknown for that situationid, the situationid cannot be flagged infranash for that player.
13. The database
It is possible to compile a database with all possible situations and all possible transitions out of these situations. Since the rules for chess prevent a chess game to last forever, all games end in a final situation. Working back from that final situation, all transitions can be given Nash statuses. Using the transition statuses, intermediary situations can be given statuses, until the initial situation is given its statuses. Von Neumann proves that the initial chess situation must have the following statuses: [==].
14. Playing
A player cannot make the situation supranash for himself. He must keep chosing between those moves which lead to a next situation in which the other player cannot make any moves that are supranash for the other player. It does not matter which alternative move he choses to make. All moves satisfying that constraint are equivalent. The player can chose randomly between them. The player must wait for the other player to make a move that leads to a situation that is supranash for him. If that happens, the player will win. Otherwise it will be a draw.
15. Two Programs.
One program runs for a long time. It calculates the exhaustive list of situations and possible transitions between these situations, by full enumeration; and uses the final situations to flag all intermediary situations and transitions with their Nash statuses.
One program is lightweight. The user needs to enter the current situation on the chessboard into the program. The program will tell him what the statuses are for that situation, by looking up the situation in the database. The program will look up all outgoing transitions for the player, starting in that situation and the next situation to which the transitions lead. The player must not chose to make any move that will lead to situation that is supranash for the other player. The player will therefore always win or draw.
Any other chess rules, not mentioned in this posting, only affect the lawfulness of an outgoing transition, and must be taken into account when enumerating the complete collection of outgoing transitions for a situation.
If I have time in the future, I will write the programs by myself. Otherwise feel free to implement them by yourself.
lemma 13 opposes your original proposition, namely that one needs not to think in advance, since you propose to evaluate ALL possible moves (transitions) until the end of the game
Your lemma, that there is a calculable nashvalue for each position is at least doubtable. try to ENFORCE any move after the first white one...
Originally posted by Ponderablepaste this type of comments also at the site where the guy who wrote it can see them.
lemma 13 opposes your original proposition, namely that one needs not to think in advance, since you propose to evaluate ALL possible moves (transitions) until the end of the game
Your lemma, that there is a calculable nashvalue for each position is at least doubtable. try to ENFORCE any move after the first white one...