This site is supported by donations to The OEIS Foundation.

Chess

From OeisWiki
Jump to: navigation, search

The fascinating game of chess gives rise to many integer sequences in a natural way - for example, counting the number of possible positions, moves or checkmates after n plys, etc. See also the OEIS index section on chess.

Counting games, diagrams and positions

It is well known that from the initial position each party has 2 x 8 pawn moves plus 2 x 2 knight moves for a total of 20 distinct moves. So several of the chess related sequences have initial terms 20, 400, ...

There are some subtleties requiring precise definitions:

  • diagram = position without castling and en passant information
  • file = a "column" of the board, usually labelled from 'a' to 'h' (for an 8 x 8 board, of course).
  • game = a sequence of legal moves.
  • ply = half-move. Ply 0 is the starting position.
  • position = position with castling and en passant information
  • rank = a "row" of the board, usually labelled from '1' to '8' (for an 8 x 8 board, of course).

Number of games:

A006494 = (1, 20, 400, 8902, 197281, 4865617, 119060679, ...): Number of possible chess games at the end of the n-th ply plus number of games that end in checkmate in fewer than n plies.
This sequence is A048987 plus the cumulative sum of A079485.
A007545 = (1, 20, 400, 8902, 197742, 4897256, ...): Number of chess games with n plies (another version: Up to a(6) this is the number of chess games with all legality constraints removed, even allowing the king to be captured. (his differs from the number of positions in suicide chess, as suicide chess contains compulsory captures.)
A007577 = (1, 20, 400, 8902, 197281, 4865577, ...): Number of chess games with n plies (another version).
A007747: linked to possible scores at a chess tournament
A019319 = (1, 20, 400, 5362, 71852, 815677, 9260610, 94305342, ...): Number of possible chess diagrams after n plies.
A048987 = (1, 20, 400, 8902, 197281, 4865609, 119060324, ...): Number of possible chess games at the end of the n-th ply. (Here the move order matters, as opposed to positions.)
A057745 = (1, 20, 400, 5362, 72078, 822518, 9417683): Erroneous version of A083276. (Two less at n=6 due to positions where en passant is illegal and therefore the position is equivalent to those where it is not available.)
A079485 = (0, 0, 0, 0, 8, 347, 10828, 435767, 9852036, ...): Number of chess games that end in checkmate after exactly n plies.
A083276 = (1, 20, 400, 5362, 72078, 822518, 9417681, 96400068, ...): Number of distinct chess positions after n plies including differences due to availability and possibility of castling and en passant captures.
A089956 = (0, 0, 0, 12, 461, 27004, 798271, 32668081, ...): Number of chess games that end in check (but not checkmate) after exactly n plies.
A089957 = (1, 20, 400, 1862, 9825, 53516, 311642, 2018993, 12150635, ...): Number of chess positions that can be obtained in exactly one way in n plies.
A090051 = (1, 20, 400, 1862, 9373, 51323, 298821, 1965313, 11759158, ...): Number of chess diagrams that can be obtained in exactly one way in n plies. This is also the number of dual-free proof games in n plies.
Number of possible chess games at the end of the n-th ply, starting without some pieces:
A285873 (no queens), A285874 (no rooks), A285875 (no knights), A285876 (no bishops), A285877 (no pawns), A285878 (pawns and king).

Coding squares, moves and positions

To define sequences whose indices or terms = values correspond to positions or possible moves, we need to fix a convention for encoding these.

Obviously, the squares of the chess board can be labelled, e.g., row-wise, by integers s from 0 to n²-1, or from 1 to n². The former choice is convenient because it gives the file f = s % n and rank r = s // n (both numbered from 0 to n-1) through Euclidean integer division '//' and remainder operation '%'. Given that rank 1 (r = 0) is usually on bottom of the diagram, the lower left square would have number s = 0, and the upper right square would have number s = n²-1. The latter choice (numbering from 1 to n²) may be handy especially when one wants to use 0 as a special marker, but is mathematically less convenient, also for what follows.

Any move can unambiguously be coded by giving the departure = starting and destination = ending squares s and e, e.g., as m = s + n² e. Then again one gets back (s,e) from m through s = m % n² and e = m // n². (The castling moves, usually denoted by O-O and O-O-O, are given as the king's move, e.g., 'e1-g1', i.e., m = 4 + 64*6.)

In some situations, e.g., pawnless endgames, one has obvious rotational and mirror symmetries (the symmetry group of the square) making many positions equivalent in some sense (distance to mate, best move, ...). In that case, one may restrict the position of, e.g., one of the kings to 1/8 of the chess board, i.e., the triangle between a1 - d1 - d4, for example.

Coding moves for a single piece

Whenever only one piece is considered, one can code its moves simply by the destination square, or by the difference e - s.

  • For rook moves, these differences are multiples of 1 (for "horizontal" displacements) or n (for vertical displacements), no exceeding a factor +-(n-1) (for an n×n board).
  • For bishop moves, these differences are multiples of n-1 or n+1 (on an n×n board).
  • For knight moves, these differences are always among +/- {n-2, n+2, 2n+1, 2n-1}.
  • For king moves, these differences are always among +/- {1, n, n-1, n+1}.

Knight tours

The famous problem of "knight tours" consists in finding a path for a knight to travel across each square of the board exactly once, starting from a given square and possibly having to end on the starting square. To get uniqueness, one would usually record the lexicographically first sequence (which might differ depending on the chosen coding scheme).

The two obvious "canonical" choices for the starting square might be s = 0 (lower left, a.k.a. 'a1'), and s = (n²-n)/2 (a.k.a. 'd4' for the 8x8 board), but any square within the triangle 'a1' - 'd1' - 'd4' (again for n = 8) will lead to an inequivalent sequence.

The idea of knight moves is used in some other (not chess related) sequences as ... [TO DO: put XREFs here!]

Checkmate related

From initial position

A079485 : Number of chess games that end in checkmate after exactly n plies.

(see also: A089956 Number of chess games that end in check (but not checkmate) after exactly n plies.)

A258110 Number of Mirror Chess games that end in checkmate after exactly n moves.

A274458 White to move: Number of up to 5 man GBR-codes on an 8x8 chessboard having

longest checkmate under perfect play in n moves if any such checkmate exists.

Endgames

Longest checkmate in king and xxx versus king endgame on an n X n chessboard

  additional material | sequence
        queen         |  A225551
        rook          |  A225552
       amazon         |  A225553
       empress        |  A225554  (Cf. A137774, A218244: max. number of nonattacking empresses)
      princess        |  A225555
   bishop + knight    |  A225556  (See also A274683: K+N+B vs K, # positions with mate in n.)
     two bishops      |  A225557
    three knights     |  A227437


Chess or checkers board related

Some sequences do not depend on any rule of chess, but simply on the structure of the checkers board, i.e., an n×n square grid:

  • number of squares (of any size) visible on an n×n chessboard: A000330 = Square pyramidal numbers = (0, 1, 5, 14, 30, ...):
e.g., on a 2×2 board, there are four 1×1 squares, plus the square formed by the entire 2×2 board.

References

History and authorship

Retrieved from "https://oeis.org/w/index.php?title=Chess&oldid=1658707"