Difference between revisions of "Winter"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| Line 21: | Line 21: | ||
** The classifier is trained via [[Temporal Difference Learning|temporal difference learning]] to predict whether a [[Moves|move]] will return [[Beta|beta]] | ** The classifier is trained via [[Temporal Difference Learning|temporal difference learning]] to predict whether a [[Moves|move]] will return [[Beta|beta]] | ||
** Classifier considers [[Hash Move|TT move]], [[Killer Move|killers]], [[Moves#Type|move type]], [[Origin Square|from square]], [[Target Square|target square]], [[Captures|capture target]], [[Static Exchange Evaluation|SEE]], target square of last move, [[Check|check]] and changes between forcing and unforcing moves (a capture is more likely after another capture) | ** Classifier considers [[Hash Move|TT move]], [[Killer Move|killers]], [[Moves#Type|move type]], [[Origin Square|from square]], [[Target Square|target square]], [[Captures|capture target]], [[Static Exchange Evaluation|SEE]], target square of last move, [[Check|check]] and changes between forcing and unforcing moves (a capture is more likely after another capture) | ||
| + | ** [[Countermove Heuristic]] (Winter 0.3) | ||
* [[Selectivity]] | * [[Selectivity]] | ||
** [[Null Move Reductions]] | ** [[Null Move Reductions]] | ||
| Line 30: | Line 31: | ||
==[[Evaluation]]== | ==[[Evaluation]]== | ||
[[FILE:Normal Distribution PDF.svg|border|right|320px|thumb|A set of Gaussians]] | [[FILE:Normal Distribution PDF.svg|border|right|320px|thumb|A set of Gaussians]] | ||
| − | * Non standard approach | + | * Non standard approach relied on a [https://en.wikipedia.org/wiki/Mixture_model mixture model] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66266&start=7 Re: Winter Released] by [[Jonathan Rosenthal]], [[CCC]], January 09, 2018</ref>, since Winter '''0.3''' on [https://en.wikipedia.org/wiki/Fuzzy_clustering Fuzzy C-Means] |
** Assumes [[Chess Position|positions]] encountered in search come from some set of k [https://en.wikipedia.org/wiki/Gaussian_function Gaussians] <ref>[https://en.wikipedia.org/wiki/K-means_clustering k-means clustering from Wikipedia]</ref> <ref>[http://stanford.edu/~cpiech/cs221/handouts/kmeans.html K Means] by [https://web.stanford.edu/~cpiech/bio/index.html Chris Piech]</ref> | ** Assumes [[Chess Position|positions]] encountered in search come from some set of k [https://en.wikipedia.org/wiki/Gaussian_function Gaussians] <ref>[https://en.wikipedia.org/wiki/K-means_clustering k-means clustering from Wikipedia]</ref> <ref>[http://stanford.edu/~cpiech/cs221/handouts/kmeans.html K Means] by [https://web.stanford.edu/~cpiech/bio/index.html Chris Piech]</ref> | ||
** Mixture model is trained via [https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm EM algorithm] <ref>[http://www.ics.uci.edu/~smyth/courses/cs274/notes/EMnotes.pdf The EM Algorithm for Gaussian Mixtures - Probabilistic Learning: Theory and Algorithms, CS 274A] (pdf) [https://en.wikipedia.org/wiki/University_of_California,_Irvine University of California, Irvine]</ref> <ref>[http://people.csail.mit.edu/dsontag/courses/ml12/slides/lecture21.pdf Mixture Models & EM algorithm Lecture 21] (pdf) by [https://people.csail.mit.edu/dsontag/ David Sontag], [https://en.wikipedia.org/wiki/New_York_University New York University]</ref> either on [[Databases|database games]] or positions sampled from search | ** Mixture model is trained via [https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm EM algorithm] <ref>[http://www.ics.uci.edu/~smyth/courses/cs274/notes/EMnotes.pdf The EM Algorithm for Gaussian Mixtures - Probabilistic Learning: Theory and Algorithms, CS 274A] (pdf) [https://en.wikipedia.org/wiki/University_of_California,_Irvine University of California, Irvine]</ref> <ref>[http://people.csail.mit.edu/dsontag/courses/ml12/slides/lecture21.pdf Mixture Models & EM algorithm Lecture 21] (pdf) by [https://people.csail.mit.edu/dsontag/ David Sontag], [https://en.wikipedia.org/wiki/New_York_University New York University]</ref> either on [[Databases|database games]] or positions sampled from search | ||
Revision as of 01:12, 17 December 2018
Winter,
an UCI compliant open source chess engine by Jonathan Rosenthal, written in C++, released on January 08, 2018 under the terms of GPL Version 3. Winter is inspired by machine learning techniques, as applied in move ordering and in particular in evaluation, and heavily relies on C++ templates but not on any library aside from STL as it comes with its own implementations for statistics [2] and linear algebra [3]. Winter started its life in 2016 as a group project at ETH Zurich in a course on parallel computing along with Jonas Kuratli and Jonathan Maurer - the current release with Jonathan Rosenthal as sole author has removed the parallel portion of the code [4]. It started to play on-line at HGM's Online Engine Blitz Tourneys in April 2017 [5].
Contents
Selected Features
Board Representation
Search
- Lazy SMP (Winter 0.3)
- Fail-Hard Iterative Deepening
- Alpha-Beta Principal Variation Search
- Transposition Table
- Move Ordering is based on the linear part of a Logistic Regression classifier aka cluster analysis
- The classifier is trained via temporal difference learning to predict whether a move will return beta
- Classifier considers TT move, killers, move type, from square, target square, capture target, SEE, target square of last move, check and changes between forcing and unforcing moves (a capture is more likely after another capture)
- Countermove Heuristic (Winter 0.3)
- Selectivity
Evaluation
- Non standard approach relied on a mixture model [7], since Winter 0.3 on Fuzzy C-Means
- Assumes positions encountered in search come from some set of k Gaussians [8] [9]
- Mixture model is trained via EM algorithm [10] [11] either on database games or positions sampled from search
- For each Gaussian a separate evaluation function is trained. When the evaluation function is called the relative probability a position stems from each Gaussian is estimated, the evaluation functions are computed and the final score is returned as the weighted average - a generalization of tapered eval with game phases [12]
- Parameter weights are trained via a mixture of reinforcement (temporal difference) learning and supervised learning
- Minimizing the cross entropy loss of a Logistic Regression model for each of the k Gaussians
- Training converges fast due to linear model at the heart
Misc
- Perft
- Print pretty Unicode chess boards
Forum Posts
- Re: Tapered Eval between 4 phases by Jonathan Rosenthal, CCC, October 16, 2017 » Tapered Eval
- Winter Released by Jonathan Rosenthal, CCC, January 08, 2018
- Re: Winter Released by Jonathan Rosenthal, CCC, January 09, 2018
- Windows version released by Jonathan Rosenthal, CCC, January 23, 2018
- Winter 0.2 Release Overview and Select Games by Jonathan Rosenthal, CCC, Auguat 20, 2018
- Winter 0.3 Release Overview and Select Games by Jonathan Rosenthal, CCC, December 16, 2018
External Links
Chess Engine
Misc
- Winter from Wikipedia
- Winter - Wiktionary
- winter - Wiktionary
- Winter (disambiguation) from Wikipedia
- Summer and Winter Schools | ETH Zurich
- Wintel from Wikipedia
- AI winter from Wikipedia
- Winter (surname) from Wikipedia
- Edward Winter (chess historian) from Wikipedia
- Johnny Winter - Winter Ballade, ina.fr 1970, YouTube Video
- feat. Tommy Shannon on bass and Uncle John Turner on drums
References
- ↑ Image clipped from Winter views from our floor by Bertrand Meyer, ETH Zurich, Gray moment with Zentralbibliothek and Predigerkirche in the foreground, Lake Zurich, Grossmünster, Fraumünster and St. Peter behind, in the background foothill of Uetliberg, from Bertrand Meyer's ETH home page
- ↑ Winter/statistics.h at master · rosenthj/Winter · GitHub
- ↑ Winter/linear_algebra.h at master · rosenthj/Winter · GitHub
- ↑ Winter Released by Jonathan Rosenthal, CCC, January 08, 2018
- ↑ Re: On-line engine blitz tourney April by Harm Geert Muller, CCC, April 22, 2017
- ↑ based on Winter Released by Jonathan Rosenthal, CCC, January 08, 2018
- ↑ Re: Winter Released by Jonathan Rosenthal, CCC, January 09, 2018
- ↑ k-means clustering from Wikipedia
- ↑ K Means by Chris Piech
- ↑ The EM Algorithm for Gaussian Mixtures - Probabilistic Learning: Theory and Algorithms, CS 274A (pdf) University of California, Irvine
- ↑ Mixture Models & EM algorithm Lecture 21 (pdf) by David Sontag, New York University
- ↑ Re: Tapered Eval between 4 phases by Jonathan Rosenthal, CCC, October 16, 2017
