C Chess game lacks power?

Hello C World,

I am a beginner to programming and to the C language, so please forgive me if I am not as knowledgable as I should be. As a side project during my first year of programming I've been working on a chess playing program, with a built in AI (as of now it only plays the black pieces). I want it to be strong enough to beat a couple of chess-playing friends of mine(around 1800 strength), or barring that, a low-strength piece of commercial software like Chess-Titans.

However a problem I have been running into is that no matter what I try to do to prune the search tree, the search times seem to be unusually slow. As of now, with alpha-beta pruning, and some sorting functions, it can search at a depth of 5 ply at an average of about 1-2 min. per move. I know that in order to be decent, a program should be able to search at least 7-8 ply.

I know there are more pruning functions that I could add to prune the tree more aggressively. But I can't shake the feeling that that isn't the problem. My friend (non-programmer) suggested that maybe the program isnt' drawing enough resources from the computer. I am sure the basic functions of the code (i.e. the function which checks legality of moves, the piece functions etc.) are poorly optimized, which maybe could cause the slow down. But I have tested with trying to improve the efficiency of the code and it hasn't changed the search times one bit.

Is there anyone with experience as a programmer/Chess-AI programmer who could provide their insight? If requested I could post my code, but be warned its excessively long and maybe a bit obscure..

*(I ran the program locally and looked at it in taskmanager. under memory it says its using 680K. Could that be relevant to the slow search times?)

I have done a chess AI that plays at about 2200 before (Brainless).

Do you know if your problem is an excessively large tree or slow node search speed? Try adding node counting to your program, if you don't have it already. See what kind of NPS (nodes per second) you got. Crafty does about 4 million NPS, with a lot of highly optimized inline assembly. My program does about 1.5 million NPS, and is considered fairly fast (it has relatively rudimentary evaluation).

With alpha-beta and trivial ordering (captures of high values first), you should be able to go 6-7 plies in a few seconds.

Memory usage has nothing to do with this. You shouldn't need much memory until you implement the transposition table.

[Edit]
Ah. Yea. Don't bother with this. I misread the quoted statement.
[/Edit]

Quote:

---

You shouldn't need much memory until you implement the transposition table.

---

What?

Soma

thanks for your response.

I tested the NPS and it seems very slow, only a few thousand nodes per second. It takes the computer over half a minute to do a full width min-max search at 3 ply during the middlegame. Evaluation function is extremely simple at this point so it can't be due
to that.

Do you have any idea why NPS would be so slow? I stored the chessboard in a 3-dimensional array (two dimensions for the board, the third for past and present board positions). My code might be inefficient in many places, but does that account for the lack of search speed?

A NPS that low is definitely a problem. The ply count sounds about right for that kind of NPS. You should aim for at least in the 100knps range.

The reason is probably the inefficient code. No one can tell you what's wrong with it without seeing the code, and probably no one has time to go through your whole program to find out what's wrong since it's probably pretty big.

That's why a chess AI is not really a good beginner project - it requires you to know how to write fast code, what actually happens in background with every C statement, what constructs are fast, and what constructs are slow and should be avoided (memory access patterns, etc). Unfortunately that really only comes with experience, and if you try to learn all those optimization techniques now, it would be very confusing and distract you from your learning of general programming concepts, which are much more important.

A fast chess AI is usually ugly (just look at Crafty source code...) out of necessity for performance, but that's not the kind of code you want to be writing as a beginner.

Therefore, I suggest putting this project aside for now, and work on something else first, and come back to this once you feel more confident about the language, and programming in general.

I always wanted to make a chess game that decided its moves by trying to own as much of the board as it could. It would pick whatever move gave it the most control of the most enemy pieces or the most board coverage:

rkbqKbkr
pppppppp
11111111
00000000
00000000
22222222
pppppppp
rkbqKbkr

At the start, everything with a 1 is owned (covered) by the top player. Everything with a 2 is owned by the bottom player. Player 1 would make a move which would own the most squares for them (or control the most enemy pieces - put them in danger). Each piece would have point value that would help decide what was a better piece to cover in the event of a tie.

No look-ahead. Just try to gobble up as much of the board and pieces as you can. Then I'd just make it play itself to see how it would turn out. But I never get around to doing it.


Quzah.

A more involved form of this concept is present in most chess engines - static exchange evaluation. Basically "score" a capture based on expected exchange of material without a real search. It's used in move ordering, which means all else equal, a move that will win material has better chance than a move that will lose or not win as much material. However, there are obviously many exceptions, that's why it's not usually an evaluation term. The closest idea that's commonly an evaluation term is mobility (essentially number of possible moves). It's pretty important.

With AIs that do only what you described, the game may be fun to watch, but the program will be very weak.

Quote:

---

Originally Posted by Coolio_High

Hello C World,

I am a beginner to programming and to the C language, so please forgive me if I am not as knowledgable as I should be. As a side project during my first year of programming I've been working on a chess playing program, with a built in AI (as of now it only plays the black pieces). I want it to be strong enough to beat a couple of chess-playing friends of mine(around 1800 strength), or barring that, a low-strength piece of commercial software like Chess-Titans.

However a problem I have been running into is that no matter what I try to do to prune the search tree, the search times seem to be unusually slow. As of now, with alpha-beta pruning, and some sorting functions, it can search at a depth of 5 ply at an average of about 1-2 min. per move. I know that in order to be decent, a program should be able to search at least 7-8 ply.

I know there are more pruning functions that I could add to prune the tree more aggressively. But I can't shake the feeling that that isn't the problem. My friend (non-programmer) suggested that maybe the program isnt' drawing enough resources from the computer. I am sure the basic functions of the code (i.e. the function which checks legality of moves, the piece functions etc.) are poorly optimized, which maybe could cause the slow down. But I have tested with trying to improve the efficiency of the code and it hasn't changed the search times one bit.

Is there anyone with experience as a programmer/Chess-AI programmer who could provide their insight? If requested I could post my code, but be warned its excessively long and maybe a bit obscure..

*(I ran the program locally and looked at it in taskmanager. under memory it says its using 680K. Could that be relevant to the slow search times?)

---

Have you run a profiler on it? Would probably be way more helpful than task manager at determining what could be optimized.