## chess programming is coool!

Member
Posts: 749
Joined: 2003.01
Post: #1
Man, I'm trying to program a chess AI...

This is really a cool task actually. Probably one of the most challenging I had...

The "theory" is very simple, you just need to list all possible moves, then the possible replies, then the possible re-replies ecc... up to a point, and at that point evaluate the position "statically' (say just counting how many pieces are left and giving some points to every piece), then procede backwards finding the best move for the player given that the opponent (and you too) will play the optimal move each turn...

the crazy thing is that I'm doing this in Matlab (since I have to learn it for my studies), which is pretty good in the sense that vector operations are built in and many math stuff too, the problem is that it's quite slow I guess...

In the end I managed to get the basic stuff done (oh by the way now all my pieces move like queens, It was the most "challenging" piece so I sticked to that one :-P)

So I organized data in this way: for every piece on the chessboard I listed all possible moves and all the positions in which you may arrive with that piece (that identifies all possible moves), then you create all the corresponding positions (chessboard matrices), and then you should continue iteratively for a while before the "static" evaluation, but it looks that I manage only to look 1 move ahead before the CPU starts taking ages...

I just realized that it might be more convenient to store the information of the chessboards not as matrixes representing the chessboard, but simply by the position of the pieces. However this is quite unnatural and may lead to problems.

I really encourage you to spend a few days trying to set up a "brute force" program, nothing really fancy, just to check out what a cool challenge it is

that's also a really cool idea for a new contest!

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com
Founder
Posts: 1,141
Joined: 2002.04
Post: #2
You should contact Colin at Freeverse about your Chess programming. He may be interested.

Carlos A. Camacho,
Founder
iDevGames
Member
Posts: 156
Joined: 2002.10
Post: #3
The brute force algorithm will work fine for one move ahead, as you say, but beyond that it will be useless. Consider the following:

Assuming, that each piece on the board can make 1 possible move (for simplicity) i.e. 16 possible moves:

White's move : 16 possible moves
Black's move : 16*16 = 256 possible moves
W: 16^3 = 4096
B: 16^4 = 65535

Now this clearly becomes ridiculously large for even a small number of moves ahead, in fact it is exponential in the number of moves. Now bear in mind that especially in the mid-game, there are many more possible moves that just 16!

There are a few possible ways that I can think of off the top of my head to improve your AI. Firstly, store your possible board positions as a tree, so that any possible positions acheivable by one move from a given position are children of that position. This means that when you actually make a move, or the human makes a move, you just find the current board position in the tree and make that the root of the tree, thus you don't have to recompute all the possible moves from that position, as you may have already done all the work. This does however mean that you'll have to keep track of which bits of the tree to start computation from when your AI next gets a chance to think. (NB the AI can also be thinking while the human player is making their move ) When working out all the possible positions, you will want to do the search breadth-first, although I guess you are already doing this.

You also need to consider how you are deciding what is a 'good' position. I don't actually know, but I'm sure google will turn up some good chess-position scoring algorithms, which you can use. Now based on these scores, you can form a heuristic that will cut down how many possible moves you have to evaluate. For example, you could figure out all positions two moves ahead and evaluate all of them, then only consider the top 10% for further analysis. This will allow you too look much further ahead down the 'good' avenues of play. However, it will tend to stop your AI performing suicide or Trojan Horse strategies, which involve sacrificing pieces to gain strategic advantages.

To cut down on storage space you could also consider storing only the move 'deltas' each time, rather than the entire board. However, in this problem I think storing the board will be best as it is CPU use rather than data that will be the bottleneck I expect.

Anyway, have fun, and I look forward to seeing a demo of this AI!

Cheers

- Iain
Member
Posts: 749
Joined: 2003.01
Post: #4
I made it! I mean, I finally wrote this program that, at least theoretically, solves the game of chess!

Of course it's completely unoptimized, extra brute force ultra-stupid, but it works! And you can choose the depth of reasoning!!

I didn't think I would actually manage to make it general enough to be possible to make it recursive, which allows in theory for infinite depth...

From the practical point of view, I can only make it look 4 moves ahead, before it takes ages, anyway with 4 moves he is a decent player...

Yeah now optimisation of the algorithm is a big job, but I'm not so much interested, I just wanted to see if I could make something that with infinite CPU power would play good.

by the way matlab is much faster than what I expected: I mean, I tell him that for every possible square in the chessboard (8x8); the piece on it ,if it exists, has 27 possible moves ,and for every move define an 8x8 new chessboard...

8x8x27x8x8 every depth you want to see, therefore in 4 depths he has to hande

(8x8x27x8x8)^4 numbers... = 149587343098087735296 numbers...

of which about 99% are zeros...

Man this is really spitting on the cpu, but I thought it was the simplest way...

Â©hâ‚¬ck Ã¸ut Âµy stuÆ’Æ’ Ã¥t ragdollsoft.com