3
$\begingroup$

I am developing a chess engine, and wrote four classifiers (logistic regression) for:

  1. detecting which part of the game it is (opening, middlegame, endgame) based on current board / position
  2. predicting that white will win (no draw games) if in opening position
  3. predicting that white will win (no draw games) if in middlegame position
  4. predicting that white will win (no draw games) if in endgame position

Now for the engine, I would like to compute the probability that white will win (for the minimax algorithm, white tries to increase this probability, black tries to decrease this probability by making moves). My first guess was to compute:

P(W) = P(W|Opening)*P(Opening) + P(W|Middlegame)*P(Middlegame) + P(W|Endgame)*P(Endgame)

Where each probability on the right is from logistic regression above. But now I am unsure, if this is the right "ansatz".


Edit: The idea here is to have a bitboard representation of a position and to interpret the coefficients of the logistic regression as piece value tables as is custom in other engines, with the difference that the values in this table are from logistic regression and not from experience of the programmer / player. As you can imagine predicting is stronger at the end of the game (opening 64% accuracy, middlegame 75 %, end game 83% ) so my idea was to write a classifier which detects on which part of the game it is and then to "combine" these different classifiers to have an evalutation function for each board.

I will illustrate this with some concrete probabilities:

 r n b q k b n r
 p p p p p . . .
 . . . . . . . p
 . . . . . p p .
 . . . P P . . P
 . . . . . . . N
 P P P . . P P .
 R N B Q K B . R

 # whichPart =  [0.91647043 0.07489996 0.00862961]
 # prOpen =  [0.20907355 0.79092645]
 # prMiddle =  [0.00829384 0.99170616]
 # prEnd =  [0.00323957 0.99676043]
 # pWhiteWins =  0.8077411092561112

So for the position above, the logistic regression whichPart detects correctly that the position belongs to the opening part ( 0.91 probability). But then prOpen thinks that white will win with probability 0.79, which is unclear at this point and which results in 0.8 probability that white will win.

My question is: How do I incorporate the uncertainity of the logistic regression prOpen when calculating the probability that white will win?

Below are the confusion matrices for the logistic regressions:

  1. Logistic regression for detecting which part of the game it is:

    [[1536  205   20]
     [ 226 1202  376]
     [   6  299 1381]]
    
  2. Logistic regression for detecting if white won the game based on observing one position from the opening:

    [[334 421]
     [240 756]]
    
  3. Logistic regression for detecting if white won the game based on observing one position from the middlegame:

    [[517 238]
     [208 788]]
    
  4. Logistic regression for detecting who won the game based on observing one position from the endgame:

    [[611 144]
     [157 839]]
    
$\endgroup$
2
$\begingroup$

Rather than trying to reinvent the wheel here, it is probably worth noting that there is a huge academic literature working towards solving the game of chess. It is worth reading some of this literature to understand what has already been done, however, there are a few things you will need to consider before you start with your problem. The first thing to note is that you will need to specify what you mean when you refer to the "probability" of winning, because chess is a game where the solution under perfect play is deterministic.

Chess is not a solved game (it is extremely complex), but many of its endgames have been solved, and there is already a large literature on computational methods relating to chess. You can get some basic information in Simon and Schaeffer (1992) and Elkies (1996)


Under perfect play the outcome of chess is deterministic: Formally, chess is a deterministic finite two-player game with perfect information. There is an important result in game-theory called Zermelo's Theorem which proves that any game of this kind has only three possible outcomes at strategic equilibrium: either the first player always wins, or the second player always wins, or a draw always occurs. In other words, under perfect play, the result is deterministic, and so the probability of a white win is either zero or one.

Predicting the probability that white will win for non-perfect play: The above fact means that you are only going to get a non-trivial probability value if you are examining non-perfect play. If you want to examine this as a probabiltiy problem, as opposed to a computational problem in game theory, you will need to specify what kind of imperfect play you are interested in. Presumably you are interested in estimating the probability of a white win for some population of players using imperfect play. The worse the quality of play, the closer the probability is likely to be to one-half, and the better the quality of play, the closer the probability will be to the true zero/one value under perfect play.

What is your predictive information: If you are looking at chess under imperfect play, for a particular population, you will also need to specify the information you are using for your predictions. From your question it appears that you will have some characterization of the chosen strategy in the early-game, mid-game, and end-game. However, in the later part of your question it appears that you intend to take account of the entire board-state at certain points (which will give you a problem at the highest level of complexity that is presently computationally impossible to solve). You will need to have more of a think about the information you will use and the match data you are interested in.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer. I will have a look at the papers. $\endgroup$ – orgesleka Feb 8 at 9:56
0
$\begingroup$

I strongly doubt your method will work unless the training set is massive and the prediction is for members inside the training set. Moreso, you would be ignoring Elo rating which does provide a prediction as to which player would win. Let me give you two scenarios as to why I do not think this will work.

My brother was at an international open and an international grandmaster was playing a simul with about twenty other players. He was zipping along moving from board to board when my brother did something unexpected, he manually reversed the castling that he had performed previously.

The GM stopped playing everyone else and started just playing my brother. The GM won but congratulated him. He showed my brother that he had a guaranteed win in five from the uncastled position. My brother made a mistake and lost.

This creates two problems for your algorithm. First, the probability of a win was unity. There was no uncertainty as it was unstoppable. The person with no chance of losing, lost.

My point is that chess is a deterministic system that is too complicated, but not too complex, to see deep enough into the future to determine the winner. What would your logistic regression be measuring? Would it be the absence of precision by a player in executing their best game? Chess is not a random process.

The second example happens quite a bit with beginners. King-Rook versus King is a guaranteed win, but beginners force a draw all of the time. If your logistic regression were trained on masters, then the probability would be unity, but on beginners, it may be 80%. Go slightly more complicated, to Bishop-Bishop-King versus King and you may never see an end to the game.

Positional thinking depends only on the skill of the player. Players with more skill can do more with a given position. Some openings, such as the center-counter should always result in a loss for black, but black wins from time to time. It should never happen with a master, but it happens quite a bit otherwise because the players do not take advantage of black being one pawn down. They lack the skill to take advantage of the position and black wins.

$\endgroup$
  • $\begingroup$ Thank you for your detailed answer. The engine should not be super strong, just so that it can defeat me ;), which should not be that hard. $\endgroup$ – orgesleka Feb 7 at 18:13
  • $\begingroup$ I edited the question to clarify what I mean. $\endgroup$ – orgesleka Feb 7 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.