Connectivity

From Chessprogramming wiki
Jump to: navigation, search

Home * Evaluation * Connectivity

Knight's graph [1]

Connectivity,
in computer chess, a loosely defined property to quantify positional play based on the graph theoretical relationship between the chess pieces and the squares they control on the 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, 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 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, ...} [2]. This stems from the idea that the less mobile a piece is, the more protection it needs. The connectivity term encourages pawn chains, and discourages loose pieces. Originally, Kopec et al. used the computation of 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 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 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 [3].

Simplex and Complex

Ron Atkin and Ian H. Witten [4] 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 [5]. 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 updated network properties, interpreted as a time series during the course of the game, may act as an evaluation feature [6].

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

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 [8]. The chess neighborhood is a vector of 17 elements, focusing a square of the chessboard with 16 satellites corresponding to the closest pieces (if any) of the eight ray directions and pieces or empty squares in knight-distance of the eight knight directions.

A board representation as vector of 64 neighborhoods of each square is suited to serve as an input layer of a regression network, whose weights are optimized by gradient descent, along with training positions previously generated using 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 entropy.

ChessNeighbourhood.jpg

The overall model of the Morph learner [9]

See also

Publications

1970 ...

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.

1990 ...

2000 ...

2010 ...

Forum Posts

External Links

References

  1. ↑ Knight's graph showing the number of possible moves from each node, by R. A. Nonenmacher, June 23, 2008, Knight's tour from Wikipedia
  2. ↑ Danny Kopec, Ed Northam, David Podber, Yehya Fouda (1989). The Role of Connectivity in Chess. Workshop on New Directions in Game-Tree Search, pdf
  3. ↑ Mikhail Botvinnik (1984). Computers in Chess: Solving Inexact Search Problems. Springer-Verlag, New York
  4. ↑ Ron Atkin, Ian H. Witten (1975). A Multi-Dimensional Approach to Positional Chess. International Journal of Man-Machine Studies, Vol. 7, No. 6
  5. ↑ Derek Farren, Daniel Templeton, Meiji Wang (2013). Analysis of Networks in Chess. Team 23, Stanford University, pdf
  6. ↑ Derek Farren, Daniel Templeton, Meiji Wang (2013). Analysis of Networks in Chess. Team 23, Stanford University, pdf
  7. ↑ Robert Levinson, Richard Snyder (1993). Distance: Toward the Unification of Chess Knowledge. ICCA Journal, Vol. 16, No. 3
  8. ↑ Robert Levinson, Ryan Weber (2000). Chess Neighborhoods, Function Combination, and Reinforcement Learning. CG 2000, pdf
  9. ↑ Image Fig. 5.3 on pg. 13 from Robert Levinson, Ryan Weber (2000). Chess Neighborhoods, Function Combination, and Reinforcement Learning. CG 2000, pdf
  10. ↑ Re: Whatever happened to Neural Network Chess programs? by Andy Walker, rgcc, March 28, 2000

Up one level

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