Since quite a while I'm wondering about the benefits of increasing horizon. First this seems to be quite obvious: An engine which is able to look further down the road is more likely to win the game because it can see traps earlier and therefor can avoid them easier while on the other hand traps placed by it will be seen late by it's opponent, maybe too late.

But then, things seem to get more difficult.

- What about the diminishing marginal utility? Will it shrink down to zero - more and more with each added ply? While on the other hand the expense in terms of calculation time is exploding?

- Will the benefit of another added ply finally go down

If so, would that mean that being a good chess player requires a certain amount of non-knowledge? Or at least a, let's say, a poker face?

But then, things seem to get more difficult.

- What about the diminishing marginal utility? Will it shrink down to zero - more and more with each added ply? While on the other hand the expense in terms of calculation time is exploding?

- Will the benefit of another added ply finally go down

**below**zero? To explain this question I'd like to refer to a remark of some GM I've read or heard somewhere a while ago. I don't know it by heart, but basically the guy said that he is expecting engines to reach a level soon, where it will be harder and harder for a human player to follow their games and to find out the reasons for their moves. Actually they have already reached this level, if you ask me, but anyway: Is it possible that engines will finally paralyze themselves, reacting to some potential thread 30 plies away and being unable to find a useful move, because always there's some refutation somewhere in the far future?If so, would that mean that being a good chess player requires a certain amount of non-knowledge? Or at least a, let's say, a poker face?

Interesting question. To me, the big mystery is the simple question: Why does search work?

I have heard that some weird games were constructed as examples where search will lead to decreased performance. I would be very interested to learn what are the concrete game conditions for search to work.

I have heard that some weird games were constructed as examples where search will lead to decreased performance. I would be very interested to learn what are the concrete game conditions for search to work.

Yes, there is no apriory reason to believe that deeper search leads to stronger moves! In fact we can almost certainly say (at least theoretically) that at some stage the strengt (mesasured in rating) in some sense decrease with search dept. Imagine the "perfect program" that search the whole tree to the very end. Such a program would play chess exactly as a tablebase. It would have an incredible strength in won positions, and would presumable (though though this is less clear, since postponing the mate the longest might not in general lead to the toughest defence agaist a non-perfect opponent) be incredible good in defence. In drawn , balanced positions it would no doubt play at quite low level. 1.g4,d5 2.h4 might hold for white so the program might be as happy with that line as with any other line that "holds". This point is wellknown, however if we evaluate all and positions (so a draw with in a nominal better endgame , is better than a draw in a worse endgame), then maybe the program (with unlimited search) would play extremely well.

I believe that there is an a priori reason to believe that deeper search leads to stronger moves, and it's very simple: the second law of thermodynamics. Deeper search will see a larger number of macrostates (plies) and also a larger number of microstates (positions) in each particular macrostate. This is the natural state of chess--you would have increasing "entropy" with increasing depth possibilities, and thus greater chance for the game to go awry if there isn't some sort of "ordering principle" to keep it from doing so. This "ordering principle" is the search in a strong engine.

Actually the problem is: What is chess really? What does the search really see, when it searches?

Let's assume there were some kind of perfect search algorythm which could see the complete chess, all lines and variations and their outcomes and connections to other lines at once - till the final mate or draw. All that at the same time.

Now, what would this search see? Would it see an incredibly complex labyrinth, but still with doors and connections and exits? In this case everything would be fine, and you are right.

Or would it see a dark trap with only an entrance, but no exits? Because for each possible line and variation there is a refutation somewhere along the line? Doors shut? Connections blocked up? And only our human imperfection makes us believe there were open ways and floors, and possibilities to walk a different route if we find the current one to be a blind alley?

If this would be the case, then the inreasing macro- and microstates could very well lead to blocked engines, if you increase search depth dramatically...

Let's assume there were some kind of perfect search algorythm which could see the complete chess, all lines and variations and their outcomes and connections to other lines at once - till the final mate or draw. All that at the same time.

Now, what would this search see? Would it see an incredibly complex labyrinth, but still with doors and connections and exits? In this case everything would be fine, and you are right.

Or would it see a dark trap with only an entrance, but no exits? Because for each possible line and variation there is a refutation somewhere along the line? Doors shut? Connections blocked up? And only our human imperfection makes us believe there were open ways and floors, and possibilities to walk a different route if we find the current one to be a blind alley?

If this would be the case, then the inreasing macro- and microstates could very well lead to blocked engines, if you increase search depth dramatically...

While your comparison to a thermodynamics is very interesting, I feel inclined to comment: If we need to involve physics to explain why search works, then we have not really yet hit upon the crucial game properties that result in search to work ;-)

Some random babblings:

1) Clearly, evaluation is critical. If we turn the evaluation upside-down, more search would lead us to more effectively find the worst move, and then search leads to decreased performance. Also, if the evaluation scores every position at 0.00, search will be of no difference.

2) OK, so we assume now that the static evaluation is actually a fairly good indicator of the theoretical game state (win/draw/loss). Then I may ask: Why is a depth N+1 search better than a depth N search?

This may seem like an incredible lame question, but the more I think about it, the more in doubt I come about what is actually going on. I can reformulate the question like this:

With a 1-ply search, we can give a static evaluation to all our candidate moves. We can order these evaluations and make the move. Alternatively, we can make a 10-ply mini-max search and order our candidate moves based on this. Then the question becomes: Why does the latter ordering lead to stronger performance than the first ordering?

Some "naive" sub-questions:

a) Is there special going on at depth 10? (The answer would seem to be "no".)

b) Are the static evaluations at depth 10 more precise than the static evaluation at depth 1? (Again, the answer would seem to be "no" or "not relevantly so").

