Sign in to follow this  
aztoys

Chess Artificial Intelligence

Recommended Posts

Hi I'am making a game for the PSP console its a basic chess game and i was wondering if implementing artificial intelligence to it was possible where do i even start? can anyone link me to a chess game with a.i that provides source codes?? right now my game only can be played player vs player not player vs comp.

Share this post


Link to post
Share on other sites
Modern chess programs have a clear separation of engine (the part that "thinks") and GUI (the interface), and the two of them communicate via a text protocol. Some people only write engines, which every user can use with their favourite GUI. This also allows for easy matching of one engine against another. The same protocol can be used to communicate with a chess server over the Internet. There are two common protocols: WinBoard and UCI. I recommend using UCI, since it's designed better.

A lot of good info about how to make a chess engine can be found at Bruce Moreland's website.

Share this post


Link to post
Share on other sites
Hi Aztoys,

Fortunately for you, chess AI is very well documented :).
Basically, in theory, you create a tree which contains all of the possible outcomes of the next N moves (and all possible player responses), and select the move which leads you to the "best" outcomes. In addition, to simply things, you always assume the player tries the best possible move available to him/her.
One may ask:

1.) What is the "best" outcome? A naive answer might be: for a given board configuration, compute (number of player pieces) - (number of opponent pieces) on board. There are, of course, other (and better) criteria.
2.) What is the best/fastest way of searching the game tree?
3.) How deep and how wide does one need to construct a certain game tree?

There are also programming-related questions, such as:

4.) How many moves into the future does my current hardware allow me to calculate?
5.) How should I store a board configuration at a tree's node?

Producing full trees for chess is very prohibitive, as there are many, many configurations. The "common knowledge" algorithm used to cut down on the number of tree nodes is called the alpha-beta algorithm - look it up.
There are also other tricks such as creating in advance moves for pawns (which are "simple", since they can almost always move one step ahead).
I have never implemented a chess AI program myself so I'm afraid I can't give you practical advice, but I hope the ideas and buzzwords I've given you here will give you a good headstart.

Assaf.

Share this post


Link to post
Share on other sites
Quote:
Original post by assaf
Hi Aztoys,

Fortunately for you, chess AI is very well documented :)...


This approach can build an engine that is fairly strong in the endgame but much weaker in the positional opening/middle game. With 32 pieces on the board each with 28 potential moves there are > billions of potential positions after only 2-3 moves. I'm sure Fritz, Deep Blue or one of the other top AI engines is able to see fairly deep into a middle game but that is a lot of data to analyze.

I think to build a truly strong Chess AI you need to combine the brute force method with a system to analyze the positional game. This is incredibly complex. Sometimes passed pawns, open files, doubled pawns, centralized knights.... are good and sometimes not. You really can't look at 2-3 pieces and say 'these guys are sitting on ideal squares'. You need to take in the entire board and, usually, there isn't a logical reason one position is better or worse than another.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this