Chess

[Teddybare]

I need some ideas on how a chess game is programmed.

Thanks in advance,
Ted

[GuOddian]

In all honesty it doesn't appear that your question has anything to do with C++ directly as programming a chess game doesn't require any particular language. I would suggest researching methods to represent real life situations using an Object Oriented language like UML and then translate that into C++.

[Teddybare]

Wow!!

Can you explain a little bit (just the overview) on what UML is? I've come across it often but never really got to the bottom of it.

Thanks,
Ted

[GuOddian]

Sure no problem,

UML (Unified Modelling Language) is a specification to describe Object Oriented designs and simplify your code. C++, being a language that conforms to most of the OO (object oriented) prinicpals, is suited to UML. You create class definitions using UML and then translate them into code to represent them.

I would suggest a quick google search for tutorials in OO design for C++ would return may tutorials that would help you. If you're keen to learn more on UML you might start at OMG's UML page (http://www.uml.org/).

[Teddybare]

Thanks for the link.

But my question remains.. and I think this question might be more suited for algorithms and data structures forum.

How is a chess game implemented in software...(just an intriguing thought)

-Ted

[Marc G]

[ moved thread ]

[olivthill]

In many chess softwares, the algorithm is the following:

- Find how much time is available

- Find the list of all the legal moves

- Select the best move amongst them with the exploration of a big subtree, because the "brute force" strategy (seeing many moves with a quite simple evaluation fucntion) is givng good results for computers whereas a more clever strategy (seeing fewer moves but with a more complex evaluation function).

- The subtree is explored until the time limit set earlier is up, or until it is clear that one particular move gives a clear advantage.

- In order to speed things up, the tree is reduced with different tricks, the most simple and popular is called "alpha-beta". This technique takes into account moves already examined in order to avoid loooking for moves that will be worse anyway. It's not easy to explain how it works in two lines, search the internet for "alpha-beta". With alpha-beta, the tree is well shrinked if the best moves are examined before the bad moves. This is why, before examining a new depth level, all the available moves are listed and sorted accorded to an algorithm who guesses the values of the moves.

- The evaluation function is often split in two: a dynamic and a static part. The dynamic part updates the evaluation at each depth, and the static part gives an evaluation of the final situation at the final depth. It is of course better to have a very small or no static evaluation and have a dynamic evaluation.

- The tree can be reduced when similar situations are seen. This happens very often in the endgame, when you reach the same situation if you first move the king then the rook, or first the rook then the king. In order to find situations already seen, the softwares use hash tables to store the score associated with each situation so that they won't have to compute again the score for a situation which has been reached with a different order of the moves.

- The depth of the tree can be dynamic. It is important to go far away when the situation is not stable until you reach a quiet situation.

- If the evaluation varies a lot between two levels, it might be because the situation is not stable, or because the evaluation is not well done. The programmer should try to have an algorithm for the evaluation which is not affected very much by the horizon effect.

[RoboTact]

As I heard, biggest problem is evaluation function (other tricks are just techical details, after all).