OK, so how come the mini-max tree is useful for us? Perhaps one could say that with this tree, we are guaranteed a certain static evaluation 10 plies from now. What I don't see is how this guarantee can be used to explain why the high-depth ordering is better than the low-depth ordering (remember, nothing special should be going on at depth 10).

Maybe there is a very simple explanation that I am completely missing, but it could also be that the answer to the question is actually not that simple. That's why I would like to learn about the concrete game properties that are required for search to work. We know already one property: Our game is turn-based. Please feel free to expand the list of required properties below :-)

1) Turn-based game.

2) ......

3) ......

Some random babblings:

1) Clearly, evaluation is critical. If we turn the evaluation upside-down, more search would lead us to more effectively find the worst move, and then search leads to decreased performance. Also, if the evaluation scores every position at 0.00, search will be of no difference.

2) OK, so we assume now that the static evaluation is actually a fairly good indicator of the theoretical game state (win/draw/loss). Then I may ask: Why is a depth N+1 search better than a depth N search?

This may seem like an incredible lame question, but the more I think about it, the more in doubt I come about what is actually going on. I can reformulate the question like this:

With a 1-ply search, we can give a static evaluation to all our candidate moves. We can order these evaluations and make the move. Alternatively, we can make a 10-ply mini-max search and order our candidate moves based on this. Then the question becomes: Why does the latter ordering lead to stronger performance than the first ordering?

Some "naive" sub-questions:

a) Is there special going on at depth 10? (The answer would seem to be "no".)

b) Are the static evaluations at depth 10 more precise than the static evaluation at depth 1? (Again, the answer would seem to be "no" or "not relevantly so").

OK, so how come the mini-max tree is useful for us? Perhaps one could say that with this tree, we are guaranteed a certain static evaluation 10 plies from now. What I don't see is how this guarantee can be used to explain why the high-depth ordering is better than the low-depth ordering (remember, nothing special should be going on at depth 10).

Maybe there is a very simple explanation that I am completely missing, but it could also be that the answer to the question is actually not that simple. That's why I would like to learn about the concrete game properties that are required for search to work. We know already one property: Our game is turn-based. Please feel free to expand the list of required properties below :-)

1) Turn-based game.

2) ......

3) ......

Above, I have used the picture of a labyrinth to visualize a chess game. Maybe that is your answer: Imagine being in a labyrinth and you can only see exactly one step ahead, regardless of the direction. So you can move, and you can avoid bumping into walls, because you can see them as soon as you are standing directly in front of them. But you will have a very hard time to find the exit, and chances are that you will run into one of the beasts which are roaming this labyrinth, so you will never see the exit.

Now, on the other hand, you can see exactly 10 steps ahead. Wouldn't that certainly be a big improvement? You can avoid many floors completely because you can see at once they are just blind alleys. You can probably avoid lots of the beasts, too, unless they are especially mean and fast. Your chances to find an exit have greatly improved...

Now, on the other hand, you can see exactly 10 steps ahead. Wouldn't that certainly be a big improvement? You can avoid many floors completely because you can see at once they are just blind alleys. You can probably avoid lots of the beasts, too, unless they are especially mean and fast. Your chances to find an exit have greatly improved...

Interesting. I will think about it :-)

Your labyrinth analogy here only works if the search has accidentally pruned out the best move from consideration. When you run into a beast, that is the equivalent of a fail low, at which point the branching in the search tree must be increased, at which point the correct move will either be searched or not searched; if not searched, you hit another fail low; if it's searched, you either find the way out or hit yet another fail low--if this happens, the position is lost anyway.

Depends. If you run into a beast while being able to look one step ahead it's not much more but bad luck. Hasn't a lot to do with pruning.

If you run into a beast while being able to look ten steps ahead, it also hasn't to do much with pruning as long as the beast is waiting at step 11. If your pruning is okay you should see it immediately when it proceeds to step. 10 - or better when you go one step ahead. Then it depends. Usually you should be able to outrun the beast. But sometimes it is very fast and you cannot (or cannot completely) avoid the bad variation which the beast is symbolizing.

If you run into a beast while being able to look ten steps ahead, it also hasn't to do much with pruning as long as the beast is waiting at step 11. If your pruning is okay you should see it immediately when it proceeds to step. 10 - or better when you go one step ahead. Then it depends. Usually you should be able to outrun the beast. But sometimes it is very fast and you cannot (or cannot completely) avoid the bad variation which the beast is symbolizing.

I think this is changing the subject--the original question was basically "why is it better to be able to look n+1 steps ahead than n steps ahead"? The direct answer is that the probability of running into a beast (i.e. a losing continuation) before the very end (i.e. a win or draw) decreases as you look further ahead and don't see all paths leading to beasts.

That's right. But imagine there are so many potential beasts in game (which probably is not the case, but it might), that each alley could be blocked by one. Imagine further, that you have the power, by not knowing about some of the beasts, to make them imaginary, so you can simply walk through them. How is that? Well, if you don't know about them (even if you should be able to see them in terms of horizon), chances are they don't know about you... ;-)

So it could be that chess is a game which is only working, because everyone who plays it (including the engines) is far from being a perfect player and thus

So it could be that chess is a game which is only working, because everyone who plays it (including the engines) is far from being a perfect player and thus

**believes**(only believes) that there are doors and exits - instead of beasts... ;-)
I think that one of the assumptions in the original argument is that the engines don't make serious mistakes when trying to evaluate a particular position. If we don't assume this, then we basically get nowhere anyway, and it's nearly the equivalent of evaluating all positions as 0.00.

