Changes

Jump to: navigation, search

Connectivity

11,034 bytes added, 13:26, 16 May 2018
Created page with "'''Home * Evaluation * Connectivity''' FILE:Knight's graph showing number of possible moves.svg|border|right|thumb|[https://en.wikipedia.org/wiki/Knight%2..."
'''[[Main Page|Home]] * [[Evaluation]] * Connectivity'''

[[FILE:Knight's graph showing number of possible moves.svg|border|right|thumb|[https://en.wikipedia.org/wiki/Knight%27s_graph Knight's graph] <ref>[http://commons.wikimedia.org/wiki/File:Knight%27s_graph_showing_number_of_possible_moves.svg Knight's graph] showing the number of possible moves from each node, by [https://commons.wikimedia.org/wiki/User:Nonenmac R. A. Nonenmacher], June 23, 2008, [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour from Wikipedia]</ref> ]]

'''Connectivity''',<br/>
in computer chess, a loosely defined property to quantify positional play based on the [https://en.wikipedia.org/wiki/Graph_theory graph theoretical] relationship between the [[Pieces|chess pieces]] and the [[Squares|squares]] they [[Square Control|control]] on the [[Chessboard|chessboard]]. [[Danny Kopec]], [[Ed Northam]], [[David Podber]] and [[Yehya Fouda]] proposed a connectivity term with some scaling required as sum of products of a value for each own protected pawn and own protected piece in the inverse order of their [[Point Value|point value]], i.e. {P=50, N=35, B=30, R=10, Q=4} times a value looked up by their up to three direct or [[X-ray|x-ray]] protectors, i.e. {Single: P=8.00, B=4.50, N=4.00, R=3.00, K=2.50, Q=2.0; Double: PP=15.00, QK=4.00, ...; Triple: PPN=18.00, ...} <ref>[[Danny Kopec]], [[Ed Northam]], [[David Podber]], [[Yehya Fouda]] ('''1989'''). ''The Role of Connectivity in Chess''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]], [http://www.sci.brooklyn.cuny.edu/%7Ekopec/Publications/Publications/O_24_C.pdf pdf]</ref>. This stems from the idea that the less mobile a piece is, the more protection it needs. The connectivity term encourages [[Pawn Chain|pawn chains]], and discourages [[Loose Piece|loose pieces]]. Originally, Kopec et al. used the computation of [https://en.wikipedia.org/wiki/Entropy entropy], a term taken from physics, which measures the tendency of matter to increase in its level of disorder. A low entropy score was indicative of a high degree of protection and a high connectivity score.

=Trajectories=
More complex models concerning connectivity in chess, also considering [[Mobility#ProgressiveMobility|progressive mobility]], were proposed and elaborated by various researchers. To mention is [[Mikhail Botvinnik]] within his [[Pioneer]] project with the hierarchical mathematical projection (MP) of [[Trajectory|trajectories]], zones consisting of a network of main trajectories conform to attacking or defending plans, opponent's counter trajectories and own supporting counter-counter trajectories <ref>[[Mikhail Botvinnik]] ('''1984'''). ''Computers in Chess: Solving Inexact Search Problems''. Springer-Verlag, New York</ref>.
<span id="SimplexAndComplex"></span>
=Simplex and Complex=
[[Ron Atkin]] and [[Ian H. Witten]] <ref>[[Ron Atkin]], [[Ian H. Witten]] ('''1975'''). ''[http://www.bibsonomy.org/bibtex/2b91106ea980eb48aa505f6b54c130707/dblp A Multi-Dimensional Approach to Positional Chess]''. [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_7.html International Journal of Man-Machine Studies, Vol. 7, No. 6]</ref> labeled a piece and the squares that it attacks a simplex, and simplexes are composed into complexes. By analysis of the simplexes and complexes, Atkin and Witten showed that it is possible to make reasonably effective move predictions using real games as a point of comparison <ref>[[Derek Farren]], [[Daniel Templeton]], [[Meiji Wang]] ('''2013'''). ''Analysis of Networks in Chess''. Team 23, [[Stanford University]], [http://snap.stanford.edu/class/cs224w-2013/projects2013/cs224w-023-final.pdf pdf]</ref>. In line with Atkin and Witten, [[Derek Farren]], [[Daniel Templeton]] and [[Meiji Wang]] proposed a model of four types of networks, support, mobility, position, and tracking networks, where certain [[Incremental Updates|incremental updated]] network properties, interpreted as a [https://en.wikipedia.org/wiki/Time_series time series] during the course of the game, may act as an evaluation feature <ref>[[Derek Farren]], [[Daniel Templeton]], [[Meiji Wang]] ('''2013'''). ''Analysis of Networks in Chess''. Team 23, [[Stanford University]], [http://snap.stanford.edu/class/cs224w-2013/projects2013/cs224w-023-final.pdf pdf]</ref>.

=Distance=
[[Mobility]] as well as connectivity are special cases of the graph-theoretic representation of chess knowledge introduced by [[Robert Levinson]] and [[Richard Snyder]], uniformly based on a single mathematical abstraction dubbed ''Distance'', when squares are only at [[Distance|distance]] 1 <ref>[[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref>.
<span id="ChessNeighborhood"></span>
=Chess Neighborhood=
Related to connectivity and distance is the graph-theoretic representation of Chess neighborhood, proposed by [[Robert Levinson]] and [[Ryan Weber]], as applied in the learning research chess program [[Morph]] <ref>[[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]</ref>. The chess neighborhood is a vector of 17 elements, focusing a [[Squares|square]] of the [[Chessboard|chessboard]] with 16 satellites corresponding to the closest pieces (if any) of the eight [[Direction#RayDirections|ray directions]] and pieces or empty squares in [[Knight-Distance|knight-distance]] of the eight [[Direction#KnightDirections|knight directions]].

A board representation as vector of 64 neighborhoods of each square is suited to serve as an input layer of a [[Neural Networks|regression network]], whose weights are optimized by [https://en.wikipedia.org/wiki/Gradient_descent gradient descent], along with training positions previously generated using [[Temporal Difference Learning|temporal difference learning]]. At the lower level the expected probability of winning of the neighborhoods are learned and at the top they are combined based on their product and [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 entropy].
[[FILE:ChessNeighbourhood.jpg|none|border|text-bottom]]
The overall model of the [[Morph]] learner <ref>Image Fig. 5.3 on pg. 13 from [[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]</ref>

=See also=
* [[Distance]]
* [[Mobility]]
* [[Morph]]
* [[Square Control]]
* [[Trajectory]]

=Publications=
==1970 ...==
* [[Ron Atkin]] ('''1972'''). ''Multi-Dimensional Structure in the Game of Chess''. In [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_4.html International Journal of Man-Machine Studies, Vol. 4]
* [[Ron Atkin]], [[Ian H. Witten]] ('''1975'''). ''[http://www.bibsonomy.org/bibtex/2b91106ea980eb48aa505f6b54c130707/dblp A Multi-Dimensional Approach to Positional Chess]''. [http://www.interaction-design.org/references/periodicals/international_journal_of_man-machine_studies_volume_7.html International Journal of Man-Machine Studies, Vol. 7, No. 6]
* [[Ron Atkin]] ('''1977'''). ''Positional Play in Chess by Computer''. [[Advances in Computer Chess 1]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/xthKCFRJkeM/ZgORiY9-gF0J Re: Whatever happened to Neural Network Chess programs?] by [[Andy Walker]], [[Computer Chess Forums|rgcc]], March 28, 2000</ref>
==1980 ...==
* [[Mikhail Botvinnik]] ('''1984'''). ''Computers in Chess: Solving Inexact Search Problems''. Springer-Verlag, New York
: [[Michael Tsfasman]], [[Boris Stilman]] ('''1984'''). ''The Positional Estimate and Assignment of Priorities''.
* [[Yehya Fouda]] ('''1987'''). ''Computer Chess: A Study of Entropy and Opening Play''. Master's thesis project report. [https://en.wikipedia.org/wiki/San_Diego_State_University San Diego State University]
* [[Danny Kopec]], [[Ed Northam]], [[David Podber]], [[Yehya Fouda]] ('''1989'''). ''The Role of Connectivity in Chess''. [[WCCC 1989#Workshop|Workshop on New Directions in Game-Tree Search]], [http://www.sci.brooklyn.cuny.edu/%7Ekopec/Publications/Publications/O_24_C.pdf pdf]
==1990 ...==
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Jonathan Allen]], [[Edward Hamilton]], [[Robert Levinson]] ('''1997'''). ''New Advances in Adaptive Pattern-Oriented Chess''. [[Advances in Computer Chess 8]]
==2000 ...==
* [[Boris Stilman]] ('''2000'''). ''[http://atimopheyev.narod.ru/LG01pdf_in_HTML/LG01_eng.HTML Linguistic Geometry - From Search to Construction]''. Operations Research/Computer Science Interfaces Series. Springer US, ISBN: 978-0-7923-7738-2, [http://atimopheyev.narod.ru/LG01pdf_in_HTML/LG01_eng.HTML#ACKNOWLEDGMENTS Acknowledgments]
* [[Robert Levinson]], [[Ryan Weber]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_9 Chess Neighborhoods, Function Combination, and Reinforcement Learning]''. [[CG 2000]], [https://users.soe.ucsc.edu/~levinson/Papers/CNFCRL.pdf pdf]
* [[Daniel Walker]], [[Robert Levinson]] ('''2004'''). ''The MORPH Project in 2004''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
==2010 ...==
* [[Derek Farren]], [[Daniel Templeton]], [[Meiji Wang]] ('''2013'''). ''Analysis of Networks in Chess''. Team 23, [[Stanford University]], [http://snap.stanford.edu/class/cs224w-2013/projects2013/cs224w-023-final.pdf pdf]

=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=55272 LCP] by [[Lyudmil Tsvetkov]], [[CCC]], February 09, 2015 » [[Pawn chain]]
* [http://www.talkchess.com/forum/viewtopic.php?t=55380 Pawn defence] by [[Lyudmil Tsvetkov]], [[CCC]], February 18, 2015

=External Links=
* [https://en.wikipedia.org/wiki/Connectivity Connectivity (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 Connectivity (graph theory) from Wikipedia]
* [https://en.wikipedia.org/wiki/Connected_space Connected space from Wikipedia]
* [https://www.scholarpedia.org/article/Brain_connectivity Brain connectivity - Scholarpedia]
* [https://en.wikipedia.org/wiki/Entropy_%28disambiguation%29 Entropy (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Introduction_to_entropy Introduction to entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Simplex Simplex from Wikipedia]
* [https://en.wikipedia.org/wiki/Simplicial_complex Simplicial complex from Wikipedia]
* [https://en.wikipedia.org/wiki/Q-analysis Q-analysis from Wikipedia]

=References=
<references />

'''[[Evaluation|Up one level]]'''

Navigation menu