Difference between revisions of "Winter"

From Chessprogramming wiki
Jump to: navigation, search
 
(10 intermediate revisions by the same user not shown)
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 29: Line 30:
 
** [[Static Exchange Evaluation]]
 
** [[Static Exchange Evaluation]]
 
==[[Evaluation]]==
 
==[[Evaluation]]==
−
[[FILE:Normal Distribution PDF.svg|border|right|320px|thumb|A set of Gaussians]]
+
* 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>, and since Winter '''0.3''' on [https://en.wikipedia.org/wiki/Fuzzy_clustering#Fuzzy_C-means_clustering Fuzzy C-Means], a more direct generalization of a [[Tapered Eval|tapered eval]] with disjoint phases aka clusters <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69288 Winter 0.3 Release Overview and Select Games] by [[Jonathan Rosenthal]], [[CCC]], December 16, 2018</ref> <ref>[[Mathematician#JCBezdek|James C. Bezdek]], [http://www.legacy.com/obituaries/saltlaketribune/obituary.aspx?n=robert-ehrlich&pid=189574728 Robert Ehrlich], [https://www.researchgate.net/profile/William_Full William Full] ('''1984'''). ''FCM: The fuzzy c-means clustering algorithm''. [https://www.journals.elsevier.com/computers-and-geosciences Computers & Geosciences], Vol. 10, Nos. 2-3, [https://pdfs.semanticscholar.org/64a8/77d135db3acbc23c295367927176f332595f.pdf pdf]</ref>
−
* Non standard approach relies 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>
+
** Assumes [[Chess Position|positions]] encountered in search come from some set of [https://en.wikipedia.org/wiki/K-means_clustering k-means clusters] <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>   
+
** 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  
+
** For each cluster, a separate evaluation function is trained. When the evaluation function is called the relative probability a position stems from each cluster is estimated, the evaluation functions are computed and the final score is returned as the weighted average - a generalization of [[Tapered Eval|tapered eval]] with [[Game Phases|game phases]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65466&start=4 Re: Tapered Eval between 4 phases] by [[Jonathan Rosenthal]], [[CCC]], October 16, 2017</ref>
−
** 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|tapered eval]] with [[Game Phases|game phases]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65466&start=4 Re: Tapered Eval between 4 phases] by [[Jonathan Rosenthal]], [[CCC]], October 16, 2017</ref>
+
* Parameter weights are trained via a mixture of [[Reinforcement Learning|reinforcement]] ([[Temporal Difference Learning|temporal difference]]) learning and [[Supervised Learning|supervised learning]]
−
* Parameter weights are trained via a mixture of [[Reinforcement Learning|reinforcement ]] ([[Temporal Difference Learning|temporal difference]]) learning and [[Supervised Learning|supervised learning]]
+
** Minimizing the [https://en.wikipedia.org/wiki/Cross_entropy cross entropy] loss of a [[Automated Tuning#LogisticRegression|Logistic Regression]] model for each phase
−
** Minimizing the [https://en.wikipedia.org/wiki/Cross_entropy cross entropy] loss of a [[Automated Tuning#LogisticRegression|Logistic Regression]] model for each of the k Gaussians
 
 
** Training converges fast due to [https://en.wikipedia.org/wiki/Linear_model linear model] at the heart  
 
** Training converges fast due to [https://en.wikipedia.org/wiki/Linear_model linear model] at the heart  
 +
* As of '''Winter 0.6.2''', the evaluation function relies on a [[Neural Networks|neural network]] with two main parts. The first part is a non-standard [[Neural Networks#Convolutional|convolutional neural network]] which uses sparsity similarly to [[NNUE]]. This convolutional network is used to calculate [[Pawn Structure|pawn structure]] features, so the output can be reused very often as it gets stored in a separate [[Pawn Hash Table|hash table]] with a high hitrate. The second part is a fully connected network which has as input the output of the convolutional network as well as a set of handcrafted features standard to classical engines, mostly a subset of the features from before neural networks were added to Winter <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74531&start=5 Re: NNUE accessible explanation] by [[Jonathan Rosenthal]], [[CCC]], July 24, 2020</ref>
 
==Misc==
 
==Misc==
 
* [[Perft]]
 
* [[Perft]]
Line 42: Line 43:
  
 
=Forum Posts=
 
=Forum Posts=
 +
==2017 ...==
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65466&start=4 Re: Tapered Eval between 4 phases] by [[Jonathan Rosenthal]], [[CCC]], October 16, 2017 » [[Tapered Eval]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65466&start=4 Re: Tapered Eval between 4 phases] by [[Jonathan Rosenthal]], [[CCC]], October 16, 2017 » [[Tapered Eval]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66266 Winter Released] by [[Jonathan Rosenthal]], [[CCC]], January 08, 2018
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66266 Winter Released] by [[Jonathan Rosenthal]], [[CCC]], January 08, 2018
 
: [http://www.talkchess.com/forum/viewtopic.php?t=66266&start=7 Re: Winter Released] by [[Jonathan Rosenthal]], [[CCC]], January 09, 2018
 
: [http://www.talkchess.com/forum/viewtopic.php?t=66266&start=7 Re: Winter Released] by [[Jonathan Rosenthal]], [[CCC]], January 09, 2018
 
: [http://www.talkchess.com/forum/viewtopic.php?t=66266&start=8 Windows version released] by [[Jonathan Rosenthal]], [[CCC]], January 23, 2018
 
: [http://www.talkchess.com/forum/viewtopic.php?t=66266&start=8 Windows version released] by [[Jonathan Rosenthal]], [[CCC]], January 23, 2018
−
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=68266 Winter 0.2 Release Overview and Select Games] by [[Jonathan Rosenthal]], [[CCC]], Auguat 20, 2018
+
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=68266 Winter 0.2 Release Overview and Select Games] by [[Jonathan Rosenthal]], [[CCC]], August 20, 2018
−
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69288 Winter 0.3 Release Overview and Select Games] by [[Jonathan Rosenthal]], [[CCC]], December 16, 2018
+
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69288 Winter 0.3 Release Overview and Select Games] by [[Jonathan Rosenthal]], [[CCC]], December 16, 2018 » [[TCEC Season 14]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=72284 Winter NN Training Script] by [[Jonathan Rosenthal]], [[CCC]], November 09, 2019
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74531&start=5 Re: NNUE accessible explanation] by [[Jonathan Rosenthal]], [[CCC]], July 24, 2020 » [[NNUE]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=75301 Winter] by [[Jonathan Rosenthal]], [[CCC]], October 05, 2020
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=75301&start=14 Re: Winter] by [[Jonathan Rosenthal]], [[CCC]], July 09, 2021
  
 
=External Links=
 
=External Links=
 
==Chess Engine==
 
==Chess Engine==
 
* [https://github.com/rosenthj/Winter GitHub - rosenthj/Winter: UCI Chess Engine]
 
* [https://github.com/rosenthj/Winter GitHub - rosenthj/Winter: UCI Chess Engine]
 +
* [http://ccrl.chessdom.com/ccrl/4040/cgi/compare_engines.cgi?family=Winter&print=Rating+list&print=Results+table&print=LOS+table&print=Ponder+hit+table&print=Eval+difference+table&print=Comopp+gamenum+table&print=Overlap+table&print=Score+with+common+opponents Winter] in [[CCRL|CCRL 40/15]]
 
==Misc==
 
==Misc==
 
* [https://en.wikipedia.org/wiki/Winter Winter from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Winter Winter from Wikipedia]
Line 63: Line 71:
 
* [https://en.wikipedia.org/wiki/Edward_Winter_%28chess_historian%29 Edward Winter (chess historian) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Edward_Winter_%28chess_historian%29 Edward Winter (chess historian) from Wikipedia]
 
* [[:Category:Johnny Winter|Johnny Winter]] - Winter Ballade, [https://en.wikipedia.org/wiki/Institut_national_de_l%27audiovisuel ina.fr] 1970, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
* [[:Category:Johnny Winter|Johnny Winter]] - Winter Ballade, [https://en.wikipedia.org/wiki/Institut_national_de_l%27audiovisuel ina.fr] 1970, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
−
: feat. [https://en.wikipedia.org/wiki/Tommy_Shannon Tommy Shannon] on bass and [http://yeech.altervista.org/Band/winter_band_john_turner.html Uncle John Turner] on drums
+
: feat. [[:Category:Tommy Shannon|Tommy Shannon]] on bass and [http://yeech.altervista.org/Band/winter_band_john_turner.html Uncle John Turner] on drums
 
: {{#evu:https://www.youtube.com/watch?v=8P0wdTKMDyo|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=8P0wdTKMDyo|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
−
 
 
'''[[Engines|Up one Level]]'''
 
'''[[Engines|Up one Level]]'''
 
[[Category:UCI]]
 
[[Category:UCI]]
 
[[Category:Open Source]]
 
[[Category:Open Source]]
 
[[Category:GPL]]
 
[[Category:GPL]]
 +
[[Category:X86]]
 +
[[Category:X64]]
 +
[[Category:ARM]]
 +
[[Category:PC]]
 +
[[Category:Android]]
 +
[[Category:Linux]]
 +
[[Category:Windows]]
 +
[[Category:NN]]
 +
[[Category:OpenBench]]
 
[[Category:Johnny Winter]]
 
[[Category:Johnny Winter]]
 +
[[Category:Tommy Shannon]]

Latest revision as of 09:35, 10 July 2021

Home * Engines * Winter

Winter in Zurich, ETH Zurich view [1]

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].

Selected Features

[6]

Board Representation

BMI2 - PEXT Bitboards

Search

Evaluation

  • Non standard approach relied on a mixture model [7], and since Winter 0.3 on Fuzzy C-Means, a more direct generalization of a tapered eval with disjoint phases aka clusters [8] [9]
    • Assumes positions encountered in search come from some set of k-means clusters [10]
    • Model is trained via EM algorithm [11] [12] either on database games or positions sampled from search
    • For each cluster, a separate evaluation function is trained. When the evaluation function is called the relative probability a position stems from each cluster 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 [13]
  • Parameter weights are trained via a mixture of reinforcement (temporal difference) learning and supervised learning
  • As of Winter 0.6.2, the evaluation function relies on a neural network with two main parts. The first part is a non-standard convolutional neural network which uses sparsity similarly to NNUE. This convolutional network is used to calculate pawn structure features, so the output can be reused very often as it gets stored in a separate hash table with a high hitrate. The second part is a fully connected network which has as input the output of the convolutional network as well as a set of handcrafted features standard to classical engines, mostly a subset of the features from before neural networks were added to Winter [14]

Misc

Forum Posts

2017 ...

Re: Winter Released by Jonathan Rosenthal, CCC, January 09, 2018
Windows version released by Jonathan Rosenthal, CCC, January 23, 2018

2020 ...

Re: Winter by Jonathan Rosenthal, CCC, July 09, 2021

External Links

Chess Engine

Misc

feat. Tommy Shannon on bass and Uncle John Turner on drums

References

  1. ↑ 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
  2. ↑ Winter/statistics.h at master · rosenthj/Winter · GitHub
  3. ↑ Winter/linear_algebra.h at master · rosenthj/Winter · GitHub
  4. ↑ Winter Released by Jonathan Rosenthal, CCC, January 08, 2018
  5. ↑ Re: On-line engine blitz tourney April by Harm Geert Muller, CCC, April 22, 2017
  6. ↑ based on Winter Released by Jonathan Rosenthal, CCC, January 08, 2018
  7. ↑ Re: Winter Released by Jonathan Rosenthal, CCC, January 09, 2018
  8. ↑ Winter 0.3 Release Overview and Select Games by Jonathan Rosenthal, CCC, December 16, 2018
  9. ↑ James C. Bezdek, Robert Ehrlich, William Full (1984). FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences, Vol. 10, Nos. 2-3, pdf
  10. ↑ K Means by Chris Piech
  11. ↑ The EM Algorithm for Gaussian Mixtures - Probabilistic Learning: Theory and Algorithms, CS 274A (pdf) University of California, Irvine
  12. ↑ Mixture Models & EM algorithm Lecture 21 (pdf) by David Sontag, New York University
  13. ↑ Re: Tapered Eval between 4 phases by Jonathan Rosenthal, CCC, October 16, 2017
  14. ↑ Re: NNUE accessible explanation by Jonathan Rosenthal, CCC, July 24, 2020

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Winter&oldid=25546"