But of course they make serious mistakes. Usually horizon based (not seeing a problem or trap until it's too late), but sometimes evaluation based, too. Else it would be close to impossible to win against an engine. But of course other engines do that all the time - even Rybka has her share of losses. Okay, in a human/human game the same mistakes would only be minor, if they would be called mistakes at all. But in engine/engines games even minor mistakes become serious...

Search gives you two things - tactical strength and positional strength. Tactical strength is self-evident and not really that important anyway after some basic point, so let's just talk about positional strength.

You have a position P and an evaluation function E ().

Can you agree that E (P) is less accurate than trying every move m1, m2, .. in P, evaluating every resulting position, and taking the best score from E (P+m1), E(P+m2), etc?

Vas

You have a position P and an evaluation function E ().

Can you agree that E (P) is less accurate than trying every move m1, m2, .. in P, evaluating every resulting position, and taking the best score from E (P+m1), E(P+m2), etc?

Vas

Technically speaking, I don't think I have truly used physics here--I have used mathematics, as entropy is a statistical quantity that happens to be useful in, among other places, physics. The second law of thermodynamics could just as well be called something else, and is really statistical in nature--again, it also happens to be useful in physics. I think these provide a direct answer to the affirmative that search DOES work, and I think it also gets to the question of why it's important and at the same time gives a possible proof that all arguments that lead to the conclusion that increased search can be "wrong" must have a flaw somewhere.

As for (1) with evaluation being crucial, if the evaluation is such that evaluating a position as "won" (i.e. mate in or less than such and such) is correct, then increasing search indefinitely will eventually lead to winning moves. As for evaluation scoring every position at 0.00, search still makes a difference because one of two things can happen: (a) the evaluation is incorrect, and one of the moves evaluated as 0.00 is actually a losing or winning move, or (b) the evaluation is correct, but there are moves with a very high "entropy", giving the opponent lots of chances to make mistakes. In situation (a), a deeper search will eventually change the evaluation to something that hopefully indicates the nature of the position. In situation (b), there should be something in addition that, in case of a tie in evaluation, plays the move that gives the opponent the largest search tree.

I think that Vas is in the process of answering (2), so I won't steal his thoughts, especially since he's practically an infinitely better programmer than I am, and that question deals more with such issues.

As for (1) with evaluation being crucial, if the evaluation is such that evaluating a position as "won" (i.e. mate in or less than such and such) is correct, then increasing search indefinitely will eventually lead to winning moves. As for evaluation scoring every position at 0.00, search still makes a difference because one of two things can happen: (a) the evaluation is incorrect, and one of the moves evaluated as 0.00 is actually a losing or winning move, or (b) the evaluation is correct, but there are moves with a very high "entropy", giving the opponent lots of chances to make mistakes. In situation (a), a deeper search will eventually change the evaluation to something that hopefully indicates the nature of the position. In situation (b), there should be something in addition that, in case of a tie in evaluation, plays the move that gives the opponent the largest search tree.

I think that Vas is in the process of answering (2), so I won't steal his thoughts, especially since he's practically an infinitely better programmer than I am, and that question deals more with such issues.

I think you misunderstood me. When I mention a static evaluation that scores every position at 0.00, I meant just that. It would mean that the program would score every candidate move at 0.00, no matter how much search is performed -- the move to be played would be chosen at random, and search would not help you one single bit.

It's just a really lame example, meant to emphasize the fact that the static evaluation has to meet some basic conditions in order for "search to work".

I perfectly understand that thermodynamics is just a mathematical model, and I understand why it can be applied to physical predictions. What I failed to understand was how thermodynamics can by applied to the dynamics of game-search. I still don't get it ;-)

It's just a really lame example, meant to emphasize the fact that the static evaluation has to meet some basic conditions in order for "search to work".

I perfectly understand that thermodynamics is just a mathematical model, and I understand why it can be applied to physical predictions. What I failed to understand was how thermodynamics can by applied to the dynamics of game-search. I still don't get it ;-)

My first assumption about what you meant was that you were talking about a "trivial evaluation" of which you have just elucidated; I then decided you weren't talking about this. Anyway, it's certainly true that search wouldn't help in such a case, but then the programmer is taking away his machine's even most remote possibilities of winning (though if white starts out with something like 1.g4 and 2.f3, then there is something like a 0.002 chance that the machine has played something like 1...e6 or 1...e5 and then finds 2...Qh4#. I guess the conditions that must be met are that the programmer is making at least a minimum amount of effort to allow his machine to win games.

As for how entropy can be applied to the dynamics of the game search, I think it works because you still have the second law, which in this case would state that for every increase in ply, you will have not only a new, larger macrostate, but a macrostate with a far larger number of microstates. The entropy is proportional to the natural logarithm of the number of microstates--in thermodynamics, the proportionality constant is Boltzmann's constant k = 1.3806565E-23 joules per kelvin, but here it would be something different--I have some ideas as to what it would be, but the language involved in the justification is not something that I've yet figured out how to explain here--though perhaps someone else might be able to do so--it would have something to do with information and, in particular, possibly some sort of units with "change in percent to completion divided by amount of information", or even possibly the inverse of one or both of these. Anyway, without increased search coupled with an evaluation function, the entropy increases without any sort of correction--the entropy always increases because you always technically have a "trivial search" like the one mentioned above that evaluates all positions with 0.00, but if you have a search coupled with a non-trivial evaluation, you are decreasing the entropy, assuming that your search isn't a trivial search. If you stop your search at one previous ply, then you have effectively left the rest of the microstates that would have occurred with additional search "unordered" and thus with increased entropy, or more of a "random" state.

As for how entropy can be applied to the dynamics of the game search, I think it works because you still have the second law, which in this case would state that for every increase in ply, you will have not only a new, larger macrostate, but a macrostate with a far larger number of microstates. The entropy is proportional to the natural logarithm of the number of microstates--in thermodynamics, the proportionality constant is Boltzmann's constant k = 1.3806565E-23 joules per kelvin, but here it would be something different--I have some ideas as to what it would be, but the language involved in the justification is not something that I've yet figured out how to explain here--though perhaps someone else might be able to do so--it would have something to do with information and, in particular, possibly some sort of units with "change in percent to completion divided by amount of information", or even possibly the inverse of one or both of these. Anyway, without increased search coupled with an evaluation function, the entropy increases without any sort of correction--the entropy always increases because you always technically have a "trivial search" like the one mentioned above that evaluates all positions with 0.00, but if you have a search coupled with a non-trivial evaluation, you are decreasing the entropy, assuming that your search isn't a trivial search. If you stop your search at one previous ply, then you have effectively left the rest of the microstates that would have occurred with additional search "unordered" and thus with increased entropy, or more of a "random" state.

I see no way that search can give below 0.

It is possible that a program is going to play a move that gives no practical chances in order to prevent something worse that the opponent will probably not see but this is not something new.

Uri

It is possible that a program is going to play a move that gives no practical chances in order to prevent something worse that the opponent will probably not see but this is not something new.

Uri

True. But now imagine that, due to a dramatically increased ply depth, the engines would see worse things everywhere and get paranoid, so to speak. Would they still be able to do anything else but shuffling the rooks around without any practical use? Would they finally find that the best strategy to play against another engine would be a variation of this horrible anti-computer chess of Pablo Restropo? :=)

different versions of an engine, all tailored for different opponents. this will prevent that possible "horizon effect" for weak opponents.

for example, can we integrate fritz 10 in rybka , to create a rybka which can guess the replies of fritz for each possible move, and

select the ones which fritz evaluates with most mistake ?

but when the problem is an engine-engine match with closer strength and closer search depth, the answer is different.

for example, can we integrate fritz 10 in rybka , to create a rybka which can guess the replies of fritz for each possible move, and

select the ones which fritz evaluates with most mistake ?

but when the problem is an engine-engine match with closer strength and closer search depth, the answer is different.

I see no reason that the possibility of shuffling the rooks around without any practical use will happen only at big search depth.

There are going to be cases when the program may shuffle the rooks without practical use at low depths when at big search depths the program is going to find something better and I see no reason why this possibility is going to be less common than the possibility of shuffling the rooks only at big depth.

Uri

There are going to be cases when the program may shuffle the rooks without practical use at low depths when at big search depths the program is going to find something better and I see no reason why this possibility is going to be less common than the possibility of shuffling the rooks only at big depth.

Uri

*I see no reason that the possibility of shuffling the rooks around without any practical use will happen only at big search depth.*

I did not claim that.

*There are going to be cases when the program may shuffle the rooks without practical use at low depths when at big search depths the program is going to find something better*

Certainly, but you are missing my point.

*and I see no reason why this possibility is going to be less common than the possibility of shuffling the rooks only at big depth.*

Because I think it might be possible that "perfect chess" would simply be to do nothing at all. Lots of people have debated about if chess being solved would mean that White always wins or that all games would be a draw. But what if chess being solved means that he who makes the first substantial move (anything beyond Restropo-Chess) always loses?

Your words simply do not make sense.

In most drawn positions there is no single drawing move but many drawing moves.

Shuffling pieces can be a way to get a draw but it is usually not going to be the only way so if the program does not do it at small depths then it is not going to do it at big depths.

Uri

In most drawn positions there is no single drawing move but many drawing moves.

Shuffling pieces can be a way to get a draw but it is usually not going to be the only way so if the program does not do it at small depths then it is not going to do it at big depths.

Uri

You are completely missing my point, Uri. But I don't know how to say it better. Blame it on me and my lacking English skills. I'm sorry.

The possibility that the side who makes the first substantial move (anything beyond Restropo-Chess) always loses is not logical.

I cannot prove mathematically that it is not the case but it seems obvious to me that there are many perfect games and not a single perfect game.

You can also say that maybe white wins in the opening 1.e4 e5 2.Ba6

I cannot prove that it is not the case but it seems obvious and claiming that maybe white can win by that line does not make sense.

Uri

I cannot prove mathematically that it is not the case but it seems obvious to me that there are many perfect games and not a single perfect game.

You can also say that maybe white wins in the opening 1.e4 e5 2.Ba6

I cannot prove that it is not the case but it seems obvious and claiming that maybe white can win by that line does not make sense.

Uri

Agreed Uri. It is nonsense to suggest that deeper searches = poorer play. However, of course, the difference between 100 plies and 101 is almost non existant.

Depends on your definition of a "Worse" move.

That's the whole problem with this discussion.

If your definition of a worse move is a move which leads to a worse result assuming optimal play, than of course, deeper search will tend to improve the quality of moves (actually even in that case, not always. As long as it cannot see to the leaf (final) positions in its search, there is a minimal chance that a move will seem to work at ply 30, for instance, but a change in ply 31 makes it look bad again, and at 29 it wasn't even considered. Of course, for this to happen AND for the Quiescence search to fail to notice it means a VERY VERY low chance. Bordering on 0 I think, although I haven't tested).

So, if that's your definition for a better/worse move, you would almost always be right.

But there's a problem with this definition, which is why it is NOT my definition of a worse move. And it is obviously not the definition of many other players.

The problem is this:

This definition means that there are only 3 types of moves: "Winning, losing, and drawing".

This makes comments such as "Ne7 would have been a tougher defense" a bit meaningless.

But that is how we analyze games.

That is even how engines analyze games in a more restricted sense. They have a +0.1 for one move and a +0.14 for another. so they'll prefer the +0.11. It may be that both of them are drawn.

Now consider positions in which the previous remark would be a likely comment made by GM analysis. ("Ne7 would have been a tougher defense"). Further suppose that the move played is, say, ...h6.

An engine that can see both moves all the way to the lost position would just choose one of them. There is no difference between them according to it.

Which means that it has about a 50% chance to choose the one which most other people and/or engines would easily find how to crack and not the one that would manage to riposte the attack against many of them. that would cause the ACTUAL performance in those positions to be lower than other engines.

The main counter argument is that it would cause an increase in performance in far more positions than the ones where it will cause a decrease in performance. Testing this argument (which is logical) for every feasible deep search solution (some actually not feasible at all and completely theoretical) is quite impossible.

Now about the starting position. Same thing here. I don't care if anyone ever proves that both 1.e4 and 1.h4 lead to a draw.

According to the way I define "better moves" 1.e4 would still be better. The same goes if I HAD access to the full knowledge of how to play both openings during a game. Against strong non perfect players, my performance would be better with 1.e4.

So, it's all a matter of definitions and terminology.

in my "book" (pun intended), "better" moves need not necessarily be moves leading to an objectively better result considering optimal play,

and "worse" moves need not necessarily be moves leading to an objectively worse result considering optimal play.

You're definitely right about one thing: none of this is new.

I just wanted to make it clear it all rests each and every person's definitions and approach to the game.

That's the whole problem with this discussion.

If your definition of a worse move is a move which leads to a worse result assuming optimal play, than of course, deeper search will tend to improve the quality of moves (actually even in that case, not always. As long as it cannot see to the leaf (final) positions in its search, there is a minimal chance that a move will seem to work at ply 30, for instance, but a change in ply 31 makes it look bad again, and at 29 it wasn't even considered. Of course, for this to happen AND for the Quiescence search to fail to notice it means a VERY VERY low chance. Bordering on 0 I think, although I haven't tested).

So, if that's your definition for a better/worse move, you would almost always be right.

But there's a problem with this definition, which is why it is NOT my definition of a worse move. And it is obviously not the definition of many other players.

The problem is this:

This definition means that there are only 3 types of moves: "Winning, losing, and drawing".

This makes comments such as "Ne7 would have been a tougher defense" a bit meaningless.

But that is how we analyze games.

That is even how engines analyze games in a more restricted sense. They have a +0.1 for one move and a +0.14 for another. so they'll prefer the +0.11. It may be that both of them are drawn.

Now consider positions in which the previous remark would be a likely comment made by GM analysis. ("Ne7 would have been a tougher defense"). Further suppose that the move played is, say, ...h6.

An engine that can see both moves all the way to the lost position would just choose one of them. There is no difference between them according to it.

Which means that it has about a 50% chance to choose the one which most other people and/or engines would easily find how to crack and not the one that would manage to riposte the attack against many of them. that would cause the ACTUAL performance in those positions to be lower than other engines.

The main counter argument is that it would cause an increase in performance in far more positions than the ones where it will cause a decrease in performance. Testing this argument (which is logical) for every feasible deep search solution (some actually not feasible at all and completely theoretical) is quite impossible.

Now about the starting position. Same thing here. I don't care if anyone ever proves that both 1.e4 and 1.h4 lead to a draw.

According to the way I define "better moves" 1.e4 would still be better. The same goes if I HAD access to the full knowledge of how to play both openings during a game. Against strong non perfect players, my performance would be better with 1.e4.

So, it's all a matter of definitions and terminology.

in my "book" (pun intended), "better" moves need not necessarily be moves leading to an objectively better result considering optimal play,

and "worse" moves need not necessarily be moves leading to an objectively worse result considering optimal play.

You're definitely right about one thing: none of this is new.

I just wanted to make it clear it all rests each and every person's definitions and approach to the game.

Actually... It doesn't rest on persons and their definitions of better and worse (except maybe on persons like Vas) but on engines (since we were talking about them) and their definition of better and worse. Which is simple: +0,14 is better than +0,11, no matter what - at least as far as I understand them. Now what happens if, assuming perfect play being possible, all the "better" moves were those which don't really change anything?

It does rest on PEOPLE's definitions...

The whole question was whether or not an engine can play worse moves by searching more...

That depends on how the person answering the question defines better or worse moves.

The engine's opinion about the move is irrelevant.

The question is whether or not an engine that searches more can play a move which is actually worse.

Obviously it can't play a worse move if you're considering its own definitions for the values of the moves....... it will always play the best move it finds according to its evaluation.

The question is whether or not it can be a worse move than a move generated by a more shallow search.

That requires the definition an interpretations of outside observers.

The whole question was whether or not an engine can play worse moves by searching more...

That depends on how the person answering the question defines better or worse moves.

The engine's opinion about the move is irrelevant.

The question is whether or not an engine that searches more can play a move which is actually worse.

Obviously it can't play a worse move if you're considering its own definitions for the values of the moves....... it will always play the best move it finds according to its evaluation.

The question is whether or not it can be a worse move than a move generated by a more shallow search.

That requires the definition an interpretations of outside observers.

Your assumption here is not correct:

"An engine that can see both moves all the way to the lost position would just choose one of them. There is no difference between them according to it."

This is correct

You continue:

"Which means that it has about a 50% chance to choose the one which most other people and/or engines would easily find how to crack and not the one that would manage to riposte the attack against many of them. "

This is not correct

The fact that the engine choose one of them does not mean that both have 50% chances.

The engine starts at small depth and has a best move.

The fact that the score of the move drop to draw score does not mean that the engine will prefer a different move because the engine may need to see by search that the second move lead to advantage in order to do it.

Uri

"An engine that can see both moves all the way to the lost position would just choose one of them. There is no difference between them according to it."

This is correct

You continue:

"Which means that it has about a 50% chance to choose the one which most other people and/or engines would easily find how to crack and not the one that would manage to riposte the attack against many of them. "

This is not correct

The fact that the engine choose one of them does not mean that both have 50% chances.

The engine starts at small depth and has a best move.

The fact that the score of the move drop to draw score does not mean that the engine will prefer a different move because the engine may need to see by search that the second move lead to advantage in order to do it.

Uri

Actually you're wrong.

More precisely, not exactly right.

The problem is that each engine can reach a different move of the two first in its search.

due to different evaluations at different depths of the variations created by the two moves, and different cut off heuristics may mean that it takes a shorter time to reach a certain depth with one of the moves in one implementation and another in another implementation.

So there is no reason to assume the engine will prefer the "better" move (in the NON optimal definition of the term).

Of course this also means that my 50% is also not really based on anything, It's just the way I related to something which I have no way of knowing which way it will go.

It can be 20% or 80% or any% of course.

The numbers are off, but I just used the example as a way to show how an example when a deeper search can decrease performance be constructed.

Of course, the chance for an engine to find the "wrong" move first can be even a fraction of a percent. I don't know. I just meant to say it is possible.

More precisely, not exactly right.

The problem is that each engine can reach a different move of the two first in its search.

due to different evaluations at different depths of the variations created by the two moves, and different cut off heuristics may mean that it takes a shorter time to reach a certain depth with one of the moves in one implementation and another in another implementation.

So there is no reason to assume the engine will prefer the "better" move (in the NON optimal definition of the term).

Of course this also means that my 50% is also not really based on anything, It's just the way I related to something which I have no way of knowing which way it will go.

It can be 20% or 80% or any% of course.

The numbers are off, but I just used the example as a way to show how an example when a deeper search can decrease performance be constructed.

Of course, the chance for an engine to find the "wrong" move first can be even a fraction of a percent. I don't know. I just meant to say it is possible.

*I see no way that search can give below 0.*

It is clearly possible theoretically for deeper search to have a negative impact on the overall playing strength of an engine. To see this, consider first an engine E with access to an evaluation function which is perfect in the sense that for every drawn position it will return zero while for all the other positions an appropriate value representing distance to mate will be returned (for example, 32000 - distance_to_mate for won positions and distance_to_mate - 32000 for lost positions from the point of view of the side not to move). Clearly, E will be a perfect player no matter what the search depth.

Now, assume that there is a drawn position P such that P is the child of only one other position P' and such that the move leading from P' to P is in fact the best move in the strong sense that all other moves lose half a point; I do not know whether such a pair of positions does exist in the game of chess but it does not seem implausible to me to suppose so and I think with some work, it could indeed be possible to find an actual example. Assume that Q is the position that is reached by the second-best move in P' and that E(Q) = q. Assume that q+1 < 0, then we can construct another evaluation function E' by setting E'(P) = q + 1, and E'(x) = E(x) everywhere else. Then, an engine using E' as evaluation function will with a one-ply-search still find the best move in every position, since the move ordering based on static evaluation has by construction changed for no position, but it will prefer a loss with evaluation larger than q+1 to the prospect of reaching the drawn position P at higher search depths and this can possibly lead it to play wrong moves. Hence, under these circumstances, increasing search depth will clearly hurt the playing strength of the engine.

In real life, such effects could I believe happen if the static evaluation of an engine happened to be bad at comparing the values of positions from different game-phases while being reasonably good at comparing positions from the same game-phase; in this case, the engine might prefer for example an unclear middlegame to a clearly won endgame if it has a tendency of liking middlegame positions more in general. This in turn would in my opinion probably hurt more at high search depths than at low search depth, because at high depths the engine has a higher chance to be given a choice between leaf-nodes in different game-phases than at a lower depth.

In general, I think the condition that an evaluation function has to meet in order for search to help would simply be that it should have a tendency of becoming more accurate as we get closer to the final game-state. Accuracy of an evaluation function E could in this context for example be rigorously defined by the number n(E, m) of pairs of positions (p,q) which are m moves away from a final game-state in a perfect game of minimal length starting from those positions such that E(p) < E(q) while p is in fact preferable to q.

Regards,

Neuromancer

In theory of course it can happen but I think that practically it cannot happen.

Of course deeper search can lead to worse moves in some cases but it seems clear to me that practically in more cases deeper search is going to lead to a better move and the total result of a deeper search is a bigger rating.

I assume that you do not write on purpose a program that is going to play worse with deeper search and I assume that you evaluate checkmates correctly(if you write a program that evaluates checkmate as a loss for itself then it will try to do everything to avoid winning and of course deeper search may cause it to try to force the opponent to make checkmate so deeper search is going to cause it to lose rating).

Uri

Of course deeper search can lead to worse moves in some cases but it seems clear to me that practically in more cases deeper search is going to lead to a better move and the total result of a deeper search is a bigger rating.

I assume that you do not write on purpose a program that is going to play worse with deeper search and I assume that you evaluate checkmates correctly(if you write a program that evaluates checkmate as a loss for itself then it will try to do everything to avoid winning and of course deeper search may cause it to try to force the opponent to make checkmate so deeper search is going to cause it to lose rating).

Uri

The big surprise for me in computer chess is that the diminishing returns with depth has happened at a much slower rate than we all expected twenty years ago. Each ply adds a little less than the previous one, but just very slightly less. That's why Rybka on a Quad can play at 3150, few would have believed it possible back then. It looks pretty clear to me now that we are nowhere near the point where additional plies are close to worthless. Probably a fifty ply search vs. a forty ply search would at least draw easily with Black, and would reach favorable endgames every time with White, many of which would turn out to be wins. Since many complex endings can't be judged as won or drawn without huge search, I would say that extra plies will have some value even at 100 ply.

this entire subject made me think about a "reversed" question:

it is very hard to find the best possible move in a certain position,

maybe it is easier to find the worst possible move in that position?

If the answer is "yes", then that approach could be repeated

until only one or two moves are left to investigate :-)

