last day (15 days later) » 

Feeds
Feeds
12:26 PM
7
A: How do chess engines decide which best line to play when the game outcome is within their horizon?

user21820The other answer is wrong; we can in fact program the chess engine to favour traps! As you already noted, when the engine thinks it is winning it should simply choose the best move. So the question is how to aim for the sharpest lines for the opponent when it is losing. This is of course subjecti...

 
Riking
Riking
Can you add a few more words acknowleding engines where this actually happens, or recognizing that it usually doesn't?
 
user21820
user21820
@Riking: Chess engines usually do not implement the technique I stated, because it is computationally expensive. However, the asker was clearly asking about how one can choose the best move to lay traps ignoring any time constraint. My answer addresses that. In contrast it is mathematically unsound to have a 'contempt factor', so it is really irrelevant what Stockfish or any other engine using 'contempt' does.
 
Annatar
Annatar
Computationally expensive indeed: There usually isn't only one E1(X), but rather some E1(X)-En(X), where n is up to the number of all possible moves for the opponent - unlike when searching for their single best move, you cannot predict which error they are going to make (if they do, of course).
 
Mike Jones
Mike Jones
github.com/vollmerm/TrappyBeowulf tries to play "human" traps. I've seen other engine attempt this human play. I've never seen any of these engine play, so I can't comment on how well they play tricks.
 
user21820
user21820
@Annatar: I've added a paragraph to my answer touching briefly on the manner in which computing E1 can be expensive, as well as why it is not relevant to the question about known game outcomes. However, it is not true that we need to 'predict which error the opponent makes'. The normal search function is something like Eval(P,α,β,d) where P is a position and α,β are the alpha-beta bounds and d is the depth. To compute E1 we just need to add boolean parameters for whether the players have made an error or not.
Namely, Eval(P,α,β,d,e,e') is the maximum score where current player must make e errors and opponent must make e' errors. To evaluate E1(X) for move X to position P, we compute Eval(P,α,β,d,0,1) with the appropriate α,β,d passed in.
@MikeJones: Thanks for your link! Do you know how exactly TrappyBeowulf tries to play 'human traps'?
 
Annatar
Annatar
12:26 PM
@user21820 Is "the maximum score where a player must make one error" the same as "the score for that player's second best move"?
 
user21820
user21820
@Annatar: No. It is "must make e errors in the future (unless forced)". Are you familiar with dynamic programming with such constraints? It's the same here. To compute Eval(P,α,β,d,1,0) simply compute max( − Eval(Q,...,d−1,0,1) , − Eval(Q',...,d−1,0,0) ) where Q is the result of making the best move from P and Q' is the result of making the second-best move from P. (Using the negamax convention, and alpha-beta pruning has to be modified accordingly.)
 
Annatar
Annatar
@user21820 Okay, the error is somewhere in the future, but still "second-best". Scenarios where "best play" is a narrow path where your opponent is better if they always find the right move, but worse otherwise, are pretty clear. But what if there are two (three,...) branches of the tree where the opponent remains better? The second-best of these would still be an "error", but that doesn't exactly constitute a real trap (=tipping the scales), does it?
(Unless if the complete tree is already known as asked in the question, but since you write about pruning, I assume you talk about the more general case)
 
user21820
user21820
@Annatar: I mentioned pruning mostly to explain why it is expensive to implement the technique in practical chess engines that want to lay traps even when the outcomes are unclear. Let us continue this interesting discussion in chat!
@David: Read the question again; it says "when the game outcome is within their horizon", and my answer addresses that... (I presume you meant "can" instead of "can't".)
 
David
David
The fact that you can program an engine to consider "traps" does not mean actual engines who are used in practice do that
@user21820 Indeed. Corrected
 
user21820
user21820
@David: You shouldn't delete and re-post a comment to fix a typographical error, as it makes the thread confusing. Now it appears as if I responded to your comment before you made it haha.. Anyway, as I said, the question was about how an engine could set traps, not whether current ones do or not.
 
which-line
which-line
12:26 PM
@user21820 As in the question title, my question is about how engines currently do choose between lines. I'm sorry if that wasn't clear. Another question on how they could set traps would be interesting, if you have any ideas on how to ask it so that it wouldn't be closed as too broad.
 
user21820
user21820
@which-line: Thanks for clarifying your question. But I'm not convinced that asking about what chess engines currently do is much more well-defined, unless you restrict to specific engines. The problem is that by definition, if I create a chess engine that uses the technique in my post, then it would be a current chess engine that favours traps. In any case, I think the alternative interpretation of your question (how they could set traps) is not too broad. Anyway, most chess engines play 'badly' when they think they are losing, precisely because they do not 'set traps'.
For example, if SF (StockFish 10) has a choice between two moves, one leading to essentially a simple KRK situation with score #−10, and another leading to a complicated forced sequence with score #−8, it will pick the first one just because it takes longer to lose...
 
David
David
@user21820 I had flagged your comment as "no longer needed"
 

last day (15 days later) »