Exploring Chess Programming: Algorithms and Mathematics

[kant]

I know very little about chess programming, but i would like know more about it. I want to know every thing i could about it. how do chess programs flind, and plan a move algorithmically? What nice mathematics are there for the game of chess?

 

[rcgldr]

The chess programs assign a value to a position on the board, and include databases for certain patterns, openings, and end games scenarios. Although not a real chess fan, I bought Deep Junior 8 to help out with some co-workers that were interested in chess programs. This is one of the chess programs that have won against world class grand master players.

The algorithms have gotten reasonably good, but the real improvement is due to the shear brute force of the cpu speeds in moderately high end PC's (3+ghz hyperthreading cpus), with 1 or 2 gb of ram, that allow these games to look ahead 13 to 17 moves, and space enough to hold huge opening and endgame databases. The computers are winning most of the human versus computer matches these days when they host events.

With cpu speeds capping out at 4ghz due to heat dissipation issues, multi-processing, like dual core cpus with hyperthreading, will be the way the games push look ahead capabilities further still. Eventually humans won't stand a chance against these programs.

 

[MeJennifer]

There is a good forum for chess programming on: http://216.25.93.108/forum/"

Check the "Computer Chess Club: Programming and Technical Discussions" section.

 

[0rthodontist]

The algorithms have gotten reasonably good, but the real improvement is due to the shear brute force of the cpu speeds in moderately high end PC's (3+ghz hyperthreading cpus), with 1 or 2 gb of ram, that allow these games to look ahead 13 to 17 moves, and space enough to hold huge opening and endgame databases.

Sure, but without alpha beta trimming you would only be able to look ahead five or six ply, not 13.

 

[MeJennifer]

Currently an improvement of CPU speed primarily gives a faster result but not a necessarily better result. For instance even a doubling of CPU power is not going to make a dramatic effect on the quality of the selected move, it is just going to be delivered twice as fast. The time saved is hardly enough to do another ply since we are already so deep.

But needless to say faster is always better in chess computing.

Currently the dual core Athlons blow away any Intel when it comes to chess computer speed. Overclock some 4800+ dual core Athlons and rock!

Deep Blue in 1997 benchmarked about 200 million positions per second while now on the PC we can already reach over 3.5 million positions per second.

 

[rcgldr]

Currently an improvement of CPU speed primarily gives a faster result but not a necessarily better result. For instance even a doubling of CPU power is not going to make a dramatic effect on the quality of the selected move, it is just going to be delivered twice as fast. The time saved is hardly enough to do another ply since we are already so deep.

I was referring to the fact that early PC chess programs were running on 6mhz 286 cpu's, and now run on 3+ghz pentiums, that's a 500 fold increase in speed. Earlier still, there were chess programs that ran on 1mhz 6502 (Apple II) and 2mhz 6502 (Atari 400/800/65/130) cpu's.

 

[0rthodontist]

Currently an improvement of CPU speed primarily gives a faster result but not a necessarily better result. For instance even a doubling of CPU power is not going to make a dramatic effect on the quality of the selected move, it is just going to be delivered twice as fast. The time saved is hardly enough to do another ply since we are already so deep.

Doubling the speed of the computer should give a constant increase in ply, whether you're already at 3 ply or at 12. I think it would be less than 1 ply though.

 

[MeJennifer]

Doubling the speed of the computer should give a constant increase in ply, whether you're already at 3 ply or at 12. I think it would be less than 1 ply though.

Incorrect, the increase in ply is not constant, the deeper the CPU calculates the less the improvement when the speed doubles.

 

[0rthodontist]

No, the deeper the CPU calculates, the less improvement when the speed increases by a constant amount. When the speed doubles, the ply increases by a constant amount because the n'th layer of the game tree is exponential in n. If for example the branching factor in the game tree is 2, the ply will increase by roughly 1 for every doubling in speed, regardless of current ply, because the number of leaves is roughly equal to the number of internal nodes. If the branching factor is 4, the ply will increase by roughly 1/3 for every doubling in speed, because the number of leaves in this case is roughly equal to three times the number of internal nodes.

I don't know what the typical branching factor is in a chess engine--probably it is larger than that so a doubling in speed will yield a smaller fraction of a ply.

 

[MeJennifer]

All engines use pruning since a raw calculation (e.g. the brute force approach) is a waste of resources for obviously bad moves. The branching factor depends on the pruning mechanism for the particular chess engine. Obviously you can have an engine that calculates more ply but prunes too much. Furthermore if your position analysis function is too advanced you slow down your processing.

 

[buddyholly9999]

I think that I read the best chess program looks ahead 40 ply. I can kick any computers @$$ at chess...all I have to do is unplug it.. ;)

 

[MeJennifer]

I think that I read the best chess program looks ahead 40 ply. I can kick any computers @$$ at chess...all I have to do is unplug it.. ;)

I doubt that 40 is at all possible with current hardware.
Of course it depends on the amount of pruning. Typically chess engines search deeper on certain branches they consider "interesting", things like king attack or possible pawn promotion etc, so some branches might get to 40 but not on the whole.