My likely highly suspect impression of the game so far:
Black has lost a pawn, but has greatly superior development. White’s pieces are almost all bottled up and undeveloped (and he will have to retreat his lone developed piece, that knight), while Black’s bishops and queen all have open avenues at their disposal.
This is jolly accurate! 
Fortunately for me, it’s still all ‘book’ i.e. known analysis - plus I’ve played this position many times…
Well–this is basically the secret sauce of chess programs, whether you’re talking openings or anything else.
The most obvious stopping point is checkmate, but as we agree this isn’t going to come very early for most openings. So instead we need a fuzzy evaluation function. A very simple one would be to assign a point value to each piece based on its strength. A more sophisticated scheme would take positioning into account, but you don’t want it too complicated, because at a certain point you’d rather spend the processing on looking another move ahead.
As for the number of moves–basically, every program has some pruning algorithm which stops looking if the game is looking too bad (or too good!). It really just depends on the circumstances.
Anyhow, in this respect openings are no different than midgame play. The difference is that, as with endgames, you can have your computer chug away for as long as you want offline and keep the results in a database. This isn’t really any different from opening books, which reflect the accumulated knowledge of millions of human games.
Well, here’s one approach: you let the computer play millions of games against itself (with the opening held constant). However you inject noise into the system so that you don’t get exactly the same game each time. For instance, suppose on each move you rank the “best” moves, but instead of always picking the best you pick the top one 50% of the time, the next one 25% of the time, and so on. Or better yet, you weight the percentages with how strong the moves are (if one move is undeniably the best then you pick it 100% of the time, but if there are two nearly equal ones then you pick 50/50%). At any rate, you get a large variety of games which are for the most part very strong but quite different from each other. If it turns out that the pawn sacrifice indeed confers a positional or other advantage, this should be reflected in the win/loss ratio of the final tally.
I’m sorry, but I still think you don’t see the massive difference between computers analysing openings, playing middlegames and using endgame tablebases.
I know all the stuff you mentioned about programs (e.g. I’ve discussed computer chess programs with their programmers in a World Computer Championship and was one of the first humans to test the tablebase for K+2B v K+N.)
Let me explain why I disagree, point by point:
No kidding!
**Any opening where somebody gets checkmated is not worth analysing **- it’s because of a stupid blunder.
Indeed they do - and the program can make mistakes because of it. But the problem is particularly severe in openings.
Here’s a game I posted earlier:
If you set the parameters for your program’s opening analysis to 8 moves ahead (which is a vast number of positions!), you conclude that this line leads to a win for Black at move 8 - since he’s a piece up.
No! No! No!
Openings are very different from middlegames.
The computer only looks a few moves ahead - now this perfection is enough to get the advantage in a middlegame over a human, but doesn’t tell you enough about which opening moves are best (or even sound.)
For openings, you cannot have your computer chug away for as long as you want offline and keep the results in a database.
Endgames **with just a few pieces **can be analysed by looking at every legal position, compiling a tablebase and then referring to it. (We’ve done 6 pieces and are working on 7.)
It may well be literally impossible to ever construct a tablebase for 32 pieces (i.e. including the opening position) as there may not be enough material in the Universe to hold the data.
‘Chugging away … This isn’t really any different from opening books, which reflect the accumulated knowledge of millions of human games.’
The millions of human games were an **incredibly tiny fraction **of the possible games within the first 10 moves or so.
No human has ever analysed 1.h3 h6 2. h4 h5 , for example. This is just a sample of what a computer would have to analyse - since that position would undoubtedly register as ‘equal’ and therefore to a computer be a potential playable opening!
The only initial moves played regularly by top human players are 1. e4, 1.d4, 1. Nf3 and 1. c4. The other 16 legal first moves are considered inferior. How long would two computers have to run to establish that?
How many games are you going to play?
Remember you need to look at every legal move!
Assume you want to look 10 moves for each side ahead (a reasonable request for establishing which openings are worth playing.)
Allowing for 25 legal moves in a typical position (and I think that’s an underestimate), you’re talking about generating 25 to the power of 20 opening positions.
You then intend to play millions of games from each resulting position?!
I leave it to the SDMB mathematicians to say how much storage you need, let alone how long it would take…
Or, instead of injecting noise, you let the machine learn: Whichever side lost the last time now knows that it must diverge from that previous game at some point, and does so. Maybe it still loses, in which case it knows it has to diverge from both of those games. Maybe it wins, in which case the new losing side knows it now has to diverge. Repeat until the necessary divergences go back into the opening.
We already have extensive analysis, and extensive practical testing. I guess by some of the techniques mentioned you could either replicate or perhaps improve on the current state of chess theory.
What exactly is the claim being made? How much of opening theory are you expecting can be found by these sort of methods, in, say, the next 100 years.
ETA-I actually think you’d be very hard pressed to get close to replicating the current state of theory without telling the computers how to play certain openings.
This seems to be the main point of contention here.
We agree that there are far too many possible games to consider all of them using current computers. Any practical solution must then involve ignoring almost all of them.
So what I suggested is a statistical approach. The trick is in how we sample games. We would like wide coverage in the game space, but on the other hand we want to focus our attention on more likely games–ones where not too many mistakes are made. Of course we can’t know what a mistake is in advance, so instead of eliminating suboptimal moves completely, we weight the possibilities so that we try that move less frequently.
We know for instance that a good “opening” is to play as White (yes, I know I’m abusing the word). Do you not think that we could also discover this via the algorithm I suggested? That among millions of games, with noise injected so that we never have the same game twice, we wouldn’t find that White has the advantage?
Or, for instance, that if instead of a queen, we gave black another rook, that this wouldn’t widen the lead even further? We intuitively know this is true because queens are inherently stronger than rooks, but it’s just a heuristic–in an absolute sense, we still don’t know that Black doesn’t have a forced win. We just have a pretty good intuition that if equal skill players were to play a bunch of games with this change, Black would lose more often than before.
So I suggest that the same is true of openings; that we can come up with a table of openings up to some (small!) number of moves, and for each one come up with a win percentage. There’s no reason to believe they’d all be the same–in fact we know they can’t be due to the fool’s mates.
Now, is this number useful? That I can’t say. It sure seems like at the least, you’d be able to find some duds which aren’t currently known. And maybe you’d find some really nice ones which aren’t currently known. These seem like they’d be especially valuable, since even if they aren’t the very peak of the computer’s metric, they’d likely be unknown to the human opponent and therefore confer an advantage.
That’s a possibility. I like the noise approach because it is potentially less biased: we don’t know that the losing computer lost because of poor heuristics, or because the move was genuinely bad. With a statistical approach there is at least some possibility of sampling games that had a seemingly bad move but actually turned out to be decent (e.g., a gambit).
Even making generous assumptions the possibilities are far too large. Say the search tree is reduced so that there are only 5 moves to consider in each position, and we want to analyse the first 20 full moves of the game (i.e. 40 ply). By analyse I mean, set up the position, let the computer think about it, get an output. This isn’t going to help much, but it seems an easier task than anything so far asked, thus a generous assumption. There are 5^40, or roughly 9x10^27 such positions. To analyse each position in 100 years you would need to analyse roughly 3x10^18 positions per second.
NB: I’m not a mathematician, so feel free to check my numbers.
Except that humans, even without computers, have done a great deal of analysis of openings. Given that computers can play chess as well as the best humans, why can’t they analyze openings (a subset of the problem of chess, after all) just as well as humans, too?
I wonder – does anybody know how many USCF games have been rated in total (say going back to 1950, or earlier)? I would guess that the answer to your question is that humans have spent millions (billions?) of man-hours playing chess. And while chess computers are now better than humans, it still takes them a comparable amount of time for analysis (they can’t beat a grandmaster if given very unfair time controls). So therefore it would take millions (billions?) of cpu hours in order to get anywhere. Even with supercomputers it would take decades, probably centuries (ignoring Moore’s Law) to begin to compete with humans. Is that a fair argument?
Are you responding to the below?
[QUOTE=TATG]
ETA-I actually think you’d be very hard pressed to get close to replicating the current state of theory without telling the computers how to play certain openings.
[/QUOTE]
I have my reasons for saying this, which I will outline in a moment. But I want to make it clear that I am not sure what you, and Dr. Strangelove are arguing for (and you might be arguing for different things).
Is your claim just that computers could replicate, say, in approximate quality and quantity human analysis of openings? Is it more than that? If so, how much more?
The databases certainly have millions of games. Of course the longer ago a game was played the less likely it is to be in a database, but I can’t quantify that.
My speculation (that computers would do it hard on their own) is based on the fact that computers are, in general, relatively weak in the openings, and relatively uncreative. At least, based on past experience, maybe they have improved in that area. Aside from this, the current human+computer analysis style, seems to be quite a lot better than either one alone.
I’m somewhat impressed that up to this point (move 9), it was still a “book” position. How far does it go after 9. Nf3 e4?
I have a question about the state of things. This seems an interesting position. Black has some pawns in awful positions, but has the potential to move his pieces in control of the board. White is up in material but development is almost nil (the only decent thing seems to be the castling potential).
Mosier’s thoughts seem to be on protecting those weak pawns more than pushing for control. Was this his big mistake, or was it more of just a tactical error to allow the response on d4?
My theory of what’s best for Black is an all-out attack, keeping White from gaining any advantage. If the board is controlled, then the pawns take care of themselves. On the other side, what should White do? Build a defense and let Black do its worst, knowing that if the storm is weathered White can prevail? Or try to work against the pawns, making Black worry about having nothing left to protect? I’d imagine that building up the pawns would be what I’d go for here.
Computers are not good at deciding what to ‘ignore’.
Honestly, no! It’s the sheer number of positions that kills you.
Look you mention playing millions of games (I agree it should be easy to make them all different.)
That means you’re either analysing in full about 6 moves from the initial position (where with sensible play White has not established any advantage), or picking a miniscule fraction of opening moves at random.
Computers simply don’t play chess anything like humans.
Humans make judgements, predictions, spot patterns and decide that advantage A (lead in development) outweighs disadvantage B (weak control of the centre.) No computer can do any of this.
Now in endings (currently 6 men or less), computers can generate tablebases and thus ‘play’ perfectly. Of course they’re not actually playing, just looking up an entry on a database.
In middlegames computers are good at churning out all possible positions a few moves ahead (say 5 moves by each side), storing them and sorting them. Their analysis of each resulting position is crude (basically just on material.)
However it’s extremely difficult to look 5 moves ahead for us carbon-based lifeforms, so computers can outplay humans once the position involves fully-developed pieces.
In openings, neither of the above methods is any use.
Tablebases are out and looking just 5 moves ahead from the original position has already been done.
The only major opening innovation recently in the first 5 moves was the Benko Gambit (1. d4 Nf6 2. c4 c5 3. d5 b5!?), where Black sacrifices a pawn for long-term positional pressure down the a+b files.
No computer would ever consider this, since after 5 moves Black is a pawn down.
Opening analysis (‘book’) by humans is based on billions of games.
If someone plays a new move, it soon gets known.
My analysis (based on my previous games) goes:
and now 3 main moves by Black - Bd6 / Bc5 / Qd4.
There are some hair-raising positions resulting from Qd4 in particular!
The Black pawns would be weak in an ending, but we’re a long way from that.
Black has a lead in development and the position is considered to be about equal. (I play it because I have a lot of analysis and most of my opponents have not reached this position before.)
It’s a sharp position. Bd6 develops a piece and defends the attacked pawn. However it’s just too slow.
We’d all like that!
Your only problem is achieving it…
Well, computers are only as good as how we program them. There’s an entire subfield of game AI dealing with game tree pruning; Alpha-beta is one well-known algorithm. The basic idea is that a tree of moves is as bad as the worst move, and so you can ignore subtrees that contain particularly bad moves (such as those that lead to checkmate).
Of course that’s just one example and there are additional subtleties.
I’m not talking about arbitrary openings here–just the simple question of if it’s better to play as White. We know from human game statistics that this is true, and I posited that we could make the same inference via computer-on-computer games.
Upon further research, it turns out that you can:
This is a slightly different experiment than what I suggested, since it pits multiple chess engines against each other (instead of the same one with noise injected), but the basic idea is the same. Note that the 55.4% win rate is very close to that found on human games.
Given this fact, I then suggest that we could perform a similar analysis on openings. Probably someone has already done it and I’m not aware of it.
OK, I accept that some pruning is possible.
I still think it makes little difference to opening analysis because of the vast number of possible positions, plus the tiny chance of an early checkmate.
OK, that percentage does tie up with human expectations.
The experiment above used around 1 million games between computers to confirm that White was slightly better.
It is a **huge leap **from that to analyse every possible opening move and them play many games from each position to establish opening theory.
I make the bold claim that if someone had done it, I would have heard of it. 
Emphasis mine. What does this mean? What does opening analysis consist of here? You can certainly download the databases they have on the CEGT website and extract some data about openings, if you think the fact about white winning percentage is indicative. You could extract a winning percentage for 1.e4, and 1.d4, for instance.
CEGT’s project is genterating rating lists. The experiment was taking something CEGT produced (their avaliable data-bases), and running stats.
As an aside, the computers in those games used opening books.
I think extracting further information from CEGT is interesting, but it has limits. The problem, as you say, is that they are already using opening books. So the data is inherently biased. Maybe 1.e4 works a little better than 1.d4. Is that because it really is better, or because for whatever reason the former happens to have been analyzed slightly more deeply? White v. Black isn’t subject to this problem since chess engines must be equally optimized for both.
So I only suggest that a less biased analysis might uncover something interesting. Maybe it would only serve to reinforce existing theory; maybe it would discover something new and powerful; maybe it would uncover something particularly weak which wasn’t known before. I have no idea, which is why I think an experiment could be interesting.