(hmm, yeah, I know, this sounds like developing an extremely poor

Viterbi decoder or QPSK demodulator which makes 100% wrong decisions,

producing a completely wrong bitstream, and then putting a boolean invertor

at the output ;-) :-)

but in chess.... ???

Roger

it is very hard to find the best possible move in a certain position,

maybe it is easier to find the worst possible move in that position?

If the answer is "yes", then that approach could be repeated

until only one or two moves are left to investigate :-)

(hmm, yeah, I know, this sounds like developing an extremely poor

Viterbi decoder or QPSK demodulator which makes 100% wrong decisions,

producing a completely wrong bitstream, and then putting a boolean invertor

at the output ;-) :-)

but in chess.... ???

Roger

That's an interesting answer to my question. Actually I had the feeling myself that there would always be ways and possibilities to outsmart the labyrinth. But I thought, maybe all possible moves of a chessgame would provide so much data that each available variation would find a refutation somewhere along it's line.

Like, you know, the proof why the universe can't be infinite: because, if it were, than the sky would be blazing with stars as bright as the day even at night and temperature would be quite unpleasant....

Like, you know, the proof why the universe can't be infinite: because, if it were, than the sky would be blazing with stars as bright as the day even at night and temperature would be quite unpleasant....

**Like, you know, the proof why the universe can't be infinite: because, if it were, than the sky would be blazing with stars as bright as the day even at night and temperature would be quite unpleasant....**

That assumes stars always existed and in which their light has reached us already.

This is a fallacy. Why must there be only 1 big bang. What if space is infinite and infinitely many other big bangs happened so far from us that the light from their stars won't reach us for another zillion years (if our big bang survives that long)?

Or you might be assuming that the universe is not defined outside the last star (assuming there is a last star from us). Meaning, you could be implying that the universe is defined as the summation of all particles and energy that exists and not space-time itself. You must know that space-time (or plain space) is included in the definition. So what if only 1 big bang happened, but outside of that is nothing but infinite space-time in which to hold it? Wouldn't that still make our universe infinite?

From interview with Joseph Silks (Univesity of Oxford professor and author of many astronomy and physics books and papers)

ESA: Is the Universe finite or infinite?

Joseph Silk: We don't know. The expanding Universe theory says that the Universe could expand forever [that corresponds to a 'flat' Universe]. And that is probably the model of the Universe that we feel closest to now. But it could also be finite, because it could be that the Universe has a very large volume now, but finite, and that that volume will increase, so only in the infinite future will it actually be infinite.

ESA: It sounds like a game of words, is it?

Joseph Silk: No. We do not know whether the Universe is finite or not. To give you an example, imagine the geometry of the Universe in two dimensions as a plane. It is flat, and a plane is normally infinite. But you can take a sheet of paper [an 'infinite' sheet of paper] and you can roll it up and make a cylinder, and you can roll the cylinder again and make a torus [like the shape of a doughnut]. The surface of the torus is also spatially flat, but it is finite. So you have two possibilities for a flat Universe: one infinite, like a plane, and one finite, like a torus, which is also flat.

ESA: Is the Universe finite or infinite?

Joseph Silk: We don't know. The expanding Universe theory says that the Universe could expand forever [that corresponds to a 'flat' Universe]. And that is probably the model of the Universe that we feel closest to now. But it could also be finite, because it could be that the Universe has a very large volume now, but finite, and that that volume will increase, so only in the infinite future will it actually be infinite.

ESA: It sounds like a game of words, is it?

Joseph Silk: No. We do not know whether the Universe is finite or not. To give you an example, imagine the geometry of the Universe in two dimensions as a plane. It is flat, and a plane is normally infinite. But you can take a sheet of paper [an 'infinite' sheet of paper] and you can roll it up and make a cylinder, and you can roll the cylinder again and make a torus [like the shape of a doughnut]. The surface of the torus is also spatially flat, but it is finite. So you have two possibilities for a flat Universe: one infinite, like a plane, and one finite, like a torus, which is also flat.

I'll look that up. Thanks!

But I still don't see how the surface of the torus is finite (I know it would be flat though).

But I still don't see how the surface of the torus is finite (I know it would be flat though).

There is another problem in the semantics of this, and that is what one means by "infinite". If the Universe is globally spatially flat, then if you were to literally stop its expansion right now and travel in one direction, you would, after an extremely long time, reach an "edge" in the sense that you would no longer be able to travel any farther after that point. I have forgotten the radius of this edge, but it is far, far greater than either the event horizon (the collection of points at which we could arrive after infinite time traveling at the speed of light in some constant direction if we were to let the expansion loose again) or the particle horizon (the farthest points in the Universe at which signals traveling at the speed of light just now have the potential to reach us)--in spite of the fact that the Universe is about 14 billion years old. I believe I have read one estimate that the answer is 50-something billion light-years. Thus, if you were to stop the Universe's expansion right now, you would realize that it is finite no matter whether it has zero, positive, or negative global spatial curvature. However, the point is that we CAN'T stop the expansion (this is not only physically impossible, but also logically and mathematically impossible--what I have stated above is true, but keep in mind that we are NOT at the center of the Universe!--so you could ask how far it would be to the "edge" for someone in some galaxy 10 billion light-years away, and the answer would have to be the same--it's just one of those weird things about general relativity), and if the Universe has zero spatial curvature (a fact that has been confirmed to within two parts in a hundred), then you can travel in one direction and never reach any sort of "end". However, this is also true even if the Universe is shaped like a three-dimensional sphere and thus spatially closed! As we now know, we have a cosmological constant that started accelerating the Universe's expansion roughly 6 billion years ago, and so even if the Universe has positive spatial curvature (which it very well could--the density parameter is currently measured as 1.02 plus or minus 0.02; 1.00 exactly would denote a flat Universe), you would never be able to go "all the way around" the Universe, even given infinite time. This is, of course, assuming that we're dealing with a cosmological constant instead of some form of quintessence, whose effect would be not only to change the rate of expansion, but to change the rate of acceleration.

There is no such proof. First, we know that the Universe began at a finite time in the past. You are basically stating Olbers Paradox, though it was actually first stated as such by a Catholic bishop a few centuries beforehand. Ironically, the first correct solution came by the poet Edgar Allen Poe (yes, the Nevermore guy) who stated that perhaps there were some stars located so far away that their light had not yet had time to reach us. Furthermore, even if the Universe DIDN'T begin at a finite time in the past, there would be no problem because we know that the stars have finite lifetimes. Even further, even if the stars lived infinitely long, we know that the Universe is expanding, and we also know that light travels with finite speed. Thus, there would be a maximum radius, the particle horizon, beyond which no light would be able to reach us.

hey guys this is a chess engine forum, remember :-)

> even if the stars lived infinitely long,

Now you're entering on theoretical realm, the "what if".

What if "stars lived infinitely long" AND light traveled at infinite speed?

Then "the sky would be blazing with stars as bright as the day even at night and temperature would be quite unpleasant...."?

> hey guys this is a chess engine forum, remember (vroger007)

I already suggested an Off-topic forum to talk about such themes, but until then, let us discuss such themes... Anywhere ;)

Naturally, IF stars lived infinitely long in both the past and the future (they don't--ones with same brightness as Sun live 10 billion years; ones with same brightness as Rigel live only a few million years), and IF light traveled at infinite speed (no need to comment on this), and IF the Universe was infinitely old (I would say that COBE and WMAP have done enough to disprove this even if the initial discovery of the CMB didn't), and IF the distribution of stars was evenly spread throughout the Universe (no need to comment on this), then yes, the night sky would be as bright as the surface of a star :-).

well, since you all seem to insist :-)

IF the universe would have existed since infinity,

we would all be gone by now, and universe would be

extremely dark, very close to 0 Kelvin, with matter

evolved to mostly only iron and comparable heavy atoms,

with an extremely low matter density (say on average 1 atom

every cube lightyear or so....).

That is if expansion continues which it seems to do

(even at increasing rate still, which was quite unexpected a few years ago).

IF the universe would have existed since infinity,

we would all be gone by now, and universe would be

extremely dark, very close to 0 Kelvin, with matter

evolved to mostly only iron and comparable heavy atoms,

with an extremely low matter density (say on average 1 atom

every cube lightyear or so....).

That is if expansion continues which it seems to do

(even at increasing rate still, which was quite unexpected a few years ago).

No, because any theory of a Universe existing infinitely long in the past must be a steady state theory of some sort (these are, for all practical purposes, disproven by recent observations especially with WMAP), and in steady state theories, new matter comes into existence within spacetime itself as the Universe expands. This naturally has some energy which allows the Universe to stay a relatively "warm" 2.7 Kelvins on average. The observed element abundances are also consistent with such a theory, as shown by Hoyle and Narlikar in the 1950's and 1960's. Of course, observed galaxy evolution with lookback time is NOT consistent with such a theory, as these theories made a specific prediction that we should not see young-looking galaxies as we look to farther and farther lookback times, and yet we see these in great abundance, along with practically no older-looking galaxies.

The expansion in a steady state theory obeys the de Sitter model, i.e. is exponential. Our cosmological-constant dominated Universe will probably tend toward this as an asymptotic limit, but we can't currently be too sure.

The expansion in a steady state theory obeys the de Sitter model, i.e. is exponential. Our cosmological-constant dominated Universe will probably tend toward this as an asymptotic limit, but we can't currently be too sure.

Hi,

the discussion reminds me that what was written in E. Lasker book. He was WCC and mathematician.

He compared the chess to the physics rule of the minimum energy. The right move it is the move which is going due to the line of the less resistance. Chess are not continues space but discreete so he applied the points of the less resistance.

If we followed that way of thinking we can say that not the length of the calculation is most important but the direction of calculation.

In physics and mathematics it is called 'gradient'. If you are moving according gradient you are moving in the right direction. You do not need for that the long analysis. When you are going down the mountain you do not have to see the top or valley to go to the top or valley.

The old practical players called it rule of the 'good move', 'spirit of the position', 'demand of the position'.

If we stick with that we do not need very long calculations but it is not easy :-).

Regards

Hetman

the discussion reminds me that what was written in E. Lasker book. He was WCC and mathematician.

He compared the chess to the physics rule of the minimum energy. The right move it is the move which is going due to the line of the less resistance. Chess are not continues space but discreete so he applied the points of the less resistance.

If we followed that way of thinking we can say that not the length of the calculation is most important but the direction of calculation.

In physics and mathematics it is called 'gradient'. If you are moving according gradient you are moving in the right direction. You do not need for that the long analysis. When you are going down the mountain you do not have to see the top or valley to go to the top or valley.

The old practical players called it rule of the 'good move', 'spirit of the position', 'demand of the position'.

If we stick with that we do not need very long calculations but it is not easy :-).

Regards

Hetman

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill