How many possible openings are there in the game of chess, if we define an that opening consists of each player making their first 3 moves?
(With one move there are 400 possible openings)
So if one were to program a solution to this...
Define a coordinate on the board (x,y) as (x-1)+8(y-1) - giving us values from 0 to 63.
Ennumerate all the possible pieces from 0 to 31. We can assume that each piece is unique because a pawn cannot make it across the board in 3 moves.
A gamestate therefore can be considered an array from 0 to 31 of integers that can have values from 0 to 64. (64 meaning the piece is captured - it kinda forces us into an extra bit of storage, but since oh well)
We will also associate a "counter" with each gamestate: starting at 0, it will be incremented for each turn taken. (Have it increment for each side: 0 initial, 1 after white move, 2 after black move, etc.)
We will also need to have a queue mechanism able to store GameStates.
The initial GameState (with the pieces properly arranged) is pushed into the queue. Then we go into a loop.
while queue is not empty {
get next GameState from queue;
for every uncaptured Piece in the GameState {
for every legal Move {
if this is GameState is in third turn {
} else {
create newGameState resulting from Move;
increment turn counter on newGameState;
push newGameState into the queue;
}
}
}
}
Of course finding legal moves for a piece may be a bit complicated...
Problems? Analysys? Suggestions?
|
|
Posted by levik
on 2002-10-28 13:26:30 |
Programming
