4th Computer Chess Tournament

An anonymous reader writes: "The 4th computer chess tournament is being held online at Internet Chess Club over the next two weekends. Over 50 chess programs are involved, from commercial engines to amateur homebrews. Most will be operated by their authors. Details at CCT4 homepage. Last tournament (CCT3) there was live commentary by titled human chess masters. If you're a fan of chess or computer chess programming, login to ICC this weekend as a guest and watch the action."

Comments

How long do the games last?

[Spazntwich]

Especially with no speed throttle on the chess programs, I would imagine a normal game could be over in a few seconds.

Re:How long do the games last?

[nomadic]

I don't know, playing GNUchess at the easiest level, it takes the computer a few seconds per move. And that's in the opening, near the end it can take a little longer.

Re:How long do the games last?

[bonzoesc]

Lots of chess programs will compute out the entire game. Since the possible moveset increases exponetially every turn, calculating the whole game can take much longer than a minute in many cases.

Now, if the engines chunk up the game into larger metamoves, they might take less time, but also wouldn't be able to do it with the same chilling accuracy a brute-force program could.

Re:How long do the games last?

[ironfroggy]

lol

ive head chess programs taking days to find a good move.

Re:How long do the games last?

[Anonymous Coward]

Are you serious? : )

I don't know the exact time controls for this tournament, but generally for human tournaments they are something like:
40 moves in 2 hours, 1 hours sudden death
Which means you each get 2 hours to make your first 40 moves, and then one more hour each to make the rest of your moves.

Computer chess tournaments use the same time controls (approximately, there are many variations, and they probably use "fischer clocks", where you get an additional 5 seconds (or some other amount) every time you make a move).
The games probably proceed along similar lines to human ones:
Lots of moves (more then 20 is not rare...) are played in about 5-10 minutes, because both players have played them all before, (and for the computer it's in it's opening book, and played instantaneously), until one of them decides to deviate. Then one takes a long think to evaluate the new position, play proceeds fairly rapidly after that, the computer will use most of it's time (why not? it can definetly find better moves the longer it thinks).

Besides, most of these engines will just run on somebody's desktop, which are a far cry from the power of Deep Blue (IBM's computer used in the matches against Kasparov).

Re:How long do the games last?

[harlows_monkeys]

Since the possible moveset increases exponetially every turn, calculating the whole game can take much longer than a minute in many cases

Calculating the whole game would take, on average, a few dozen orders of magnitude longer than the expected life of the universe, using current computers, so I'd call "much longer than a minute" a rather large understatement.

Re:How long do the games last?

[Utopia]

You must either be kidding or you don't know what you are talking about. No chess program can compute out an entire game is a minute.

The fastest chess program Deep Blue, a 32-processor parallel computer with 256 VLSI chess engines, was capable of 200,000,000 positions per second which meant that it was able to conduct an exhaustive 12 ply (or 12 half moves) search for every move.

Re:How long do the games last?

[bonzoesc]

I said this:
...can take much longer than a minute in many cases.

Last time I checked, "all" fits completely within the bounds of "many," and infinity is longer than a minute. It's a good thing you do such a great* job at identifying thinly veiled wit.

*terrible

Re:How long do the games last?

[Anonymous Coward]

You also said "Lots of chess programs will compute out the entire game." Was that just wit too?

Re:How long do the games last?

[FigBug]

I don't understand it. GNU chess on my 386 took a few seconds a move, GNUchess on my 1.4 Ghz Athalon takes a few seconds a move and it doesn't seem any harder. why aren't chess games getting any faster? I'm guessing there is no game logic other than rand() and a lot of sleep() statements.

Re:How long do the games last?

[Hercynium]

I'm taking a leap here, but you haven't coded any chess algorithms, have you.

Any half-thinking programmer will realize when creating a chess-playing algorithm that the prediction branches are much more likely to decrease throughout the game, effectively (on a basic level) decreasing your moveset. One of the cornerstones of this type of game programming is algorithmic pruning of the game or 'moveset' tree. Every capable chess program strives not to create every possible move, but to eliminate all non-possible moves, as well as most non-likely moves. The path of the branch prediction and generation routines will usually use some sort of weighting algorithm to determine how deep to search, but the pruning algorithm is of utmost importance since it will aid in how deep the program will be able to search.

Now, granted, an algorithm, given infinite time and computer resources may very well try to predict every possible move, but it's not just unlikely, it's also likely to get it's ass kicked by other, more effecient algorithms.

Just my $.02

Re:How long do the games last?

[Choose Wisely]

I would assume it's because you're running it under GNU/Linucks. Perhaps you should try recompiling it with a much faster compiler for a commercially viable operating system?

Re:How long do the games last?

[ichimunki]

Reading some of the posts following this, I'm guessing it's because there is a how_long input to the move() algorithm. Said algorithm then calculates what it can in the time given and plays with what it knows when it runs out of time. Therefore to increase the apparent "skill" of the computer the first thing to do is to increase the how_long input so that it has time to do more figuring before it is forced to make a move. This squares with what I've seen on some chess games where the options are an either/or selection: you either enter a difficulty level or a per-turn time constraint.

Re:How long do the games last?

[dnoyeb]

Uhh, guys. I think a computer can. They dont need to compute until all the pieces are off the board. Just until what they percieve is a "final advantage." This can happen relatively quickly. However Im sure you appreciate the vagueness of "final advantage." And of course analysis of openings is done offline, at the game they just go from book.

Hardware

[GigsVT]

As for the hardware, you are free to use what ever you want. It would be impossible to try to get all participants use the same computer-power and to make sure that they do.


Imagine.... :)

Without equal hardware platforms, this will be hard to be more than just entertainment. It isn't much of a good benchmark of the programs involved.

This is especially true when you consider that certain processors are usually faster at certain critical operations in cases like this. It also apparently doesn't ban ASICs and other things that could make a huge difference. On the plus side, maybe we will start seeing PCI chess accelerator cards. :)

Re:Hardware

[Anonymous Coward]

And now, the obligatory /. response:

Imagine a beowulf cluster of chess-playing machines!

Re:Hardware

[sporty]

That's ok. If you don't have the IBM super computer, you could always use, dare I say, a Beowulf Cluster? :)

Re:Hardware

[tshak]

Without equal hardware platforms, this will be hard to be more than just entertainment. It isn't much of a good benchmark of the programs involved.


This is true only to an extent (unless you're playing a blitz game). Speed is very important, but chess is way to complicated to "brute force" on any type of hardware that I'd suspect would be used at the compitition. Speed is better found with incredible move analysis algorithms that are smart enough to find the best move in a short amount of time. Take, for example, the Rebel chess engine. On an Athlon 1200 it is nearing a 2800elo rating. Of course, giving it an Athlon XP 2000+ may make a difference, but many good chess engines rely a lot less on hardware and much more on the software.

Of course, it would still be nice if they all had equal hardware. I'm just pointing out that once you get a fast enough machine the hardware becomes much less of a "speed" bottlneck.

Re:Hardware

[RobertFisher]

While I agree that this is strictly true, the hardware used does not vary dramatically -- most every one is a 1 GHz - 2 GHz machine. Considering that the branching in the tree of game possibilities is a combinatoral explosion, the differences in hardware alone will not allow researchers to explore to a significantly greater depth.

The main problem in computational chess playing is not so much in the brute force with which you can explore the tree, but in how one prunes a branch when the option starts looking unpromising. That is really an algorithmic question, and I would be willing to bet that the best algorithm will in fact win in a competition of this sort. It is a bit analogous to taking two comparable, but unequal hardware machines, and running bubble sort on one, and quick sort on the other. Quick sort will always win, hands down, because it is the far superior algorithm.

What did surprise me was that there were no parallel machines on the list -- not even an SMP. I do think that with enough processors and a reasonably sophisticated algorithm, an amateur team could in fact stand to beat a more sophisticated algorithm. But that isn't the case here.

Bob

Re:Hardware

[Night0wl]

BeoWulf clusters aren't yet applicable for computer chess. At least not any typical player vs. player chess.

there isn't a, not that I know of, engine capable of harnasing a beowulf cluster. There are though several which are capable of mutlithreading.

The only beowulf engine in development, again that I know of, is by Hyatt. The creator of Crafty.

He's got a cluster of 10, Quad Xeon boxes at his disposal. Lucky man.

Re:Hardware

[GigsVT]

You are incorrect about the SMP.

1,26GHz PIII Dual Tualatin
512MB

1GHz PIII Dual
512MB

1,2GHz Athlon Dual
1GB

800MHz PIII Dual
256MB

700MHz Xeon Quad
512MB

Etc...

I'm surprised no one is using a cluster though. With hardware prices so cheap, a 6 node cluster can be built for less than $1500. I am doing that right now in fact.

I am in total agreement with you about how algorithms are overriding in determining performance. I do think that algorithms that are on the same order of algorithmic growth will not be fairly compared to each other with diverse hardware like this though.

I mean I know a O(n) will always beat an O(n^2), but with dissimilar hardware, you aren't going to be able to compare 2n+34 with 2000n+100, if you get my drift. A large constant coefficient difference in two algorithms may be concealed under a fast processor.

Re:Hardware

[Anonymous Coward]

Your drift is kind of misguided. The hardware really isn't all that dissimilar. You're not even going to have a factor of 3 speed difference, much less a factor of 1000. Remember that it takes a significant factor of additional board positions for each additional 1/2 ply of lookahead so the differences aren't that big.

Re:Hardware

[alito]

Hardware isn't as important in chess (ok, ASIC's would probably make a big difference) as in other programs. A factor of two in hardware speed difference would not even give one more ply in search depth, it will probably change it's rating by about 50-70 points but no more. Remember, chess has a very high number of branches per node (about 30), and a big factor in the strength of the program is to find smart ways to reduce that branching factor. I agree, though, that is not a good benchmark. This is just one more tournament. There are a lot of these every year (somehow, this one made it to slashdot). For a better attempt at benchmarks, go to the ssdf homepage

Re:Hardware

[Anonymous Coward]

As for the hardware, you are free to use what ever you want.

Wow! Can I enter Garry Kasparov in a box?

Re:Hardware

[Skuto]

>I'm surprised no one is using a cluster though. >With hardware prices so cheap, a 6 node cluster >can be built for less than $1500. I am doing >that right now in fact.

The latency of a (standard) cluster is too high to make it effective for chessprogramming. Moreover, it doesn't have shared memory, which is another major disadvantage.

There has been a project to make programs run over a cluser (APHID, find it via google), but as you've already seen it didn't leave a terribly good impression.

--
GCP

Re:Hardware

[Skuto]

>While I agree that this is strictly true, the >hardware used does not vary dramatically -- most >every one is a 1 GHz - 2 GHz machine.

Considering that a doubling of speed is often said to equal about 50-70 elo points, the difference certainly _does_ matter.

Many of the programs are very close in playing strength. A free 50-70 ELO boost can make quite a difference in where you finish eventually.

--
GCP

Chess Programming.

[msolnik]

I really have to give major props to these guys. Once in school I wrote a basic chess game. The algorithims in it are hard as hell to write. And even harder to get them to win games. These guys must really know there stuff and I just have to say good job and good luck to all who entered!

Re:Chess Programming.

[Skim123]

Is it really that hard to make a simple chess engine? I'd imagine it is very complicated to make a good one, but I would also wager there are books with cookie-cutter designs for making a simplistic one.

Re:Chess Programming.

[ctid]

It's not that difficult to make a chess engine. Unfortunately there are few books in print that would help a beginner, however. Generally a couple of weeks to get the engine playing legally plus a day or so to get the automatic intrerface working can get you online at ICC.

Re:Chess Programming.

[bigbadbuccidaddy]

No. I wrote one when I was a teenager. It wasn't very good at chess, but then again I was concentrating more on making the graphics look pretty (on CGA!). It was my first and probably last project in C. I am thinking about writing a decent chess engine in the near future. Stay away from the books and come up with something original. After a few revisions, then look at books for inspiration.

Re:Chess Programming.

[Anonymous Coward]

My program is in the tournement and it is written in Basic. It is compiled though, but still not as fast as the other more professional programs that are written in "C".

Re:Chess Programming.

[wildbill2]

That's entirely right, I wrote a 6809 chess program on my Radio Shack Color Computer circa 1984 and it was able to play a decent, but not great game.

I had a few good ideas (such as checking for doubled pawns on open files) but I haven't even worked on source code for a chess program for more than a decade, so I don't know if they've ever been adopted by Crafty or Gnuchess. Or if they're too expensive to really implement well.

What about this:

[The FooMiester]

I'd like to see a distributed chess engine. I think it would be fun to pit us against Deep Thought. It's kinda off topic, but something I've been thinking about.

Re:What about this:

[Score0, Overrated]

It might be quite difficult to do ... how suitable is chess to being calculated in parallel.

Determining the best move at a single point in the game can't simply be split up among X computers because there are a heirarchy of moves - the first move available can be chosen from a small pool but each of those leads to more and more.

I suppose a monte-carlo like simulation would work - each machine picks a random move each time and returns the first move and the the final goodness. The master computer picks the best first move from the returned results.

Re:What about this:

[TMacPhail]

Are you sure you meant "Deep Thought"? That is the supercomputer built in "The Hitchhiker's Guide to the Galaxy". Although that would be an interesting computer to play chess against, I believe the computer you meant to refer to was "Deep Blue", the computer which Kasperov played against.

Re:What about this:

[The FooMiester]

Whereas most engines pick moves based on score, not very hard at all. Each machine would be given a move(and perhaps a reply, if enough machines existed), and would come back with the score of that move, with possible followup moves.
I think it could be done.

Re:What about this:

[The FooMiester]

No, I meant deep thought. Deep thought will be built eventually, to program the Great Computer. =) But when it's done doing that, I'm sure it could kick the arse of deep blue any day of the week, even thursdays.

You're right, I meant deep blue. My apologies

Re:What about this:

[Score0, Overrated]

Thinking about it some more, my initial monte-carlo method would not work because it would favour opponent's bad moves as well as your good ones. You have to assume, really, that your opponent is going to try :-)

I think you would need a heirarchy of machines, which are handed off tasks when necessary - you can't simply break down the problem once each time it is your turn to move.

Re:What about this:

[ironfroggy]

Deep Thought would, with no problem, know your every thought and motive and predict EXACTLY your next moves till the end of the game.

Re:What about this:

[Tom7]

I don't think it is very hard. Game tree search is inherently parallel, you just need to be able to balance the assignment of subtrees so that you utilize processors well without too much overhead.

Check out Cilk and Cilk NOW for instance:

http://supertech.lcs.mit.edu/cilk/home/intro.htm l

They have a parallel chess implementation.

Re:What about this:

[Anonymous Coward]

Modern chess engines also do not just plow through every possible move... As that would take far, far too long. They use hash tables, and also do not only search through each line once, once they find moves that greatly change the evaluation of the position, they go back and try them again in other positions, and remember them to try first in future positions.
They also have algorithms for selecting which candidate moves should be examined first in a given position.

Also try to remember that the computer can only evaluate a position based on how the programmer told the computer to evaluate it. This depends on the chess strength and understanding of the programmer (well, programming team). And it takes years to aquire the chess knowledge required to evaluate a position accurately.
I should know, I've devoted a significant portion of my life to playing, studying and teaching chess.

Re:What about this:

[mandolin]

Well, distributing the computation over several boxes still has its inefficiences. Often programs will for speed's sake store position evaluations in a central hash table, or a history heuristic matrix or somesuch. Some of these techniques can be extremely useful in pruning the tree to be searched. One problem (I would imagine) is finding the tradeoff between communicating enough of this kind of information to nodes that could use it, and the network overhead it takes to do so. A simpler task would be taking advantage of multiple threads on an SMP box, like craftycan.

Apparently this hasn't stopped some people from doing the totally distributed approach though; try googling on "zugzwang chess program" for an example.

Re:What about this:

[What goes up]

The Deep Blue computer by IBM was a parallel chess computer. Here is an excerpt from IBM's web page:

The latest iteration of the Deep Blue computer is a 32-node IBM RS/6000 SP high-performance computer, which utilizes the new Power Two Super Chip processors (P2SC). Each node of the SP employs a single microchannel card containing 8 dedicated VLSI chess processors, for a total of 256 processors working in tandem.

If you are referring to a geographically distributed system, similar to distributed.net, I don't think that would work in a chess program. Chess computers require fast communication between processors, which the internet does not provide.
--- Mr Taco, tear down this wall!!!

Re:What about this:

[hayne]

Here's what Robert Hyatt (author of Crafty & Cray Blitz) wrote in the rec.games.chess.computer newsgroup in May of 2000:

> How are transpositions handled by a distributed engine? Is there a distributed transposition table?

Good question with multiple answers. Each machine would probably use a local hash table only. As a distributed hash table over the internet would simply not work, even with internet2 speeds. The latency/jitter is too high. But for a local 'beowulf cluster' yes distributed hashing is viable.

Re:What about this:

[Anonymous Coward]

It really depends. As other posters have said, pruning the game tree is the alpha and omega in chess engines. You need to prune at least identical and clearly-inferior positions. To do that you have to have a shared hash between the processes.

So to do it locally could be fast and furious, but over the internet it would probably be a disadvantage.

Re:What about this:

[Anonymous Coward]

That is simply not true. Game tree search is inherently serial. The data dependencies cannot be calculated beforehand. Thus a search in general will degenerate due to communication overhead and unnecessary work done,as the number of processes grow.

Re:What about this:

[Anonymous Coward]

Monte Carlo simulations won't work. Since the value of the searched position depends on one 'critical' variation. Finding that variation by random search is close to impossible. Due to the immense search space involved.

Re:What about this:

[Tom7]

> That is simply not true. Game tree search is
> inherently serial.

No, optimizations on game tree search (ie, alpha-beta pruning and hashing) may be serial, but regular game tree search is totally parallel.

The trick of course is to find a balance between these two, which the Cilk folks did.

Re:What about this:

[dnoyeb]

You MUST be kidding? every piece has multiple moves it can make. Each computer can analyze a complete branch on its own. This is incredibly parallelable.

Re:What about this:

[Anonymous Coward]

Interesting definition of parallelization. You do realize that the effectiveness of a parallel mini-max rapidly goes towards zero. When compared to alpha-beta. Mini-max is not a viable algorithm and should not be used as a serious comparision. As for Cilk and Cilkchess, it does not exibit a great degree of speedup.

Re:What about this:

[Anonymous Coward]

but not with a cluster, as you need shared memory (the transposition table)

Moron

[Anonymous Coward]

Maybe you don't feel it while playing Quake 3, but *time* is still a constraint for many many computational tasks. Chess programs in particular would *love* to have 10^36 years to make each move. They only have a few minutes, so they *are* time constrained.

chess nerds

[mr_gerbik]

as if getting picked on for being in this chess club wasn't enough.. they had to go make an internet chess club to insure that nerds will get a good beating by the jocks.

Will they be printing out move-lists...

[Ieshan]

I think it would make it wholly more entertaining if they printed out move-lists and provided a viewer which reproduced the moves, say one or two a second.

It'd make the games more interesting to those of us who actually play (and don't just code chess), and it would get the public involved (can you picture a CNN short on this without having any sort of visual representation - it's the only way it'll get coverage!)

Re:Will they be printing out move-lists...

[CyberDruid]

Of course they will. It will most likely be available in the standard PGN-format and a few of the commercial formats. Just use xboard (or winboard, if that's your cup of tea).
But all the internet chess clubs also support interfaces, so that you can watch the games live on a chessboard with standard diagram pieces. win/xboard can be used for this as well.

Shannon and chess programming

[s20451]

I was reading through the biography of Claude Shannon (information theory guy) and was surprised to read that he also did important research in chess-playing computers. The biographer suggested that his innovations are still in use today. Does anybody know more about this? How do you program a computer to play chess, anyway?

Re:Shannon and chess programming

[dimator]

http://www.howstuffworks.com/chess.htm

(Is there anything that site doesnt have?)

Re:Shannon and chess programming

[E-prospero]

How to program a computer to play chess: ($0.10 version)

The underlying idea: you try an build an exhaustive tree of every possible move, and every possible response to that move, and every possible response to that response, and so on. This gives you a full tree of all possible games; You then choose a branch on the tree which results in you winning.

The problem: This tree is huge. After just a few moves, there are literally billions of potential board positions which must be considererd. Even Deep Blue (the recent Kasparov killer) wasn't able to perform full board evaluation, even with all it's specialised chess-playing hardware.

The solution: Rather than trying to exhaustively search the entire possible move tree, only search those branches which "look promising". This is assessed using a scoring system of some kind.

It is this scoring system (called a heuristic) which is the source of all the research. This is a source of interest to information theorists as the problem of finding a chess heuristic is easy to understand, but non-trivial to solve. Essentially, the problem is to reduce the "information" describing a board position into a single boolean "this is a winning position"/"this is a losing position".

If you're interested, seek out an introductory AI textbook (or website), and look up alpha-beta pruning. I can recommend "Artificial Intelligence: A modern approach" by Russell and Norvig. The website for the book is here

Russ %-)

Re:Shannon and chess programming

[Peyna]

If you think that a tree of all possible moves for chess is huge, you should try Go. There's so many more possible moves in just the first 4 or 5 turns.

Re:Shannon and chess programming

[Anonymous Coward]

Go has a high branching factor due to the enormous board size but branches also get pruned a lot faster because there are extensive libraries of patterns known to be bad. Scoring a chess position is not as exact.

Re:Shannon and chess programming

[Priam]

AFAIK, *no* program designed to play Go has come anywhere close to beating a human that is remotely good at the game. Show me a successful Go AI, and then I'll be impressed. :)

Re:Shannon and chess programming

[sceptre1067]

"Go has a high branching factor due to the enormous board size but branches also get pruned a lot faster because there are extensive libraries of patterns known to be bad."

Umm... Joseki, the patterns you mention, though extensive, do not lead to pruning per se. In Go one is going for a one or two point gain so the Joseki tend to be subtle. Also they are 'localized' patterns and do no guarantee a win. (Tactics vs. strategy.)

"Scoring a chess position is not as exact."

I disagree... Chess IMHO (compared to Go) is only tactical. Chess positions have been just as well studied as Go and each position is well known. Merely choosing a Queen side castle vs. a King side castle decides the direction of the whole game of which the repercussions are obvious (e.g. both players choose Queen side tends to lead to attrition, one or the other choose Queen side tends to lead to and 'interesting game', and both King side is rather normal...)

In Go a certain Joseki pattern in no way guarantees what happens on the other end of the board...

Just my $.02, from someone who once played on chess and got 'converted' to go...

Re:Shannon and chess programming

[Peyna]

I found a Go game for my Palm V. It was supposedly based on GNU Go, but the AI was so poor, that even myself, a beginning Go player could beat it 90% of the time. (It didn't even score right.. ugh.)

Anyway, GNU Go is pretty good, scoring 8th in the 21st Century cup.

Re:Shannon and chess programming

[Score0, Overrated]

Is there anything that site doesnt have?

http://www.howstuffworks.com/SlashdotModeration. ht m

Re:Shannon and chess programming

[Anonymous Coward]

Hmm.. you have neatly answered your own question.

To wit:

Is there anything that site doesn't have? Lego porn!

Re:Shannon and chess programming

[filtersweep]

AI, huh?

I think *true* AI would not have the programmer(s) assign the "scoring positions." A system of mixing the programmers "scoring" agenda with permutations of moves still plays to the bias of the programmer. The good/bad position argument should ideally be resolved by the program itself, and the game's own "learned" experience. Obviously the rules themselves dictate which moves are stronger/weaker.

What about "learning" the opponent? Of studying previously played games? (Which was one of the issues with the Deep Blue match).

Theoretically two well designed game engines should always end in a draw when playing against each other.

My Palm has a pretty tough chess game... on the easier settings, it literally lets people win by tossing in a random obviously "dumb" move. At its best level, it is very difficult to beat by most mortals. I wonder how fast that processor is... or how many KB the game is? 15 years ago there were decent chess games on relatively primitive equipment. Not that these will win some fancy tournament... and not that there aren't corners being cut... but these definitely are not AI!

Re:Shannon and chess programming

[E-prospero]

As someone with a PhD in AI, who has lectured on the topic at University, allow me to assure you that Yes, this is AI. However, it is not what the public generally thinks of as AI.

AI research suffers from the major problem that it started out with grand intentions (machines that think like you and me!), and has had some great publicity, but 50 years on, it hasn't delivered on many of its promises.

Those in the trade generally classify Search, categorisation and optimisation problems like this into the category of Weak AI. They exhibit "intelligent" behaviours - i.e., they are driven by knowledge, and make informed decisions - but they are algorithmic, and cannot adapt, develop or expand upon their original programming.

The other form of AI - the form promised by movies and books - is referred to as Strong AI. This is a largely untouched problem - mostly because it is extremely difficult to even quantify what it is we mean by "intelligent".

In some ways, Strong AI defies quantification - if you can clearly define what an intelligent behaviour is, you can define an intelligent algorithm to follow - but this implies that your algorithm isn't intelligent, as it won't move outside its programming.

As for your Palm chess game - are you sure that on lower settings the program is "letting" people win by throwing in an "obvious dumb move", or is the move selection heuristic for the program just poorly suited to certain game positions?

Russ %-)

Re:Shannon and chess programming

[Hektor_Troy]

Damnit - you stole my joke you punk!

Re:Shannon and chess programming

[Skuto]

>Go has a high branching factor due to the >enormous board size but branches also get pruned >a lot faster because there are extensive >libraries of patterns known to be bad. Scoring a >chess position is not as exact.

It's way, waaay harder to score a Go position.

In chess, count the material and you'll already have a good idea who's winning in 95% of the positions a _computer_ looks at. There is no such equivalent for go.

--
GCP

Chessmaster?

[pgpckt]

I always wondered why Chessmaster and other well known commonly avaliable commercial chess programs don't compete in these competitions. I would think it would provide:

1) Great exposure for your program
2) A great way to motivate your programming staff to work at 100%
3) A way to show you are number 1

And for the programmers, if you acutally win, it would seem one of those great things you can put on a resume.

So why no chessmaster?

Re:Chessmaster?

[phantumstranger]

Chessmaster is not a fully functioning chess program. It is really more of a DB full of a shit-load of games (at least with CM 8000) and a teaching program. While I agree with damn near every other player in the world that CM is the best commercial chess program for learing, I have huge doubts with how it would match up in competitive play. I can reguraly beat CM8000 and I'm a tentative ~1500+ rated player. (In comparison the top three players in the world are well above 2700 and two are above 28.

Re:Chessmaster?

[CyberDruid]

Usually they do compete.
Chessmaster is not an engine per se. It uses "the King", which was written by König. If the King is not in the competition it is probably because it is a bit old and not up to the challenge of beating Fritz, Deep Junior, Shredder, Chess Tiger/Gambit Tiger, Ferret and the other really strong programs.

Re:Chessmaster?

[hangdog]

Because this sticker wouldn't help sell copies of the game:

"Chessmaster 9000. We finished 12th in the All-World Computer Chess Competition!"

Probably too much risk for them. Maybe they would enter the program under a pseudo-name?

Re:Chessmaster?

[alito]

You are misguided about chessmaster's strength. Chessmaster 8000 regularly plays in these tournaments and does rather well. It may not beat Fritz or Shredder but it's right below them and above Crafty, etc. It's rating is high 2600's.

Re:Chessmaster?

[Portfolio]

Funny, but true! Why do you think Deep Blue was dismantled after beating Kasparov? Because to IBM, there was nothing more to gain, and everything to risk. The same goes for most publishers of commercial computer chess programs. They only compete if they have a better-than-average chance to get that magic sticker on their shrink-wrapped box. In this particular instance (CCT4), the tournament doesn't yet have the prestige of the existing computer tournament cycles. Many of the commercials aren't bothering to compete for that reason (nothing to gain, risk to lose). Ian

Re:Chessmaster?

[AlmostDecent]

Almost all the commercials are participating. The only ones that aren't are Chessmaster (no doubt because the company just changed hands), Tiger 14, and Rebel. AFAIK, every other one is there. Not to mention experimental versions (such as Hiarcs 8) and programs that can compete with commercials (Ferret and Yace for example).

Bobby Fisher

[Anonymous Coward]

I would love to see a computer beat Bobby Fisher! Why? Because they never will.

Re:Bobby Fisher

[TMacPhail]

I am not entirely sure about this but I think it is Gary Kasperov who is currently believed to be the better player. Feel free to let me know if I am wrong.

Re:Bobby Fisher

[phantumstranger]

Kasparov is the No. 1 rated player in the world right now and has been for some time but alas, he's never played Fischer (at least in Tourney / Rated play). The thing that always gets me is that Fischer hasn't played rated tourneyt chess in over a decade and he's STILL rated third in the world by the governing body.

I wouldn't say that Kasparov is a better player, but he is rated higher.

Re:Bobby Fisher

[Anonymous Coward]

I don't need my so-called advisors, to tell me I'm more or less out of my mind.

Now go out and get me my chess-playing second. In 24 hours we begin....That is if you want....to....win.

Re:Bobby Fisher

[TheVet]

Chess uses the ELO system for rating players. As per this system, a players new ratings is dependant on their old rating and the rating of their opponent and the result of the match between them.

If a player does not play any matches at all, the rating does not change. So that list can be considered to be an all-time chess player ranking.

FIDE also has a list of current world top players as well as a 32 best players. Not exactly sure what the criteria for the best 32 players is though.

Cheers,
Vivek

Re:Bobby Fisher

[nomadic]

Most people probably consider Kasparov the best at the moment, but whether Kasparov-in-his-prime could beat Fischer-in-his-prime is very hotly debated.

Re:Bobby Fisher

[CommanderTaco]

i love how his birthdate is the only one not listed... they should have put in ???? so he could be like those fighters with "mysterious backgrounds" in any boxing/fighting video game.

USCL

[Tuxinatorium]

USCL is better than ICC, and free for all US Chess Federation members.

Related

[phantumstranger]

There were plans to hold The World's Largest chess tournament ever (via the 'Net but the record would go beyond "just a 'Net record"). The event has been put on hold due to "The present economic situation and dramatic turn down of internet sales in the aftermath of September 11."

More details are at the site and at the FIDE's network site (Fédération Internationale des Échecs).

As far as this tournament is concerened, I welcome it entirely and enthusiastically. Finally there will be a way for the greatest chess programmers (in theory) to be under the "same roof" and possibly get together to swap secrets so that the mid-level bots on-line could actually dish out something other than four variations and stumble the rest of the way through.

And to any players on /. that are also on USCL drop me an email through my link and we'll see if we can get together for some games.

See you on board :o)

Re:Related

[MtViewGuy]

One thing I've noticed about the participants is that there's a lot of machines running the AMD Athlon or Duron CPU's. Let's see if the programmers an wring out the power of the FPU on the Athlon/Duron to get a winner. :-)

Gnuchess

[damiam]

Why isn't gnuchess in this tournament? I'd love to see how it stacks up to all the other engines.

Re:Gnuchess

[Anonymous Coward]

Why the fuck was this modded down? Twice? As a troll?

Re:Gnuchess

[Anonymous Coward]

Gnuchess 4.x played in the CCT3 and did pretty well. In general I think gnuchess would lose to about 1/2 the field.

Re:Gnuchess

[Choose Wisely]

I would assume it's because it runs under Linux.

Re:Gnuchess

[ctid]

In previous tourneys, gnuchess has been added as an extra to make the number of participants even, as that means that no-one has to sit around with a bye. If we end up with an odd number of participants, I expect that gnuchess will make an appearance.

Kasparov

[(H)elix1]

So if Kasparov operates an IRC client, would that be cheating?

Re:Deep Thought

[CyberDruid]

No need for apologies, the guy who chided you was basically wrong. Deep Thought was what IBM called the first version of Deep Blue. It was later changed (possibly for copyright reasons?) to the much worse name Deep Blue.
Kasparov played his first match against Deep Thought and his second against Deep Blue.

Re:Just your standard alpha-beta window

[CyberDruid]

Chess computers are pretty boring. Every single one uses the standard alpha-beta algorithm, used in most games, with modifications for hashing. The difference comes in the evaluation of the leave positions, which position to "extend" (extensions mean that the position is deemed unstable, so you calculate a bit further), in which order the different moves in a position is evaluated, etc.

Re:Deep Thought

[Anonymous Coward]

No, both matches Kasparov played were against Deep Blue. But you are correct that Deep Thought was IBM's precursor to Deep Blue.

Chess for the Hive Mind

[Tom7]

If you want to play your own game of chess against people all over the internet, check out SICO . People take turns playing a single move in all sorts of wacky variations. It's weird but addicting...

Re:Deep Thought

[Anonymous Coward]

You're probably right...
I remember that there was talk of Deep thought vs Kasparov, but they might have changed the name after the match was announced.
Sorry.

Self moving chess pieces

[Anonymous Coward]

I want this one..it's $149 at J & R Electronics. Back in 1987 I saw something like this in downtown Chicago for $500. I wanna buy this so bad. search for " EXCALIBUR ELECTRONIC 702E Mirage Electronic Chess Game " link pdf manual is here

Re:Deep Thought

[Randall Shane]

Uh, no.

This page from IBM has a timeline of the development of Deep Blue.

Summarizing -- A group of Carnegie-Mellon doctoral students (Feng-hsiung Hsu, Murray Campbell and Thomas Anantharaman) (mostly hardware guys!) built Chiptest in 1985. Special-purpose hardware with a chip design originally loosely based on Hans Berliner's Hitech. Evolving development leads to "Deep Thought" (someone was a Hitchhiker fan) in 1988, Hsu and Campbell joining IBM in 1989, Deep Thought II in '91, Deep Blue in '93, and Deep Blue II in '97.

Deep Blue was not a very aesthetic name, but worth millions and millions to IBM in publicity, you can be sure.

Re:Really?

[CyberDruid]

I can reguraly beat CM8000 and I'm a tentative ~1500+ rated player.

Are you sure about this? My ELO is around 2200 and has been so for a few years. For you non-chessplayers, that means that statistically I should score about twice as well against a 1500-player than Kasparov should score against me (although admittedly the system tends to break down when the difference is that large, but you get the picture). When playing against CM6000 on the championship-level (full power, no takebacks, etc) on my K6-II 450 Mhz, I almost always get the snot kicked out of me. I've managed a few draws but that's it.

I am not saying that you're lying, though. Some people are really good at playing closed positions (Stonewall as white and such) and specialize in beating computers. It just seems unlikely. The CM-engine was even rated #1 at one point (in 1999, I believe) on the SSDF-list (SSDF is the voluntary organization that rates chess programs).

ICC history

[Bremen24601]

It pains me that on a site dedicated to open source that we should entirely ignore the history if ICC. Once there was the Internet Chess Server (ICS) which was free, source could be obtained and all. Then one of the people maintaining the server decided to make it propietary and charge for membership. Of course a splinter group decided they wanted a truly free server and that became the Free Internet Chess Server (www.freechess.org), however their lofty ideals came to an end when they saw others using their ideas and not giving back to the community (GPL does not stipulate you must distribute your software) and since then the version of the server software available to download as not been updated.

Now I don't mean to rant about percieved evils, whats done is done, but for a site dedicated to open source I believe this must be mentioned.

distributed

[spongman]

i'm thinking that the best way to win this thing is to use a distributed algorithm running on a large number of machines somewhat like SETI. obvisouly with the time/bandwidth constraints you'd have to have some efficient way of sending out the move information to your network. maybe you could have a tree-like structure with super-nodes having high-bandwidth connections farming out information to subordinates. maybe the brute-force aproach wouldn't work so well against a 'smarter' single-machine solution, due to the exponential nature of the search domain, but i still think it would be cool to see such an entry in a competition like this.

Re:distributed

[MadAhab]

I'm going to make this one an abbreviation because it won't die: W!IABCOT

Re:We should flood OSDN's mailbox

[Shade, The]

Uh, hello? You're not being /forced/ to use Slashdot, are you?! You're getting this for /free/ for God's sake - how in the hell can you possibly fault CmdrTaco?!

What I want to know is...

[Trepidity]

...why isn't IBM entering?

Re:What I want to know is...

[Randall Shane]

IBM Corporation has absolutely nothing to gain. If they enter some version of Deep Blue II and win, it's because they were expected to. If they draw even a single game, several years (and millions of dollars) of marketing and public hype goes out the window.

Beyond chess...

[tangent3]

Besides computer chess, Contract Bridge has also held its own Computer Bridge tournaments, of which the strongest has been Gibware. Would be interesting to see more different type of AI tournaments.... Maybe a tournament between the smartest Quake 3 or Counter-strike bots...

Human Players?

[RobertFisher]

Does this competition allow for human players? Is there any way for a human to "cheat" and pretend he is a computer, from the standpoint of the competition?

I think it would be interesting to see the results of a surprise "black knight" human player thrown into the mix. (Or perhaps even more interestingly, a human/computer team.) We're at a unique point in computational history -- the best human players can still normally beat out the best computer algorithms, though just _barely_. A decent chess player could probably still take home the prize. In 20 years, however, even the best humans will no longer stand a chance against any reasonably serious chess program.

