pseudo code for a chess game

helen_t23
helen_t23 used Ask the Experts™
on
Hi
I would like to know how to write a psudeo code implementation for a chess game.(To make my question
in plain words, if you are writing a program for playing chess like a computer interactive program which plays with a human,
1)how to write like what search you should use like BFS or DFS(depth first search).
2)What datastructure I should go for to track the moves (a stack or a queue)
3)how will i evaluate the possible chouce(like which is the best move)
etc.,
i appreciate your help.

regards
helen
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
To answer your specific questions:
1) I would go DFS, that's how the modern machines (ie Deep Blue/Deep Junior/et al do it).
2) You need a tree not a queue or a stack.  just a simple n-tree (tree in which each node has an arbitrary number of children).  But if you had to pick from the above I'd definately go with a stack.  The first node (or item on the stack) would represent the initial state of the pieces, the second layer would include all the possible moves on the current turn, the next layer down all of the possible reactions to those moves and so on.  In other words the tree gets very big very fast.
3) You would have to come up with an algorithm that suites you.  Exactly what values you assign can vary depending on the style of play the computer should have (from smart to dumb, aggressive to defensive, etc), but the general idea is that you assign each "state" a value based on what the outcome of that turn is.  For instance if you lose your queen you would assign that a low value (say -.9) or if you capture their king you give it a +1 cuz you win. Then the idea is to add up the values of the possible moves (assuming that the opponent is going to make the best possible move each time) and make the one with the most positive outlook.  

It's by no means a trivial thing to do, and there is no "best" algorithm.  Certain styles are better suited to go against others.  Just because A beats B and B beats C doesn't neccesarily mean A will beat C.
Note on the DFS for modern machines.  They use multiple processors, so it's a modified DFS (like each processor might pick a tunnel and start working on it) but a DFS nonetheless.

Commented:
You can find a chess programing tutorial at
http://www.gamedev.net/reference/articles/article1014.asp

/Joachim

Author

Commented:
I was thinking in the same way like you.But I would be happy why did you choose DFS compared to BFS?
thanks
prasanna
I'd go DFS because to really evaluate each level you have to know the potential moves that follow.  If you go BFS you use more memory and don't gain anything.  BFS is good for finding the optimal move, but with chess that doesn't really mean anything.  It doesn't help you because as you're decending the tree you can't really evaluate the top node until you've evaluated all the moves below it.  

I.E. A move that captures the queen is good, but not if it puts you in checkmate the turn.  There is no perfect move, except maybe the one that puts the opponent in checkmate.  

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial