Eco & distributed computing - reader responses

It's not that I deliberately try to do this; it's just my nature. I was always something of a gadfly (which is just a smartass with a slightly higher IQ) even as a kid. I was thrown off of the high school newspaper staff due to my tendency to "stir the pot" and was told that I'd "never amount to anything" as a writer. Pardon me while I pause to snicker before we move on...

I really don't do it deliberately -- but it's always fun when I do, 'cause I love the discussions which follow. I had a feeling that my column on ECO and distributed computing was bound to kick up a fuss. It's been online for just a few hours as I type these words and I already have more than a dozen reader responses in my mailbox. So guess what we're going to look at in this column?

Before we begin, I'll say that I still stand behind everything I wrote in that column; nobody likes a fence-jumper. A computer will never "solve" the game of chess as a forced win for either color. I'll elaborate in my responses (which will appear in italics after each reader's e-mail).

----------

Eco and distributed computing
when the last time i read about man vs machine, and machine win the game, i think that still unfair game, machine will get strong and more strong cause machine is upgrade and upgrade and more than that machine is product from many person, not just one person, and it play against one person GM, that is unfair game, if machine play against five person GM in one game that will be interesting match. And like Garry Kasparov against the world, that will more interesting match. back to your article, well we still don't know if computer will get more speed and more memory capacity to store every best move in next-next years. But i know if that happen it is not posibble to know who will win the game if one thousand GM against one GM. it just similar like a car against one human in running competition. But it will happen if human who create machine is upgrade and more upgrade to create more speed and capacity for computer.

Alexander Newbmon

Interesting letter (thanks for writing!), but it's not the same rant -- you're talking about something completely different here. But I'll put that pot on the backburner; I'll doubtless get around to stirring it at some future time. -- SL

----------

Just an FYI. Numbers beyond octillion -- as in your example of 16,777,216,000,000,000,000,000,000,000,000 -- are called nonillion (followed by decillion, undecillion, duodecillion, tredecillion, quattuordecillion, quindecillion, sexdecillion, septendecillion, octodecillion, novemdecillion, vigintillion, etc.).

This particular number is familiar to anyone who deals with colour with their computers. 16,777,216 is the maximum number of colours that a computer can display using 8 bits for each of the primary colours; 2^24 colours. Your example of 12 moves for both sides is 24 moves total. Because it's 20^24, the result is 2^24 followed by 24 zeroes.

Harvey Patterson

Thank you, Harvey! I really do need to write that down someplace handy, seriously, for the next time I have to say to my lady friend, "This is the millionth/billionth/etc. time we've argued about this" -- because I'd very much like to use far far bigger numbers. *sigh* -- SL

----------

For a long time I have been wondering if it was possible to construct a program that looks at all my prepared variations, saved in one big CB file, and select the ones that are the most important to know based on liklyhood of position arising, sharpness of position ect?

Jim Dickson

That's an interesting question, Jim; thanks for sending it. If there's any stumbling block here it's that identifying "the most important to know" might depend on a program's use of "fuzzy logic" (i.e. using logic that's analog instead of digital) in assimilating and combining the evaluation criteria you mentioned. I think it might be entirely possible to come up with some mathematical evaluation for the difference between a "sharp" and a "quiescent" position (some numerical "line in the sand" between them based on the number of legal moves, the number of possible captures, and maybe the number of squares controlled on the opponent's side of the board).

"Likelihood of position arising" troubles me though, because that depends an awful lot on the specific players involved. For example, if you (as Black) adopt the Petroff Defense against most players, the Cochrane Gambit isn't likely to come up. But if you play the Petroff when I have the White pieces, the Cochrane is a 100% dead certainty.

Now let's expand that. At one point back in the 1990's the Petroff seemed to be fairly popular, based on what I was seeing in state, national, and international chess publications. But among the several dozen people I was playing against, it almost never came up (there were only two guys playing it, and one of those fellows used to mix it in occasionally with other Black defenses he played).

The other interpretation of your "likelihood" criteria deals with transpositional possibilities, and that's certainly much easier to quantify. In fact, another reader mentions it in one of the e-mails below. -- SL

----------

You are overlooking that computer processing power is also increasing exponentially.

Whereas NOW your computer is only seeing 250,000 moves in a second, there is a theory called Moore's Law that says that processing speed is doubling every 12-24 months.

Lets split the difference and say its every 18 months.

1.5 years from now your computer could see 500,000 moves in a second. 3 years 1,000,000 per second, etc... I've attached a spreadsheet showing the increase.

In 129 years, one computer should be able to evaluate 12 moves in one second for every possible move. Add in distributive computing....

Point being, if chess processing speed is exponentially increasing without finite limit and chess has a finite limit of moves. Computers will eventually solve chess.

Frank Myers

Thanks for that e-mail, Frank; actually I didn't overlook it -- I expected somebody to bring Moore's Law into the discussion. I omitted it from my article for a couple of reasons. First, I wanted the column to be something less than book length. Second (and more important), I don't believe in Moore's Law. I read an article someplace a long time ago which made several arguments against Moore's Law holding true past a certain point. While it's definitely true that processing power has increased exponentially over the last couple of decades, the article gave several reason why that tendency won't likely hold true for much longer.

However, you do mention the "infinite" (which I don't believe) nature of Moore's Law in conjunction with the finite (albeit vast) number of chess positions. So I'll certainly cop to the possibility that Moore's may overtake the limited number of chess positions.

But there's one last fly in the ointment (and I probably neglected to mention it in my previous column because my premise is presently unprovable), ergo:

I don't think chess holds a forced win for either player.

Now a bit of explanation may be in order here. We're talking about a forced win here; that from Move One a win is inevitable for either player. It means that, after any White move for example, Black can force a win with a particular defense. Black would require a forced win against every one of the twenty possible White opening moves, no matter what White plays as a second move after any of them.

Flipping the coin, a White forced win would require that his opening move can enforce a win against any of Black's twenty possible responses.

Look at a common occurance in chess -- a player announces mate in three. He'll make a move (usually a check) which will force a particular response from his opponent (i.e. he has just one way to get out of check). Then the first player makes a second move which again forces a particular response, after which the first player mates. All of the second player's moves are forced -- he has absolutely no other options at a particular point. There's the basic definition of "forced".

I honestly don't see how that's possible from Move One. I read somewhere that checkers has been solved, but checkers is a much more restrictive game than is chess. Each piece moves the same way and (when played properly) there's a rule which states that a player who's able to make a capture must do so. Chess is a much "freer" game, in that the only "forcing" requirement is that a player who's able to get out of check must do so. That gives each player much more leeway, especially in the opening, and I honestly can't see how one player can "force" any line of play with his opening move.

So, really, I was having a bit of fun with the whole "distributed computing" thing. You can't solve a problem for which a solution doesn't actually exist. And the whole thing was initially prompted by a prior e-mail in which a reader wanted to use ChessBase/Fritz to extend the analysis of every line published in ECO -- and my initial goal was to illustrate what a daunting (impossible, really) task that would be with present-day hardware/software combinations.

However, in 129 years I'll be a spry 174 years old (and fully intend to still be writing ChessBase Workshop), so we'll check back later and see how well Moore's Law held up. It's possible that I'm wrong about this whole "solvability" thing. -- SL

----------

I enjoyed your column on solving chess. I have to agree that the ultimate truth is out of reach. But the problem becomes more tractable if you allow pruning. When you ask an engine to display its evaluation of, say, four variations at a time when it analyzes a position, often you find only a few candidate moves score within 0.5 pawns of the move the engine calculates to be the best. If you prune away all moves not within a 0.5 pawn evaluation score of the best move, then you won't miss too many brilliant moves (the computers are better than Topalov remember) and your branching factor becomes a more manageable number, perhaps averaging as little as 3 (it would be interesting to see what that number proves to be if tested over a few dozen different games).

If we analyze the best 3 moves per position (instead of 17 in your example) then when the engine analyzes all moves from your example leaf node at move 11 out to move 20 then we get "only" 387,420,489 positions. Fritz can handle that in less than half an hour. Get those 10,000 distributed computers humming and all of ECO would be cooked in less time than a holiday dinner.

Dave Clarke

Thanks for the e-mail Dave! You're absolutely right. But (in life there's always a "but") the e-mail which got this whole ball rolling (not Angelo DePalma's, but the one he was commenting on) was from a reader who wanted to do the whole thing himself on a single machine. And I was just trying to illustrate why that can't be done.

Hey, you've given me more numbers to play with! So let's have an example. ECO has five hundred alphanumeric codes; each has a variable amount of numbered variations (but we'll use "10" as a benchmark/average/median figure). Each of those has a variable amount of numbered footnoted leaf nodes; let's use the example I gave in my previous column and take "18" as a benchmark.

Using your figure of 30 minutes (give or take) to extend the analysis of each position an additional eighteen to twenty ply (nine or ten moves), it would take nine hours to arrive at the extended analysis for all the leaf nodes of that one numbered variation. The rest of the math is easy. Multiply that nine hours by ten (our benchmark for the amount of numbered variations for a particular ECO code) and you get 90 hours to finish off just one ECO code. Multiply that by five hundred ECO codes and you get a total of 45,000 hours to knock off all of ECO.

Now remember that we're talking about a reader who wanted to do all of this by himself on a single machine. Assuming he wants to do this full-time (that's forty to forty-five hours a week for us Yanks), it'll take him a thousand weeks to finish the job. Divide this by 52 weeks a year (assuming no vacations, illnesses, etc.) and it'll take him more than nineteen years to finish the job.

Now I'm really not trying to dissuade him from trying it. If he manages to do it, I won't buy him a beer, I won't buy him a pitcher -- I'll buy him a whole damn keg.

He'll deserve it. And probably need it. -- SL

----------

Thanks for that, I found it most enjoyable.
My one comment / question is this:
Given the exponential increases being achieved in computations by modern supercomputers, how would your conclusions change if at all, when computers CAN calculate those types of positions in minutes rather than aeons? And does your analysis exclude legal moves that result in obvious checkmate in say three moves or less?

Neil

I omitted your last name because your e-mail address indicates that this was written from a business account. Dude, you're on the clock...

I still say that chess isn't solvable as a forced win for either side (see above). As for the analysis question, if there's a leaf node in ECO that results in a forced mate in three, then they should have put that three move line in the danged book.

You know, there are plenty of lines in ECO that end with a mate. It really doesn't change my numbers, though, because I think I undershot the numbers a bit when establishing my benchmarks (see above) -- the time should still come out about the same (or require more time, if anything).

Neil, thanks for writing! -- SL

----------

I think your first argument is invalid, and your second is just a question of scale.

Tree pruning doesn't really matter. Yes, it does if you are trying to map out the whole of chess. But you are not. You are just trying to steer the game towards a winning line. It is OK to prune out a Queen sac line that produces distant - but beyond the event horizon of calculation - benefits, as long as you have a tangible benefit on an alternative line within the event horizon. If this tangible benefit is mate then the other line is irrelevant.

Which brings it down to a question of scale - which leads to your second point.

Yes, your argument is valid if you say we cannot at this time calculate far enough using distributed PCs running Fritz 9. But that doesn't mean that we will never be able to.

Looking at your numerical argument say 20 years ago it would be inconceivable that we could ever build a computer that could look 18 moves ahead. But we have - Hydra. Yes, it does prune, but if it finds a mate down another line then this doesn't matter.

Are we ever going to solve all of chess, or even all ECO variations in the near future? No, probably not. You are right. But still I don't think it is a blind alley. What about taking something like Hydra and analysing a handful of obviously bad or obviously good and straight forward variation in ECO? Could we prove for at least one line that it is without question good or bad? Difficult, but possibly an achievable goal given the right selection of line and enough time. You chose the Ruy Lopez exchange variation, which isn't exactly fair is it - mankind has been struggling with that one since the 16th century!

Martin (no last name given)

Thanks for writing sir. I'm not sure how to reply, and that's my own danged fault for coving two separate (but related) topics in the same column. Mea culpa.

If we're talking about extending ECO's analysis, I agree that tree pruning is irrelevant for the reasons you stated. But if we're talking about trying to solve the game of chess, then tree pruning is absolutely relevant -- if for no other reason, because that Queen sac could either force a mate more quickly or maybe negate the alternative mating line. Remember that we're talking about a forced win here; if the Queen sac leads to viable lines of play that avoid the mate, then a "forcing" line in the alternative variation isn't forced, since the player sacking his Queen has a viable means of avoiding the forced line.

So we'll have to examine every possible option when looking for a forced win in chess. And that means that tree pruning is right out. If one player has a means of escape, then we have to find it, otherwise our forced win isn't "forced" at all.

The choice of opening doesn't matter -- in fact, that's irrelevant, since a forced win means that one player can win no matter what his opponent plays. If you're talking about the ECO analysis question, however, I just picked the Ruy Exchange more or less at random because I'm pretty familiar with it. I could have chosen any opening, really, since the discussion at that point in the column was about the number of leaf nodes in ECO and the amount of time required to analyze them all.

My apologies if I've misunderstood your e-mail; if I've done so it's (as I've said) my own fault for mixing the two topics/examples in my column. -- SL

----------

A few years ago an Italian programmer wrote a program to play connect 4, the prog was called Vallero or something like that -- it’s the Italian word for poison.

So what? Well, this program played VERY differently to it’s rivals:

a)It had NO look ahead search at all
b) It played perfectly winning every game where it had the 1st move

the guy was a maths genius. Instead of trying to write a prog that searched deeper and deeper, he said: Connect 4 must follow mathematical principals. We don’t know what they are but they exist. Eventually he deduced the game by 8 mathematical equations, programmed them into his PC and it plays perfect connect4 -- I’ve got it and I can tell you it beats ANYONE and ANYTHING. Because it’s not a massive number cruncher it can achieve these results even on a humble 286 !!!!

Now I realise chess is FAR more complex. But it is a game of perfect information and squares and symmetry, at least to begin with. I bet you that equations are part of the game. We don’t know them and there may be 100’s of them but I reckon they are there. I bet if we could have an interview with God he’d know what they were. Perhaps then we can begin to move away from alpha beta searching and start looking at the mathematical laws of chess. It might be possible for example to reduce a simple ending into an equation, like K + R V K.

Once that is complete we can move on and expand. Given that there are a finite number of squares and a finite number of movements I bet it’s possible to play the ending K+R V K perfectly without lookahead and without tablebases -- just by maths. The creator of vallero succeeded in doing this with his (relatively) simple problem, despite people telling him it was impossible.

Maybe we can do the same!

Carl Bicknell
London

Carl, thanks for writing! Man, that is so cool, except for the part about an interview with God (which was kind of scary). He'd probably yell at me for smoking, drinking beer, and flirting with the ladies, and then send me off so embarassed that I'd forget all about asking Him about the chess thing. But I still say He'd look just like Johnny Cash.

Ah, but the rest of your letter...

You're talking about using heuristics, "rules of thumb", in lieu of brute-force calcluation. And this Italian fellow is indeed a genius, because these rules of thumb are very often difficult (almost impossible at times) to define and quantify mathematically. He found a way to do it, to boil Connect 4 down to just a few simple rules, and did it so well that the processor speed doesn't really matter (it can process this mere handful of rules quickly, even on a slow machine) -- it's still a buttkicker of a program on an old 286. Man, that's a thing of beauty.

I've mentioned this before in prior columns, but chess programmers have more or less been after the same Holy Grail for over a decade. And this dovetails nicely into the number crunching we did in my previous column. The number of possible chess positions, the number of forks in the road at any given point (which lead to many other similar forks, and so on, exponentially), forced programmers to start thinking outside the box because brute-force calculation just wasn't going to get it anymore (Moore's Law included).

So back in the mid-90's, chess programmers started adding positional heuristics (at least the ones that were mathematically quantifiable) into their chess engines. One enlightened soul, Hiarcs' Mark Uniacke, had been doing it even sooner, by the way. And the results speak for themselves; the playing strength and analytical abilities of commercial chess programs have skyrocketed over the last ten years, somewhat independent of the hardware they're running on (see below). The engines "understand" the game better because of the rules of thumb which have been added to their algorithms. In fact, much of the "buzz" about Fritz9 has been about this very point -- Franz Morsch made a conscious decision to sacrifice much of Fritz' speed in order to provide it with a better understanding of these positional characteristics.

However the processing speed will still play a part, for the exact reasons you mentioned. Chess is indeed more complex than Connect 4, and the heuristics/equations will doubtless number in the hundreds (as you indicated). So there's a tradeoff involved. Programmers use the processor's speed to run more quickly through the long "checklist" of positional heuristics instead of using that speed to calculate deeper variations (as they'd previously done). It's very similar to what that genius guy did with his Connect 4 program.

Will it work? Time will tell, I guess. Meanwhile, Carl, thank you for a really cool e-mail! -- SL

----------

Man, that was fun! I'm going to stop there because I didn't even use all of the mail I've read and three more responses have hit my e-mail box just in the time it's taken me to write this column. We're going to take a "time out" to look at some new ChessBase CD/DVD offerings (a couple of which have been sitting on my desk for a couple of weeks -- my apologies. Sometimes I think that making this a twice-weekly column still wouldn't be enough to cover everything), but we'll come back to this topic in another column or three.

I do enjoy your comments (even the "you're an idiot!" ones because they make me laugh -- it's not like you're telling me anything I don't already know) so keep 'em coming! My e-mail address is at the bottom of this column. Just remember the rules -- if you write, you're providing me permission to quote you. So don't say anything you wouldn't want your boss or your mom to read.

Until next week, have fun!

You can e-mail me with your comments on ChessBase Workshop. All responses will be read, and sending an e-mail to this address grants us permission to use it in a future column. No tech support questions, please.

© 2005, Steven A. Lopez. All rights reserved.