Bob

Re:Human Players?

[hayne]

Does this competition allow for human players? Is there any way for a human to "cheat" and pretend he is a computer, from the standpoint of the competition?

Sure - if the human can squeeze inside a computer case and still have enough agility to type in the moves! (Best not to use the new iMac for this.)

Re:Human Players?

[dstone]

Sure - if the human can squeeze inside a computer case

No need for the human to be on-site. Anyone within 802.11 (or whatever) range of the stealthly-equipped box would suffice. Or are there wireless lan antenna inspections? ;-)

Rock 'Em Sock 'Em Robots

[xxSOUL_EATERxx]

And so the mighty software chess intellects duke it out in the web for all to see. It is tribute to humynkind's creative impulses that we find such enjoyment in watching our creations interact with one another. As with the television show "Robotwars", the duelling automatons seem to take on lives of their own.

The next expected step will be to combine the two, software intellects with hardware brawn, creating robot minions that do not require human controllers. Of course if we are not careful, the darwinian effect of these artificial gladiators' constant struggle with one another may be to bring about a race of super robot warriors that turn on their creators and exterminate humankind, turning the Earth into a real-life version of the nightmarish Cylon Empire featued in the "Battlestar Galactica" television program.

So we must be careful not to let the cheap thrills we get out of watching robot conflicts get the best of us. We must do all we can to integrate peaceful, loving ideals into software and robot development so that perhaps in the future we will be able to lie in harmony rather than strife with our creations.

Re:Really?

[phantumstranger]

Normally from black I play, if given the option, a tight closed game (closed game based on ..1. d4) from white against humans in play-play games I open with the Grob Attack (1. g4) unless I know the strength of my opponent against obscure opennings to which I fall back on the old faithful (1. e4).

Against computers there are definite ways to play them - look for a book called (by far my favorite book) Why You Lose At Chess (not that you do or that you need it) - for instance, against a human you can generally throw a monkey-wrench into your opponents good position (or at least the psyche of it) by advancing a pawn on the King side.

You don't have that option with machines. The only way to play it out is to play out your openning further than you normally do and not make emotional moves. Not to mention machines being extremely predictable.

As far as my rating goes, I don't play tourney often, actually, I rarely do - school gets in the way. Although it could be and looks like its going to be worse 'cause Chess is starting to get in the way of school again. Ooops.

Seriously, drop me an email so we can get together and playt some. I always look for new strong players.

bad choice of words:

[Xzzy]

> watch the action.

As interesting as chess is, "action" is a pretty piss-poor word to describe the game.
Suspense, maybe. Action, not unless steven segal burst in and sprayed the place down with a machine gun.

Re:bad choice of words:

[Anonymous Coward]

As interesting as chess is, "action" is a pretty piss-poor word to describe the game.

You apparently have not been to Hawkeye and Talpa's school of lightning chess , featuring instruction by such leaders as TheBlob and Woof.

overview of recent man vs machine chess

[limber]

This article at Wired a few months back is an intriguing read on the recent history of attempts to improve chess progams and their performance versus notable humans (such as Gary Kasparov and V Kramnik).

Particularly notable (if you are a Kasparov fan) is the description of how Kasparov was, from a certain perspective, manipulated into a match setup which he could not win (wrt the Deep Blue match a few years back).

For example, he never got to view any of Deep Blue's previous games -- whereas in a human match, any world class grandmaster would certainly have studied his opponents games before hand as preparation.

Secondly, Kasparov didn't actually play the same program through the whole match -- the program was tweaked as the match went along.

This subject is quite fascinating in that some people have historically treated the 'can a computer play better than a human' question as sort of a low-level Turing test milestone.

Re:overview of recent man vs machine chess

[Skuto]

>For example, he never got to view any of Deep
>Blue's previous games -- whereas in a human
>match, any world class grandmaster would
>certainly have studied his opponents games >before hand as preparation.

They barely got the machine assembled and tested before the match. He got no games simply because there weren't any yet!

>Secondly, Kasparov didn't actually play the same >program through the whole match -- the program >was tweaked as the match went along.

Can you imagine telling Kasparov he's not allowed to learn anything from the previous game? It's not because he learns that he becomes a different man.

The situation in the Kramnik-Fritz match is just as bad. They aren't even allowed to fix bugs in the program. Is _that_ fair?

--
GCP

Re:overview of recent man vs machine chess

[bwt]

The real unfair part is that Deep Blue could use its opening book, while Kasparov couldn't. Considering that Kasparov lost the final game by playing a known losing opening move, this literally was the differnece.

If the player has to use only memory for openings, so should the computer.

Re:overview of recent man vs machine chess

[Skuto]

>If the player has to use only memory for
>openings, so should the computer.

Where do you think they store it?

A harddisk is essentially external memory.

--
GCP

Re:overview of recent man vs machine chess

[dvdeug]

The real unfair part is that Deep Blue could use its opening book, while Kasparov couldn't. Considering that Kasparov lost the final game by playing a known losing opening move, this literally was the differnece.

If the player has to use only memory for openings, so should the computer.

Huh? What's the computer equivelent of a human's memory? If it's RAM/ROM, why should it make any difference why it should load it from hard disk or RAM/ROM - it's a difference of cash thrown at the problem.

Kasparov had no excuse for the final game. From what I understand, had he played that game against a human grandmaster, the human would have savaged him as well. Grandmasters don't mess up the opening game, at least not if they want to stay grandmasters. He was rattled - but that's the way grandmasters lose to other humans, too.

Answers to all your questions...

[migstradamus]

Hmm, where to start. My name is Mig Greengard and I run Garry Kasparov's website. I work with Shay Bushinsky, who is one of the programmers of Junior, the current world microcomputer chess champion. Just leaping at a chance to karma whore in my specialty. Let me cruise through the various questions and misperceptions I've seen so far.

This is an online tournament held in the biggest online chessplaying site, the ICC. The games are "60 + 10" time control, meaning each computer gets 60 minutes on its clock and 10 seconds are added for each move. So games can last up to 2.5 hours, tops. If you think this is long, this is what we call "rapid chess." Classical games can last up to seven hours.

