3 ms·
Logistic regression can learn some quite amazing things. I trained a linear function to play chess: https://github.com/thomasahle/fastchess https://github.com/
by thomasahle 6y ago
Logistic regression can learn some quite amazing things. I trained a linear function to play chess:
https://github.com/thomasahle/fastchess https://github.com/thomasahle/fastchess
and it manages to predict the next moves of top engine games with 27% accuracy.
A benefit of logistic regression is that the resulting model really fast. Furthermore, it's linear, so you can do incremental updates to your prediction. If you have `n` classes and `b` input features change, you can recompute in `bn` time, rather than doing a full matrix multiplication, which can be a huge time saver.
- mhh__ 6y agoIsn't 27% worse than flipping a coin?
- gpderetta 6y agoOnly if you have only two legal moves.
- enchiridion 6y agoNo, uniform random would be bounded by 1/16. However you cannot move ever piece in every configuration, so it's greater than that. Actually would be an interesting problem for figure out...
- adiM 6y agoThere are only 16 pieces, but in most board positions, many pieces can make more than one legal move.
- thomasahle 6y agoA typical chess position has 20-40 legal moves. The complete space of moves for the model to predict from has about 1800 moves. For comparison Leela Zero gets around 60% accuracy on predicting its own next move. With this sort of accuracy you can reduce the search part of the algorithm to an effective branching factor of 2-4 rather than 40, nearly for free, which is a pretty big win.
- nuclearnice1 6y agoI don’t understand the comment about Leela. Why isn’t own move prediction deterministic?
- thomasahle 6y agoBecause Leela (like fastchess mentioned above) has two parts: A neural network predicting good moves, and a tree search exploring the moves suggested and evaluating the resulting positions (with a second net). If the prediction (policy) net had a 100% accuracy, you wouldn't need the tree search part at all.
- heavenlyblue 6y agoYou haven’t mentioned any nondeterministic behaviour, therefore Leela is supposed to predict it’s own moves with a 100% accuracy.
- tel 6y agoIt's not non-determinism, it's partial information. The NN part guesses the best move that will be found by search X% of the time. If you just ditched the search part, Leela would be faster and lose out on (1-X)% of the better moves.
- nuclearnice1 6y agoGot it. Thanks for clarifying. Let me restate. Part one of Leela ranks several chess moves. Part two picks among those. 60% of the time part 2 chooses the #1 ranked move.
- thomasahle 6y agoThat works :-) One addition: The second part can be run for an arbitrary amount of time, gradually improving the quality of the returned move. The 60% figure comes from the training games, which are played very quickly, and so don't have a lot of time for refining, thus increasing the prediction accuracy. In real games, tcec-chess.com/ this "self accuracy" would probably be a bit lower.