Marvin Minsky and the look-ahead efficiency in chess

[JuLieN]

One of my heroes is Marvin Minsky, and I recently discovered that his class about the Society of Mind was freely available on the MIT's OpenCourseWare website (at this address). So having read this book inside and out, both in french and english, I jumped on the occasion to see the Master himself teach about it. And I came upon a funny anecdote Minsky told about chess and look-ahead. I transcript it here with a bit of context:

17:23: Quite often, somebody says "well, if you're working on common sense, why don't you apply it to legal reasoning?" I never felt that attractive because they'd be no way to tell when you're making progress. (laughers)
18:08: There's a story of a mathematician who wrote a PHD thesis on a certain kind of group that satisfied some conditions and he prove some theorem that any group that satisfies those conditions will also have some other property, like be commutative or something, and this is one of the rare cases when he failed his thesis defense because someone in the audience shown that there weren't any such groups. So although the thesis was correct it wasn't about anything. (laughters) I know: you can never tell if these stories are true.
18:58: I once had a student that was very stubborn and he wrote a very big thesis proving something, and Papert and Shannon and I spent a lot of time on the thesis and discovered that it was a circular argument. He had spent three years on it and we kept telling him to give up. But he finally gave us this document. I only had two PHD students failing that way. Since 1960. So, very rare event. But things like that happen. The student is absolutely convinced. The problem was "under which conditions does look-ahead in a game like chess, if you look further ahead, when do you do better?" In generality you do better and he tried to prove this. And some guy at North-Western recently showed having made games where further ahead you look the worse you do. So the theorem can't be true. But our student didn't know that and we didn't think of building a counter-example. Which is pretty tricky to do... It doesn't matter, because if there were such a game nobody would play it. So it's probably why it wasn't discovered until recently. This game is completely meaningless because you make the rule so just as the look-ahead fails. It requires very intelligent design. That's a good argument for intelligent design: could a world this bad evolve just by accident, or would it need some guidance? (laughters)

This is a transcript from the 17th to 21st minutes of the fourth lecture, available here:
http://ocw.mit.edu/courses/electrical-e ... lecture-4/

So, apart from being interesting and funny, this abstract made me wonder: is there a limit to the gain in strength given by the look-ahead procedure? For example, seeing two plies deep is obviously a huge improvement over seeing only one ply deep, and this improvement is certainly greater than going from 20 plies to 21 plies. But is this improvement geometrical? For example, does looking 20 plies ahead gives the same improvement over looking 10 plies ahead than compared with the improvement from going from 1 ply to two plies? Or do we see a diminution of the improvement because the very nature of chess does that looking 50 plies ahead is about the same as looking 40 plies ahead? (This has to do with the game of chess' internal dynamics).

Of course I'm talking about real plies, not plies made of unsound pruning.

[Don]

One of my heroes is Marvin Minsky, and I recently discovered that his class about the Society of Mind was freely available on the MIT's OpenCourseWare website (at this address). So having read this book inside and out, both in french and english, I jumped on the occasion to see the Master himself teach about it. And I came upon a funny anecdote Minsky told about chess and look-ahead. I transcript it here with a bit of context:

17:23: Quite often, somebody says "well, if you're working on common sense, why don't you apply it to legal reasoning?" I never felt that attractive because they'd be no way to tell when you're making progress. (laughers)
18:08: There's a story of a mathematician who wrote a PHD thesis on a certain kind of group that satisfied some conditions and he prove some theorem that any group that satisfies those conditions will also have some other property, like be commutative or something, and this is one of the rare cases when he failed his thesis defense because someone in the audience shown that there weren't any such groups. So although the thesis was correct it wasn't about anything. (laughters) I know: you can never tell if these stories are true.
18:58: I once had a student that was very stubborn and he wrote a very big thesis proving something, and Papert and Shannon and I spent a lot of time on the thesis and discovered that it was a circular argument. He had spent three years on it and we kept telling him to give up. But he finally gave us this document. I only had two PHD students failing that way. Since 1960. So, very rare event. But things like that happen. The student is absolutely convinced. The problem was "under which conditions does look-ahead in a game like chess, if you look further ahead, when do you do better?" In generality you do better and he tried to prove this. And some guy at North-Western recently showed having made games where further ahead you look the worse you do. So the theorem can't be true. But our student didn't know that and we didn't think of building a counter-example. Which is pretty tricky to do... It doesn't matter, because if there were such a game nobody would play it. So it's probably why it wasn't discovered until recently. This game is completely meaningless because you make the rule so just as the look-ahead fails. It requires very intelligent design. That's a good argument for intelligent design: could a world this bad evolve just by accident, or would it need some guidance? (laughters)

This is a transcript from the 17th to 21st minutes of the fourth lecture, available here:
http://ocw.mit.edu/courses/electrical-e ... lecture-4/

So, apart from being interesting and funny, this abstract made me wonder: is there a limit to the gain in strength given by the look-ahead procedure? For example, seeing two plies deep is obviously a huge improvement over seeing only one ply deep, and this improvement is certainly greater than going from 20 plies to 21 plies. But is this improvement geometrical? For example, does looking 20 plies ahead gives the same improvement over looking 10 plies ahead than compared with the improvement from going from 1 ply to two plies? Or do we see a diminution of the improvement because the very nature of chess does that looking 50 plies ahead is about the same as looking 40 plies ahead? (This has to do with the game of chess' internal dynamics).

Of course I'm talking about real plies, not plies made of unsound pruning.

Each ply of lookahead will improve the strength of a chess program but there are diminishing returns for each additional ply. So I would suspect that a 100 ply search is not much stronger than a 90 ply search.

The big surprise in computer chess, learned over the decades, is that each ply of search is "almost" linear in the additional strength it provides.

The tapering is often attributed to more draws but to me that just means the programs are playing much stronger and thus gradually approaching the game theoretic result which is almost certainly a draw. If Komodo could do 70 ply searches it would be mostly draws against an equivalent strength opponent.

[hgm]

As long as they correctly implement game end (i.e.mate scores in Chess), they should in the end improve as the depth goes to infinity. (That doesn't imply they will play perfect Chess; from tablebases we now that perfect knowledge will actually lead to utterly crappy Chess, when in a drawn position: the program allows itself to be pushed to the brink of defeat without any resistance whatsoever as long as that one miraculous escape will remain available, and stay very far from the win-loss boundary even against a patzer. Like sacrrificing B+2P on the first 3 moves in KBPPKB.)

But it is very easy to make programs that do worse with larger search depth over a limited range of initial depths; you just have to give it faulty evaluation. E.g. with faulty piece values giving it more depth will just make it more clever in finding ways to force the suicidal trade.

So I don't think it is a property of the game. In any game you can have poor evaluation, or near-perfect ones.

[Uri Blass]

But it is very easy to make programs that do worse with larger search depth over a limited range of initial depths; you just have to give it faulty evaluation. E.g. with faulty piece values giving it more depth will just make it more clever in finding ways to force the suicidal trade.

Is it based on testing?

I am not sure if bigger depth is going to get worse results with a poor evaluation(assuming that you evaluate mates correctly).

The point is that the program may calculate that if it sacrifices material that the opponent is forced to capture the opponent with the material advantage can use his material advantage to sacrifice material(another sacrifice that you have to accept) so it may be better to delay the sacrifice and at big depth by delaying the sacrifice again and again it may never practically sacrifice.