Uniform hardware has pretty much been given up. They still distinguish between microcomputer and massive machines like those at NASA and Deep Blue, but everything is pretty much wide open these days. The programmers try to get the best hardware they can and usually know very well which platform is best for their program. (There WERE hardware chess accelerator cards, by the way. Back in the 80s when RISC and dedicated chess processors had better cost/chess performance ratios than CPUs. This hasn't been true since the Pentium, although various "Deep Blue on a chip" initiatives exist, including one by a member of the DB team.)

Anyone with a Slashdot account automatically forfeits the ability to call anyone else a nerd.

Move lists and online replay are both available on the site in the original post and at the ICC. Move lists are called "PGN" (portable (or player) game notation") which is an ASCII format used in databases but can be printed out and read easily if you know algabraic chess notation. Online java game viewer applets are quite common.

Both Shannon and Turing spent quite a lot of time on chess algorithms. Shannon actually wrote the first chess program before a computer existed. He 'ran' the program using slips of paper and generated moves this way.

The chess programming breakdown already posted is pretty good. The key concept these days is brute force speed versus knowledge. 20 years ago most programmers thought you needed to make the thing somehow think like a human because the brute force method was so slow. Intel and Moore won. The "fast searchers" now dominate thanks to the minimax algorithm. It just looks at one line after another and counts the beans to rapidly prune. Programs differ to an extreme degree in the amount of knowledge they apply. (HIARCS, for example, is one of the few "slow" programs at the top. It applies a lot of knowledge and looks at maybe 1% of the number of positions the fast programs like Fritz and Junior check.) A top level program, and the top 5-8 are roughly equal at a given time, will look at over one million positions per second. This sounds like a lot (well, it is a lot), but it only puts the program at a level equal to a top 100 level player at a classical time control. (At faster time controls, particularly blitz games of just minutes per side, computers are lethal. Humans just can't play mistake-free chess at that speed.) A program will look six-eight moves deep on the average, but extension will dive deeply into promising or unclear lines, sometimes up to 20 moves in a middlegame position.

Those who think chess is solvable should speak only theoretically. The number of positions is one of those great "million times the number of stars times the grains of sand in the world" numbers. The current method of tree and pruning adds less than one full move of search depth when you double processing power (node count). So the diminishing returns are very much here. The game of go is even worse for comps. Top programs still can't touch the human masters. Back-solving chess using massive databases starting with just a few pieces has had a big impact on computer chess in the past decade. Invented by Ken Thompson (yes, that Ken Thompson), endgame tablebases can now play any combination of five pieces (and many combinations of six) perfectly. This leads to humorous situations of a computer making optically stupid moves to reach a tablebase position it knows for sure is a mathematical win. (Tablebases allow the once-fantastical announcements of things like "checkmate in 45 moves.")

Most of the top commercial programs ARE playing in this event, but most people, particularly chess-ignorant Americans, only know Chessmaster. Fritz, Junior, HIARCS, and Shredder are all top commercial programs. In the chess world, Fritz is almost synonymous with chess program. Chessmaster has a very strong engine (called The King) by a well-known Dutch programmer. Various versions of The King have participated in these competitions and done just fine. Chessmaster has no reason to put its name brand on the line in these bloodbaths. An open tournament like this of only 11 rounds is not at all scientific, for one, but there mostly it's that since all these programs are so strong the power of the engine really isn't the most relevant thing when an amateur buys a chess program. Features like training materials, game databases, GUI, and graphics are much more relevant. Any decent program will kill you on even a low level unless you are an expert.

There are dozens of places to play online, and most of them have computer players as well. KasparovChess has multiple versions of the champion program Junior running and a new one generates when someone starts a game with one so you can always give it a try. (It's a dumbed-down version or it wouldn't be much fun.) The sites with the most players are, inevitably, Yahoo! and MSN. Their software and community suck, of course. Location, location, location. Of the specialist sites, the ICC, chess.net, and KasparovChess.com (my site, as disclosed above) are the largest and best. They have downloadable client software and administrated communities as well as live events, lessons, etc.

There have been many attempts at the holy grail of a massive online tournament. The biggest problem is simply cheating using these programs we're talking about. I could go on for a few dozen pages about methods and countermethods for catching cheats, but basically it's impossible at the end of the day. Don't get me started. KasparovChess hosted the first super-tournament to be played online, in the beginning of 2000. We had human observers with each Grandmaster, all over the world. We also hosted the largest online tournament so far, the world school chess championships. Thousands of kids from hundreds of schools around the world played. (Gotta trust the kids and teachers, right? Right? Actually there were several accusations made, but no decent cases.)

Yes, the ICC used to be free, and that free internet chess server (FICS) is still alive and well, although it is rapidly losing market share. There was a long and bitter battle about that split and the use of the FICS kernel, which is the foundation of just about every chess playing site in the world.

We cover top computer chess events, of which this one really isn't, but if you want to browse around some start here, at the last world championship. WMCCC

It sounds funny, but in the computer championships they have to play face to face and the programmer himself has to make the moves. The worry, of course, is HUMAN cheating, that is, a strong human helping the computer in an online event. The wisdom of a human Grandmaster combined with the accuracy of a computer program would be a devastating combination. (They have competitions of this, with GMs using computers while they play. It's called 'advanced chess' and was introduced by Kasparov. It's interesting, but not always dramatically superior quality chess.)

You can also stop by and play for free, either with an account and a rating or as a guest. We have a java applet if you don't want to download and install. We also have a lot of "learn to play" materials if you are one of the sad crowd that think it's just another board game.

Saludos, Mig

Re:Answers to all your questions...

[Anonymous Coward]

No linux client on kasparov.com, what gives?!?

Re:Answers to all your questions...

[Choose Wisely]

I can imagine that they don't have one because there's little future for it. I've been evaluating Linux's capabilities in a variety of environments, and I just don't see it.

Re:Answers to all your questions...

[Alsee]

Back-solving chess using massive databases starting with just a few pieces ... (Tablebases allow the once-fantastical announcements of things like "checkmate in 45 moves.")

Chess has one flawed rule. 50 moves without a pawn move or a capture is declared a draw. These end-game tables have proven that there are winning positions that require more than 50 moves to force checkmate.

IIRC, King vs King + Bishop + Knight is one such situation. If you play chess, try it out some time. It *IS* possible to force a mate, but it requires perfect acrobatics and a lot of moves to pull it off.

-

Re:Answers to all your questions...

[FFriedel]

Hello Michael,

I have some comments. You write:

"Both Shannon and Turing spent quite a lot of time on chess algorithms. Shannon actually wrote the first chess program before a computer existed. He 'ran' the program using slips of paper and generated moves this way."

Actually it was Alan Turing, who wrote and operated the "paper machine" -- he played the role of a human CPU. A brief history of computer chess, including the game the poor man played, is available here.

"The chess programming breakdown already posted is pretty good. The key concept these days is brute force speed versus knowledge. 20 years ago most programmers thought you needed to make the thing somehow think like a human because the brute force method was so slow. Intel and Moore won. The "fast searchers" now dominate thanks to the minimax algorithm. It just looks at one line after another and counts the beans to rapidly prune. Programs differ to an extreme degree in the amount of knowledge they apply. (HIARCS, for example, is one of the few "slow" programs at the top. It applies a lot of knowledge and looks at maybe 1% of the number of positions the fast programs like Fritz and Junior check.)"

It's more like 20%. On a 666 MHz Pentium this is the speed (in thousands of positions per second) of the current top programs:

Fritz7: 300 kN/s
Fritz6: 450 kN/s
Fritz5: 520 kN/s
Shredder: 160 kN/s
Junior7: 250-435 kN/s
Tiger: 135 kN/s
Hiarcs7: 65 kN/s

Note that Fritz7 has slowed down over the years. This is because it now has a lot of general chess knowledge built in. But you cannot measure knowledge by lack of speed. Fritz7 has more knowledge than Hiarcs 7, which is a number of years old. In fact it has more chess knowledge than any other top program available today.

"Those who think chess is solvable should speak only theoretically. The number of positions is one of those great "million times the number of stars times the grains of sand in the world" numbers."

Even the number of elementary particles in the universe (10^80) is a trivially small number, silly and insignificant compared to the number of possible games up to move 40 (10^112). But the number of unique positions that can occur on a chessboard is much smaller: 10^40 (just as the number of different words in a language is much smaller than the number of potential messages that can be generated from them). These can be theoretically solved using the Thompson back-solving method you mention. But storing the results would require the matter contained in millions of galaxies, so the game is unsolvable for all practical purposes. Just imagine what Greenpeace would say if they discovered we were dismantling millions of galaxies just to store chess!

The last part of your posting seems to have been cut off. Pity.

PS: For the others: I'm Frederic Friedel and part of the Fritz team.

Re:Answers to all your questions...

[AlmostDecent]

Note that Fritz7 has slowed down over the years. This is because it now has a lot of general chess knowledge built in. But you cannot measure knowledge by lack of speed. Fritz7 has more knowledge than Hiarcs 7, which is a number of years old. In fact it has more chess knowledge than any other top program available today. How can you affirm that last phrase? Can you truly affirm it has more knowledge than all of the following programs (for example)?: Shredder6 Junior7 Tiger14 RebelCentury4

Re:Answers to all your questions...

[Anonymous Coward]

>. But the number of unique positions that can occur on a chessboard is much smaller: 10^40 (just as the number of different words in a language is much smaller than the number of potential messages that can be generated from them)

This is not strictly true. A position is not created in a vaccum. It is generated from a game. The path taken to a position is a factor. Mainly due to the fifty move rule. And the possible treefold repetition.

Re:Answers to all your questions...

[Anonymous Coward]

Hello,

This is Vincent Diepeveen.

Programmer from DIEP, not to confuse with
Deep Blue. it's better because it has most
chessknowledge inside it and newer algorithms
(which is true for all of todays software).

Of course from the speed that fritz runs at,
like 1.x million nodes a second on a dual P3,
you already see it has way less knowledge
than DIEP which at a fast
dual K7 MP 1.2Ghz DDR ram
machine as benchmarked at
www.aceshardware.com gets about 120k

Don't believe Frederic Friedel. He knows
nothing from computerchess. He is manager
of the program Fritz. So he doesn't know
anything what knowledge is inside. He has
no access to the source code of it.

Obviously Fritz is NOT worlds most knowledgeable
program. Deep Blue for sure had more than Fritz,
though this is a close match.

Hiarcs for sure has more than fritz and deepblue
added together.

Diep has most of them all. Reason: i am
FIDE recognized master in Chess. The
programmers from Fritz and Hiarcs are real
genius guys, but obviously good programmers.

Nowadays DIEP is doing better and better. Same
is true for so called 'amateurs' like
Lambchop. Beating at a single cpu 450Mhz PII
easily a 512 processor Cray machine (Zugzwang).

The examples are plenty here. Not so many
'knowledgeable' programs get a million nodes
a second.

Please take this posting from mr Friedel with
a salt of grain he is just trying to get Fritz
more popular.

Vincent Diepeveen
diep @ xs4all.nl

Re:Answers to all your questions...

[Anonymous Coward]

Written by Vincent Diepeveen,
programmer from the chessprogram DIEP
and able to give an objective viewpoint here
as i'm not involved in the company
chessbase which sells basically fritz:

Frans Morsch (programmer from fritz)
has not given official statements
why his program slowed down, but a FIDE chess
master like me can directly see it doesn't know
much from bad/good bishops which older versions
handled better.

Also a statement from him is that fritz is
bitboards nowadays. Crafty which is in
specint2000 and a true bitboard program is
at 32 bits processors, especially the P4,
way slower than it is on 64 bits processors.

This means that the slowdown from Fritz is
probably because it has been converted to
bitboards.

nevertheless whatever gets said Fritz is hell
slower than Shredder. Obviously this is
knowledge. Hiarcs, DIEP, and many other programs
are *factors* slower despite years of work
onto it. That fritz is written in assembly
doesn't explain why it is so much faster, it
is obviously having less knowledge than
these programs.

In past times and still today the commercial
way to sell fritz is : "it learns by searching
deeper than other programs". Never the focus
was upon its knowledge. The statement from
Friedel is unexplainable other than that it
was a cheap throw to sell more of fritz.

Best regards,
Vincent Diepeveen
diep @ xs4all.nl

Re:Answers to all your questions...

[Anonymous Coward]

Nice post, Mig. Only one quibble -- it was Alan Turing who executed his chess program on paper, not Claude Shannon.

CCC reader :-)

OT: mildly pedantic nitpicking

[Uberminky]

You're completely right -- more optimal algorithms will beat the less optimal ones in this game of chess, probably.

Just one minor nitpick, regarding your comparison of using the bubblesort and the quicksort...

>Quick sort will always win, hands down, because it
>is the far superior algorithm.

I know what you mean by this, but that particular sentence isn't technically correct. There are in fact real occurrences (more common than we tend to realize, I think) when the bubblesort is in fact the superior algorithm. In certain situations involving semi-sorted data, it's hard to beat a bubblesort. Remember, an O(n) algorithm may only beat an O(n^987293487) algorithm after some particular cutoff point, which *could* be effectively infinite (the age of the universe, say) in some cases.

Anyway. Carry on, I just had to say something..

Off topic, sorta...

[adlam.bor]

Does Hemos really have hemorroids? I was going to switch teams for that guy, but if he's got hemorroids, I probably shouldn't bother. My last girlfriend gave me the clap, so, you know, I'm not into going down that road again, even for a hot stud like Hemos.

I'm not otherwise gay, though. Not that there's anything wrong with that.

Learning chess progs

[Anonymous Coward]

I was recently looking for a customizable chess program which learns. My idea was to have the computer play itself, over and over again, after each game changing the attributes of each of the players(E.G. attacker/defender, peice values etc.). It would result in a very smart program after a couple months of processor time dedicated to it(as a screensaver)..

Re:Learning chess progs

[migstradamus]

There have been many experiments in learning programs and most of today's top programs have at least a limited form of this.

Mostly it is simple database modification. Programs play the openings (the first 10-20 moves, usually) from massive databases of hundreds of thousands of games (human games) and variations. This is called the opening book. As bizarre as it might sound, chess programs don't usually 'think' at all in the first dozen moves or so; they simply play what's recommended in their book of human games. (Which sometimes leads to freaky events.)

When a program with book learning loses a game, or even gets a very negative evaluation during it, it will downgrade the evaluation of that opening line in it's book, so it won't play it again. This is why you can't just repeat an entire winning game against program again and again. (This is very hard to do even if the program doesn't have book learning. The timing has to be perfect and they usually have some randomizing algorythm either in the book, the engine, or both.)

Having an engine play endlessly against itself to learn and improve works to a certain extent. But remember that you run into a serious time factor. If those are two hour games, say, the quality of the moves will be lower than when the program plays a four-hour game in a tournament. So something it put down as good may turn out to be bad. And at longer time controls you'd need years to produce the quantity of checked variations to produce something practically useful.

But programmers do do what you say to test and tweak new versions. If your new beta isn't beating your old gold you need to find out why. Remember, however, that this doesn't necessarily produce a program that is much stronger overall, but one that is stronger than the other one. And when you increase the scope by introducing other engines and versions it again becomes very time-consuming.

This is why they use test suites of chess problems and just check to see which version scores best.

Most of the top programmers work in conjunction with professional players (Grandmasters) to 'tune' their opening books. This is not only weeding out bad lines but creating a book that will help the program get positions that it plays well. Many openings played by Grandmasters are completely incomprehensible to programs, while the comps play certain types of positions better than any human ever could.

Saludos, Mig

Re:Learning chess progs

[Anonymous Coward]

1. Why have it play itself to initialize the values? Go grab a library of previously played chess games, and initialize the program as if it were playing those games. Should save a lot of initial computation.

2. Probably there's a lot of transient conditions on the board that can't be captured with attack/defend, piece values, etc. I smell a large database in there, if you really want "a very smart program".

3. I don't play chess and I've never written a chess program, so I'm probably full of shit :) :). Just some observations and brainstorming, since this /. article had me thinking about it if I were to write one.

Re:Learning chess progs

[AlmostDecent]

Your reply dealt mostly with Opening Book learning which is only a part of the equation. I think the original poster had in mind something more along the lines of neural network programs such as used in backgammon and fathered by Gerald Tesauro (see his paper at http://www.research.ibm.com/massive/tdl.html). There have been efforts done to have programs adjust their own evaluation weights (values for each piece of knowledge), hoping to arrive at some perfect balance. The success of this has varied a great deal. One of the problems could very well be that the quantity of games was insufficient, since as can be seen in Tesauro's results, his first version of TD-Gammon was the result of 300,000 games, and his last from 1.5 million. Another problem is simply in what knowledge is included. You can have the program play itself forever, but if it doesn't know what a doubled pawn is, or take special cases into consideration, the weights will never work. Today's programs try to achieve a fine balance between the most knowledge that is *practical* with speed and depths achieved. The reason (I realize you know this Mig) is that too much knowledge can slow the program down so much that this knowledge cannot compensate the shallow depth reached. In other words, understanding the position like a World Champion won't make up for the fact that it can't see beyond its nose. Of course seeing 20 moves ahead but clueless is no better. Deep Blue, which has often been touted as being a very ignorant program, really wasn't and most likely suffered from a severe imbalance in its weights as Hsu (the author) said it had no less than 6000(!) individual elements of chess knowledge, which no matter how you look at it is loads more than any program today. DB could afford it, since the knowledge didn't slow it down any. In comparison, Crafty, a top freeware program written by Dr. Robert Hyatt, and not considered ignorant by any means had a little over 150 pieces of knowledge a couple of versions ago. Those interested can download the source-code at Hyatt's FTP site at ftp.cis.uab.edu/pub/hyatt Hsu used some automatic learning process to try to finish fine-tuning the evaluation weights, but considering that there were reports off debugging DURING the match, it seems obvious that it was very far from sufficient. It's not unlikely that had the DB team spent one year JUST fine-tuning that eval, without making any other changes, the program would have been enormously stronger, but to be fair, that's only speculation.

Albert Silver

Re:Learning chess progs

[migstradamus]

Hello there. The biggest specific eval problem programs have right now is that of 'closed' positions. The strategies involved when there is a locked center are so distinct from when the center of the board is open that many of your evals much actually change if your program is going to make decent moves in these positions. You almost need three programs. (Multi-engine programs are common, but knowing when to switch is the tricky part.)

All the knowledge you put in is general. Programs value bishops over knights, but in many specific positions, knights will be stronger. A master knows this, a program has a very hard time recognizing the patterns that make this true. (And then recognizing when they are no longer present. The next step is then to realize that the other player can create these conditions. This is why humans still win regularly.)

This is why databases tuning is practical, but trying to find a perfect eval is not. The weights in the eval have to change dramatically based on structure, so a perfect program would be able to do this. No matter what the best average static eval values come out to be, they will never produce a perfect eval compared to a human or program that can adjust on the fly.

Most of Deep Blue's tweaks during the match were more to keep Kasparov on his heels than to actually fix something they really thought was wrong. There is no way you spend years on an eval with Grandmaster consultants (not weak ones) and then decide after one game there is something that needs to be changed. But professional chessplayers survive on analyzing their opponents, and Kasparov basically played a different opponent each day, which wasn't exactly kosher. But don't get me started on that, either.

There is still a great deal of debate whether or not Deep Blue was a stronger chessplayer than the top PC programs are now. Its potential was of course enormous, but various advances have made the current generation very strong. Deep Blue played so few publicly available games that there is no way to objectively point to a move or a game and say that a current program wouldn't have done as well or better. This isn't helped by how Kasparov played absolutely horribly during most of the games.

Mig

This fellow is just a nobody karma whore...

[Anonymous Coward]

I work over in IT at kasparovchess.com (almost 90% Windows, BTW) and, while most of what this fellow says sounds technically correct, some of it is just blantantly pulled out of his ass. I admit I don't know everyone in the co. but I think he must just be some enthusiast. I could be wrong since I mainly manage backups of the systems but my gut is screaming "bullshit".

Re:This fellow is just a nobody karma whore...

[dstone]

my gut is screaming "bullshit"

Your gut, Anonymous Coward who claims to work at KasparovChess.com, is wrong.

A very effortless web search seems to indicate that Mig is indeed the Editor-in-Chief (and possibly a VP) of KasparovChess.com.
here
And from the horse's mouth...
here

It's one thing to post out of ignorance and laziness on /. It's another to not even read the website of your OWN COMPANY. Pull your head out of the sand and stop swapping the backup tapes long enough to read your own website, buddy!

Re:This fellow is just a nobody karma whore...

[migstradamus]

Don't sweat it, I'm used to anonymous loons. (This one certainly doesn't work for us; our technical staff is Israeli and they all know me quite well. I worked there on the site design for seven months pre-launch.) I still cruise by the chess groups in the Usenet but am inevitably flamed as having gone over to the dark side for working with Kasparov. (I used to just write columns in my spare time on several sites.)

I'm also 'vice-president of content,' but that's just a typical late-20th-century dotcom title. Ahh, back when everyone was at least a VP. If ya don't believe me I'll mention /. in my next editorial...

Re:This fellow is just a nobody karma whore...

[Anonymous Coward]

Do not support Israeli apartheid by helping their economy. Boycott Israel.

Re:This fellow is just a nobody karma whore...

[DaEvOsH]

These darn Anonymous Cowards..... heh :) they wont miss a thing!

I did both

[kajoob]

I played football in college and I was also in the chess club. So eat that McFly. I guess I should have kicked my own ass?

Article in Wired Magazine

[MavEtJu]

Wired had an article about computer & chess, computers & humans & chess, computers & humans & chess & cheating in the October 2001 issue:

This time it's personal

subheader: Humankind battles to reclaim the chess-playing championship of the world.

Re:We should flood OSDN's mailbox

[prizzznecious]

..While we get the content for free, Slashdot is not a free service. It just so happens that our contribution is not directly pecuniary.

Distributed Chess?

[Hektor_Troy]

I can imagine the spam already:
"Now YOU can help defeat the chess WORLD CHAMPION. All you need to do, is install this little program, send 5 US$ to this account number: Denmark 7656-3924414, juggle three roasted chickens and a frozen turkey. If YOUR computer is the one, to come up with the winning move, you will get ONE FREE TRIP to PARIS, France*.

So, go download the program, by clicking on this link, and YOU COULD WIN not only A FREE TRIP TO PARIS, but also A FREE PENIS ENLARGEMENT by looking at erotic pictures.

*only elligible for people living on Champs Elysse Paris, France"

Opening strategy against computers?

[lines]

I've heard that the best openings to play against computers are the ones that are positional in nature instead of tactical. That is, computers are clumsy when it comes to general assessments of the board, whereas they are better at direct attack and defense. So human chess adepts generally avoid these tactical situations. Additionally, when chess adepts play computers, they tend to deviate from well-known or standard opening lines to get the computer "out of book" as soon as possible.

I wonder, though, if there are any particular opening strategies when computers play each other, as opposed to human v computer? It seems to me that chess programs with good opening books would almost never fall into well-documented opening traps like the one that claimed Kasparov in his losing match against Deeper Blue. Do computers stick to the tried and true main lines when playing against each other, or would employing opening "novelties" work well?

Re:Opening strategy against computers?

[ctid]

My program is participating. What I do is to go through all the games it has played recently at ICC and try to determine which openings it seems to play sensibly. I have a two-level opening book. The "big" book has a load of high-rated GM games in it. The "preferred" book is the list of opening lines I want PostModernist to play.

For a commercial opponent, I look for games my program has won against it (very few and far between) and try to get it to play the same lines.

I don't do that for other amateur entrants, although my normal "preferred" book will often include recent novelties to see if PM can handle them.

Re:Opening strategy against computers?

[Portfolio]

Good question.

Now that computers are starting to plateau off in strength, more game results are coming down to the quality of the opening book (just like in real Grandmaster tournaments). Here the commercial programs have an edge, with a person paid to tailor an opening book which is 1) suited to the style of the program, and 2) lays traps for all the other chess programs!

Yes, they do tailor books for computer competitions, and there have been numerous upsets due to a stronger program falling into the opening trap of a weaker program. For instance, many of the programs which play on the internet chess servers (e.g. crafty) normally use a very wide book to keep their games entertaining. They switch to narrower less risky books for tournaments.

There are a number of efforts at automating the process of creating an opening book, but the results have been mediocre.

Also, getting out of book is not the weapon it used to be! Programs are strong enough now to improvise well even in the opening. (This was one of the things which killed Kasparov in his last match with Deep Blue.)

However, outside of their books full of rote opening moves, most programs don't have opening specific knowledge, such as knowing about certain thematic sacrifices and plans in particular openings. For example, a computer out of its book in the Sicilian Dragon will not make the thematic queenside RxN sacrifice.

Another problem with opening preparation against computers, compared with humans, is that they tend to play a wider range of openings. You might prepare a trap in a particular opening line, yet only have a 0.1% chance of getting to play it.

Ian

Re:Opening strategy against computers?

[lines]

My program [PostModernist] is participating. What I do is to go through all the games it has played recently at ICC and try to determine which openings it seems to play sensibly.

This makes me wonder whether computers could refine their own opening lines eventually. Maybe you could write a chess program called MetaPostModernist to do the job =) (Actually, that sounds more like a font than a program title.)

Re:Opening strategy against computers?

[lines]

Good question.

Now that computers are starting to plateau off in strength, more game results are coming down to the quality of the opening book (just like in real Grandmaster tournaments)....

I wonder what quantum computing (which i suppose might be the next major plateau in processing power) will do to the world of chess -- computer v human or otherwise. Personally, I know that I lost all interest in playing checkers when I heard that Chinook beat just about every human master there was. (A little irrational, I know.) On the other hand, if Deeper Blue was still around, I'm sure there are a lot of Grandmasters that could win games against it.

Oh, well. There's always Go...

There are a number of efforts at automating the process of creating an opening book, but the results have been mediocre....

This is a little disappointing, but perhaps not surprising. What are the main problems here? Is it more a matter of not having enough statistical power to make opening book refinements?

However, outside of their books full of rote opening moves, most programs don't have opening specific knowledge, such as knowing about certain thematic sacrifices and plans in particular openings. For example, a computer out of its book in the Sicilian Dragon will not make the thematic queenside RxN sacrifice....

On the other hand, if the computer knows that the Sicilian Dragon was the opening, maybe during the early middlegame it could always consider that move with a few extra plys. It still smacks of soft AI, but I suppose it's not too far-removed from how humans learn to play chess (memorizing openings, learning themes).

Re:Opening strategy against computers?

[ctid]

:-)

Lots of programs do "learn" which openings they are good at, but mine doesn't yet.

IMPORTANT

[baron000]

IMPORTANT: Please read the whole post

I'm sure many of you are aware of this thread already.

If you are interested in helping against the moderators who have been "editing" the thread, please read this.

Please do not moderate this post down. It is good for the long term, but if you still feel like being someone who denies the horrible truth, give me your best shot. You will help hold all of Slashdot users back in the long term.

For more info, read this piece from an apparently superior news site.

Re:Just your standard alpha-beta window

[Skuto]

Good point. The reason is simply because alpha-beta is relatively simple and works so damn well.

It's not very nice to spend hours and hours developing something new and seeing it get torn apart in the next tournament by much simpler things. There was only one attempt that was moderatrely successfull that I know of, and that was UlyssesCNS, using Parallel Controlled Conspiracy Number Search.

--
GCP

HAL9000 not invited??

[DrD8m]

Why isn't HAL9000 invited? sure will beat them all!

The game of Go

[igomaniac]

&gt The game of go is even worse for comps. Top
&gt programs still can't touch the human masters.

I don't think the writer appreciates just how different the situation is for go. The top programs can't beat a relative beginner, while a professional player can pass 25 times in a row and still beat them (Janice Kim vs. Handtalk).

The problem with go is that searching doesn't work for two reasons:

Writing an evaluation function for middle game positions is very very hard

The branching factor (the number of legal moves in a position) is much much higher than in chess

Add to that the fact that there are no easy way of applying opening books to go (the professional players say you can successfully start anywhere on the 19x19 board as long as you stay away from the first and second lines from the edges), and you have a situation where the brute-force approach breaks down completely.

The current top Go programs all try to mimic the human way of playing Go, by applying pattern matches and having expert-system like rules for what to do in each pattern. Of course this fails miserably because you need a whole-board understanding to advance beyond the beginner level.

If you write a Go program that can beat a reasonably strong amateur (1 dan level), you will be a millionare for sure, so get started, go look at "the interactive way to Go" and learn the rules, write a computer player and collect the cash ;-)

Re:The game of Go

[Anonymous Coward]

written by Vincent Diepeveen

the game of GO has a bigger branching factor
than Chess, which means GO programs play
way weaker than the professional GO players.

Do not forget however that in GO not so much
great programmers pushed the level of GO whereas
in chess last 30 years real serious work has
been done. In GO many things get discovered by
the few commercial programmers there are
themselves.

So obviously GO programs if thousands of researchers would have taken a look there would
play also way better than they do now.

Doesn't take away that solving the game is
going to be a much harder task.

On the other hand the start of the game in
GO is of much more important than in other
games, whereas in chess this is not true,
a single shot can ruin you. In go this is
much less likely. Most fights get local
fights and even weak players will see the
threats here sooner than weak players do
in a chessgame.

In chess usually endgame is of much bigger
importance than the openings play. Openings
play is more obvious.

So if somehow strong openings play can get
produced by programs the rest of the game is
a peanut.

Whether this is so easy has to be seen of
course because the first few moves the
branching factor is around 350 theoretical.

Nevertheless GO is very popular in the east
of this world. For europeans/americans this
game is because of its habits (i mean
playing a game without sitting on a chair
but sitting on the ground?) not going to
be popular soon either.

Obviously that means that effort in solving
the game is always going to be less than
other games (except when those get solved).

Not sure I see the point...

[swagr]

One of the biggest problems when watching someone play chess, is that you think you know what play should be made. When actually playing, this often translates to a mistake. i.e. you can't truly understand or appreciate the game unless you are playing, or getting a commentary from someone who knows whats going on. Now Kasparov himself has said that there isn't much point in strong human players playing strong machine players, because the machines will win (they are better). So ultimately, when watching this tournament, no one will really understand any of the moves!

Uhu....

[SageMadHatter]

I seriously doubt you are setting CM8000 to play at it's fullest strength if you are indeed beating it regularly, been a 1500 rated player. Last time I check, CM8000 was rated ~2700

Go, man, go!

[epepke]

The most successful Go programs primarily use pattern-matching, cellular automata, and neural networks. None of them are really very good.

Re:Deep Thought

[AlmostDecent]

You are mistaken. Kasparov played Deep Thought in a 2-game match in 1989 and clobbered it.

Site to learn

[AlmostDecent]

You can find out all you want at Bruce Mroeland's site: http://www.seanet.com/~brucemo/chess.htm He explains a number of the different algorithms and techniques used today, and also provides a simple program, Gerbil, with commented source-code available for you to learn from.