User:Dennette/chess

Necessity and Sufficiency in Computer Chess Algorithms

by

Dennette Arthur Harrod, Jr

Dennette@WiZ-WORX.com

April 24, 1980

Revised – 2009-09-03

Preface

This is a paper that I wrote in 1980, while an employee at Xerox. I added to it in September of 1980, and again in March of 1982. I used a Xerox Alto computer, and had created my own 5x7 dot matrix font for showing terminal dialogs in system user manuals. In 1997, I scanned the 25 year old hardcopy and used OCR software to reconstruct it, and have just recently figured out how to represent complex mathematical equations and Unicode for the chess symbols (which did not exist back then).

I am currently working on two versions, a Micro$oft Word document, and this Wikipedia essay, using each to enhance the other. Imagine my delight to find articles for Kilobaud Microcomputing, KIM-1, Microchess, and the Sicilian Defence, Najdorf Variation (ECO B96). I have even linked some of my ray-traced renderings of these positions.

I have discarded all of the KIM-1's hardware during various moves over the decades, but I still have two of them with full documentation, one being in NRFB state. OTOH, there is a freeware KIM-1 simulator for Windows that runs the original Microchess, and someone else translated the 6502 program into C with a TTY interface.

Have a better one! Dennette (talk · contribs) _{00:37, 3 September 2009 (UTC)}

Abstract

The purpose of this paper is to discuss some of the necessary parameters for a successful chess-playing algorithm. I shall attempt to define and demonstrate correctness and completeness in a chess automaton, enumerate “sufficient' and “necessary” conditions to evaluate same, and provide some benchmarks for comparison of algorithm performance. While the algorithm under discussion is Peter Jennings’ Microchess 1.6, the axioms developed apply equally well to SARGON or to Slate & Atkin's CHESS 4.7.

Introduction

All of the examples will use a modified Algebraic Chess Notation (ACN), with the modification being special characters for the pieces, e.g.,

♔ = king    ♘ = knight   × = capture  
♕ = queen   ♗ = bishop   + = check
♖ = rook                  # = checkmate

ACN is the only notation recognized by the FIDE (World Chess Federation) for recording games in tournaments, and will be the required notation for USCF (United States Chess Federation) tournaments after January 1, 1981. The use of symbols for piece-names is recommended for publications to avoid the confusion of languages, i.e. “B” for BISHOP in English is “F” for FOU in French and “L” for LOPER in Dutch.

A notation similar to ACN is used to describe board configurations. This is the standard notation used to present “puzzles” in chess journals, and includes a “checksum” or count of the number of pieces each side has on the board. Boards are illustrated in the same format as printed by the author's TTY-33ASR using English first letter abbreviations (except “N” for KNIGHT to avoid confusion with “K” for KING) and a preceding minus sign (“-”) for black pieces. In all illustrations, white moves from the bottom row to the top.

Microchess 1.0 runs on an unexpanded KIM-1 microcomputer, which means the system requires no added memory or external peripherals (it is small enough to load from the on-board hex-keypad, but it is delivered on a KIM-1 formatted audio cassette). It occupies all of the KIM-1's RAM memory, and has three levels of play.

I shall henceforth refer to the three levels of play as three distinct algorithms. Here are the names I shall use, the average time for a move, Mr. Jennings’s descriptions of them, and mine:

Microchess 0.0	3 Sec.	super-blitz	idiot
Microchess 0.5	10 Sec.	blitz	imbecile
Microchess 1.0	100 Sec.	normal	moron

All three algorithms are incorrect, and therefore incomplete, but be not quick to criticize Mr. Jennings … like the dog walking on its hind legs, it is not done well, but it is remarkable that it is done at all.

As for my descriptions of the three versions, the dictionary defines idiot, imbecile, and moron as “fools” or “mental cripples”. However, while a moron can be taught to perform simple household chores (with supervision), an idiot is not even smart enough to be toilet-trained.

For the work presented here, I used a KIM-1 with 12K of added memory, so Microchess was relocated into a contiguous section of memory. All address references, however, refer to the algorithm as provided by the vendor. The “book opening” facility has been disabled. Routines have been added to display the board on request, and all moves are echoed as sentences in English Descriptive Chess Notation (EDCN). (This echoing will ultimately be vocalized by a speech-synthesizer, but for now each word/phrase is output to the TTY as a string of ASCII characters.)

Background

In February 1950, Claude Shannon published his famous paper, A chess-playing machine, in Scientific American. (See also: Programming a Computer for Playing Chess) If you have not read his paper yet, go to your friendly neighborhood library and look it up. It's only four pages long, and takes less than 20 minutes to read on a microfilm viewer.

Although it was written nearly 60 years ago, virtually all of the chess algorithms in use in the West today are based on it. Mikhail Botvinnik developed an entirely different kind of algorithm in 1967 that incorporates sensitivity to treats, forks, pins, the mobility of pieces and unblocking, but requires the use of complex arithmetic and imaginary numbers.

Of passing interest in Shannon's paper is his reference to computers as “complicated devices composed of thousands of vacuum tubes”. This may have been a true statement in 1950, but I doubt if there is still a “vacuum tube” computer in commercial service today. In fact, the KIM-1 is faster and more powerful than anything that existed up to that time.

Within this paper, I shall make frequent use of the term “algorithm”. Shannon used the term “machine” in his paper, and conceptually, we mean the same thing. However. I shall provide the strict definition of an algorithm, and this definition shall be operative throughout.

A PROCEDURE is a finite sequence of steps, possibly iterative or recursive, that leads to the solution of a problem.

An ALGORITHM is a PROCEDURE that is guaranteed to terminate under all conditions.

Benchmark positions

Shannon's Sacrifice

In his paper, Mr. Shannon gave an example of a mate-in-three puzzle, which I shall refer to as Shannon's Sacrifice (fig.1) because it requires the sacrifice of a rook and the queen for white to force check-mate.

Fig. 1 - Shannon's Sacrifice

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

White to play and mate in three moves.

Shannon's Sacrifice in Forsyth–Edwards Notation (FEN):
3r2kr/ppp2n1p/7B/5q1N/1bp5/2Pp4/PP2RPPP/R2Q2K1

This is the solution to Shannon's Sacrifice: 1. ♖e8+ ♖×e8 2. ♕g4+ ♕×g4 3. ♘f6#

This is an example of a “forced win for white”, and Shannon cited it as an example of how an algorithm (“machine”) of the type he described, “will play a brilliant game”. Without bandying the semantics of “brilliant”, we shall expand this assumption into a rule:

A chess algorithm is SHANNON-COMPLETE if-and-only-if it will solve all mate-in-three puzzles.

For clarification, we will use this definition of a mate-in-three:

A MATE-IN-THREE PUZZLE is a chessboard configuration such that for the player having the move, there exists at least one move from which all subsequent game-trees terminate in mate on (at most) the third move.

Promotion dilemma

It can be reasoned that a brute-force tree-searcher can solve any mate-in-three, but this assumes a qualifier: the algorithm has some cognizance of pawn-promotion, and recognizes that “queening” may lead to a stalemate. As illustrated by the famous Promotion Dilemma (fig. 2), promoting a pawn to a knight results in checkmate, while promoting to a queen, rook or bishop produces a stale-mate (black Is not in check, but has no legal move, so the game is a draw).

Fig. 2 – Promotion Dilemma

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

This underlines an often over-looked deficiency in chess algorithms, and a bug which prevents them from being Shannon-complete. In fact, an algorithm that does not consider pawn-promotion is incorrect, because it is not playing with a full set of rules!

One of the best ways to judge the performance of an algorithm, and to gauge the effect of any modifications thereto, is to have the program play against itself. This brings up another rule:

A chess algorithm is SHANNON COMPLETE if-and-only-if it can play either black or white from an arbitrary board configuration.

Opening board

One of the deficiencies of Microchess 2.0 for the APPLE II is that it cannot resume play from an interrupted game. A second is that it cannot change sides and play against itself. The following is the game that Microchess 1.0 will play against itself. (I have not had access to two APPLEs to try the 2.0 algorithm.)

When I began the study of chess automatons, I recognized a need for benchmarks, or situations that could be used as a measure of performance or change. Shannon’s Sacrifice (fig.1) should be included in the list of benchmark positions because it tests the completeness of an algorithm. The Promotion dilemma (fig. 1) will help establish correctness, and represents the most frequently overlooked flaw. Microchess 1.0 is not Shannon-complete because it cannot solve Shannon's Sacrifice; it plays itself to a draw by perpetual check after 4 moves.

1. e4 e5 2. ♕h5 ♘f6 3. ♕×e5+ ♗e7 4. ♗c4 ♘g4 5. ♖×g7 Bf6 6. ♕×f7# drawn

Microchess 1.0 is incorrect because it cannot solve the Promotion Dilemma; it promotes to a queen and permits the stalemate.

What other qualifications apply to correctness? One may seem obvious, but it must still be verbalized:

A chess algorithm is INCORRECT if it ignores a move-and-mate.

SpaFis72 (Najdorf)

Fig.3a – SpaFis72 (Najdorf)

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h
Moves	1. e4 c5 2. ♘f3 d6 3. d4 c×d4 4. ♘×d4 ♘f6 5. ♘c3 a6 6. ♗g5 e6 7. f4
ECO	B96
Parent	Sicilian Defence

The Najdorf Variation of the Sicilian Defence is one of the most complex and respected of all chess openings. It is one of Black's most popular responses to 1.e4. The opening is named after the Polish-Argentinian Grandmaster Miguel Najdorf.

Fig.3a is a position reached after white's 7th move during the 7th, 11th, and 15th games of the Spassky-Fischer match in 1972. (For brevity, I shall refer to this configuration as SpaFis72.) It seems reasonable to use this position as a benchmark simply because it occurred 3 times during a single world championship match. It is called the Najdorf variation of the Sicilian Defence (ECO B96), and prior to this match, Bobby Fischer (black) had never lost with it.

Fig.3b – after 26. ♔h3

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Microchess 0.0, the dumbest version, can be proven incorrect in play against itself from this position as demonstrated by Fig.3b, which occurs after 26 ♔h3.

With black to move, … ♕h5# is the obvious choice. However, Microchess 0.0 played … ♖g5, lost its remaining bishop to white's rook, and overlooked the mate a second time! From this, one may safely conclude that the algorithm is incorrect, since the goal, after all, is to win, and the algorithm blatantly ignored two opportunities to call checkmate.

From the forgoing discussion, we can derive two more axioms:

A chess algorithm is SHANNON COMPLETE if-and-only-if it is not INCORRECT.

and:

A chess algorithm is INCORRECT if it cannot be guaranteed to find the best move.

This may seem an insurmountable task (guaranteeing the best move), but this is because we cannot define the “best” move. It turns out that we don't have to. As Shannon points out, due to the physical limits of computability, we are resigned to “having the machine play a reasonably skillful game, admitting occasional moves that may not be the best.”

Nonetheless, if we can demonstrate that an algorithm cannot examine ALL possible legal moves, then by definition, it cannot be GUARANTEED to find the BEST move. This simply says that any algorithm that does not include en-passant captures (for example) is incorrect, and therefore cannot be complete.

Tightrope

Fig. 4 - Tightrope

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Mate in three for white,
mate in four for black

The best benchmark I have found to date is fig.4, which I call Tightrope. There is an interesting property to arbitrary board configurations - it is impossible, unless the king is in check, to tell which player has the move (whose turn it is). Tightrope may be thought of as two puzzles in one because If it is white's turn, there is a forced mate-in-three (a classic knight combination), whereas black can force a mate-in-tour if given the first move (a queen sacrifice).

Forsyth–Edwards Notation:
6rk/q3N1p1/4b1pp/2pn4/5N2/3B4/PPP5/K7

The win for white is rather straightforward: 1. ♘f4×g6+ ♔h7 2. ♘f8+ ♔h8 3. ♘e7-g6#

For black, the win is less clear: 1. … ♕×a2+ 2. ♔×a2 ♘c3+ 3. ♔a3 ♖a8+ 4. ♗a6 ♖×a6#

When fed this starting position and started from white, Microchess 1.0 played exactly as required. However, when started from black, something very interesting happened: 1. … ♘×f4 2. ♘×g6+ ♘×g6 3. ♗×g6 ♖×a2#

This quicker win for black is hardly inspired. True, … ♘×f4 frees the bishop to guard a2, sealing white’s doom, but white had no business pawn grabbing in a clinch. White’s shortsightedness can be blamed for this cheapo.

What can be inferred from this exchange? Well, just because black did not find the forced mate doesn’t mean that it is incomplete or incorrect; it is merely inelegant. By this I mean that it achieved its goal (checkmate), but we are left with the feeling that ineptitude on the part of the opponent may have had something to do with it.

Play against itself

This now brings us to consideration of what can be expected of an algorithm playing with against itself.

If a correct algorithm plays itself from an equal position, either the first player will win, or the game will be drawn. Therefore, if the second player wins, either the position was not equal, or the algorithm is incorrect.

I shall not dwell on the proof of this assertion, except to mention that an algorithm is its own equal, and this places chess in the family of “first player win” games for all subsequent discussions: we will assume that neither side commits itself to an exchange which it cannot win. Also, as Shannon reminded us, “no one plays a perfect game”, otherwise chess would be a puzzle, like the SOMA cube, or the Tower of Hanoi, rather than a game.

A corollary to the above assertion quickly reveals itself:

A chess algorithm is INCORRECT if it plays against itself from an unequal position, and the side having the advantage fails to win.

The Tightrope configuration is an example of an unequal position, where the advantage is always to the player having the first move. The reason is that there exists, for each scenario, one or more paths which unavoidably lead to checkmate, and therefore it can be proven that the second player can win only as a result of incorrect play on the part of the first player.

Using the previous discussions and examples, let us now examine the modifications to Microchess 1.0 suggested by Chris McCormack in the February, 1980 issue of Kilobaud Microcomputing. I submit that the revised algorithm (which shall be known as Microchess 1.1 for the remainder of this paper) is not an improvement, and is in fact inferior.

While the following discussion may seem academic to some since Microchess has already been proven to be incorrect, it nonetheless demonstrates the kind of quantitative (and qualitative) judgments that can be made about modifications to algorithms.

Performance

Opening board

The first benchmark is the opening board. Microchess is easily modified so that it does not play from a “book” opening, and this is the mode that must be used. This benchmark tests the algorithm's ability to get through the opening phase of the game.

Fig. 5 – After 5. … ♗c5.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

White to move and mate

Microchess 1.0 plays 1. e4 e5 (1. P-K4 P-K4), which is a sane opening, and white mates on move 6: 1. e4 e5 2. ♕h5 ♘f6 3. ♕×e5+ ♗e7 4. ♗c4 ♘g4 5. ♕×g7 ♗c5 6. ♕×f7#

On the other hand, Microchess 1.1 plays 1. c3 e6 (1. P-K3 P-K3), and plays a singularly uninspiring game of 56 moves which terminates in a draw by repetition. White throws away the queen, and black consistently fails to seize the initiative, instead making lots of noise with the queen.

For benchmark 1, Microchess 1.1 rates slightly inferior.

Tightrope

The second benchmark is Tightrope. Playing white, Microchess 1.1 finds the mate-in-three with no problem. However, as black it gets lost in its underwear and draws by repetition: 1. … ♕×e7 2. ♘×g6+ ♔h7 3. ♘f8+ ♔h8 4. ♘g6+ ♔h7 5. draw

For benchmark 2, Microchess 1.1 is demonstrably inferior.

Shannon's Sacrifice

The third benchmark is Shannon's Sacrifice. Since Microchess 1.0 failed this test, Microchess 1.1 was not expected (on the basis of performance so far) to do much better, and it certainly lived up to expectation.

<more to come>

SpaFis72

The fourth benchmark is SpaFis72. Having set the precedent in International Grandmaster play to allow the same sequence of 7 moves to occur in 3 games of a single match, we are obliged to allow the same board to be setup not from the standard opening (all pieces on their “home” squares), but from a position of equilibrium somewhere along the game-tree of an accepted opening, in this case, the Najdorf variation of the Sicilian Defence.

<more to come>

Promotion dilemma

The fifth benchmark is Promotion dilemma.

<more to come>

• D'oh! … There should be more here, but it has been lost over the years … I guess I'll have to research it again. — 2009-08-14

Summary

The following is a summary of the conditions for completeness and correctness as presented in this paper.

A Chess Algorithm is SHANNON-COMPLETE if-and-only-if:

1. It can be started with an arbitrary board configuration, and
2. It can accept/echo moves in Descriptive or Algebraic notation, and
3. It can solve all mate-in-three puzzles (such as Shannon's Sacrifice), and
4. It is not INCORRECT.

These conditions are NECESSARY conditions, meaning an algorithm is Shannon-complete only if it fulfills ALL of them.

A Chess Algorithm is INCORRECT if:

1. It generates/permits illegal moves, or
2. It ignores a move-and-mate, or
3. It cannot be guaranteed to find the best move, i.e.

It is ignorant of Castling as a possible reply, or

It is ignorant of En-Passant as a possible reply, or

It is ignorant of Pawn Promotion as a possible reply.

These conditions are SUFFICIENT conditions, meaning an algorithm is incorrect if it fulfills ANY of them.

Harrod's Chess Axiom

A chess algorithm that is incapable of generating all possible legal moves cannot be guaranteed to find the best move.

Proof:

∀(B,P⊂B) ( β∈[μ(B,f,t)] | f∈P ∧ t∈π(B,f) ∧ λ(B,f,t) ) §

For any arbitrary chessboard B, and its subset P (squares containing the pieces belonging to the player with the move), the best move β is member of the set of moves μ (from squares f to squares t on board B), such that:

1. f is a member of P (the player has a piece on B(f)), and
2. t is a member of B which is derivable from f according to the generating function π (it is possible to move from B(f) to B(t)), and
3. the validating function λ is TRUE (it is legal to move from B(f) to B(t)).

Q. E. D.

This axiom applies to most two-player board games, such as checkers, go, backgammon, etc.

In English, this means that the best move must be a member of the set of possible-legal moves, a set which is defined by the move generating function π, and the move validating function, λ.

The π (possible) function takes as input a square and a board configuration, and returns a list (possibly empty) of squares that the piece on the square in question can move to. However, it may not be legal to move the piece to some or all of the squares on the list.

The λ (legal) function takes as input two squares and a board configuration, and returns TRUE or FALSE to indicate the legality of moving the piece from the first square to the second. As a minimum, λ invokes π for all pieces belonging to the opposing color to insure that the king would not be in check as a result of the move, and recursively applies itself to the possible replies in order to validate their legality.

Possible-legal moves

To generate the set of possible-legal moves:

POSLGL(B,P) = ( [f,t] | f∈p ^ t∈POSMOV(B,f) ^ LGLMOV(B,f,t) )

{define data types to be used}

type SQUARE : [0..63];
type BOARD  : SQUARE[64];
type MOVE   : BOARD[16];

{define external functions to be used}

extern POSMOV( BOARD, SQUARE ): BOARD; 	{generate possible moves}
extern LGLMOV( BOARD, SQUARE, SQUARE): bool; 	{validate legal move}

{define the “potential move” function}

func POSLGL( B, P : BOARD): MOVE;

SQUARE: F, T ;  	{temps for current “from” and “to” squares}
BOARD: G;       	{temp for possible “to” squares}    

beg
   POSLGL ← ∅;				{initialize to empty}
   forall F in P do
      G ← POSMOV( B, F );		{find moves for current piece}
      forall T in G do
         if LGLMOV( B, F, T )		{find moves for current piece}
            then POSLGL[F] ← POSLGL[F] union T;	{add to set}
         fi
      od
   od
end

Wirth Syntax Notation (WSN)

Main article: Wirth syntax notation

from Communications of the ACM 20,11 (Nov 77), 822-823

Wirth Syntax Notation, unlike BNF (Backus–Naur Form), can be defined using itself:

SYNTAX	        =	{ PRODUCTION } .

PRODUCTION	=	IDENTIFIER "=" EXPRESSION "." .

EXPRESSION	=	TERM { "|" TERM } .

TERM		=	FACTOR { FACTOR } .

FACTOR	        =	IDENTIFIER
		|	LITERAL
		|	"(" EXPRESSION ")"
		|	"[" EXPRESSION "]"
		|	"{" EXPRESSION "}" .

IDENTIFIER	=	letter { letter } .

LITERAL	        =	"""" character { character } """""

Semantics of the enclosing braces...

Parenthesis "()" Alternative
	- Must choose one and only one: (A|B)C → AC | BC

Square-brackets "[]" Optional
	- May be omitted: [A]B → B | AB

Curly-braces "{}" Repetition
	- Zero or more occurrences: {A}B → B | AB | AAB | AAAB | …

WSN for English Descriptive Chess Notation (EDCN)

1.	EDCN	= 	INTEGER ( MOVE | "…" ) [ MOVE ] .

2.	MOVE	= 	PIECE "-" SQUARE
		|	PIECE "x" PIECE
		|	CASTLE .

3.	PIECE	=	( SIDE | MAN | "P" ) ["(" SQUARE ")" ] .

4.	SQUARE	=	FILE RANK .

5.	FILE	=	SIDE [ MAN ] 
		|	MAN .

6.	RANK	=	( "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" ) .

7.	SIDE	=	"K" | "Q" .

8.	MAN	=	"R" | "N" | "B" .

9.	CASTLE	=	"0-" ( "0" | "0-0" ) .

Examples

    SQUARE  —  "K4", "QN3", "B7"

    PIECE   —  "Q", "P(KB2)", "N(R5)"

    MOVE    —  "P-K4",  "NxR",  "0-0-0", "B(KR1)xP(QN7)"

Remember, syntax and semantics are different, so it is possible for this language to generate (recognize) such gibberish as:

    "B(Q3)-Q3", "P(KB4)-QR1", and "KxK"

WSN for configuration language

1.	DESCRIPT	= 	( "wh" | "bl" ) ":" "♔" SQR
 				{ "," NAME SQR { "/" SQR } } .

2.	NAME		=	"♔" | "♕" | "♖" | "♘" | "♗" | "♙" . 

3.	SQR		=	( "a" … "h" ) ( "1" … "8" ) .

WSN for Algebraic Chess Notation

1.	MOVE		= 	PIECE [ SQUARE "-" ] SQUARE
 			|	NAME "×" NAME
			|	FILE FILE
			|	FILE "×" NAME
			|	"0-" ( "0" | "0-0" ) .

2.	PIECE		=	"♔" | "♕" | "♖" | "♘" | "♗" . 

3.	NAME		=	PIECE [ SQUARE ]
			|	SQUARE .

4.	SQUARE	        =	FILE RANK .

5.	FILE		=	"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" .

6.	RANK		=	"1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" .

Examples

For example, this is Shannon’s Sacrifice …

WH:♔g1,♕d1,♖a1,♘h5,♗h6,♙a2/b2/c3/f2/g2/h2(11); 
BL:♔g8,♕f5,♖d8/h8,♘f7,♗b4,♙a7/b7/c7/c4/d3/h7(12). 

… with the solution …

1. ♖e8+ ♖×e8 2. ♕g4+ ♕×g4 3. ♘f6# 

Added September 22, 1980

The following is a transcript from an interactive “glass chessboard” program (written in FORTRAN) that demonstrates parsing techniques. It knows enough about chess to be able to move pieces around on the board, but only the moves you provide. It is useful for replaying games printed in magazines. A facility exists for creating board configurations other than the initial board; this is good for trying to solve mate-in-4 problems.

The program consists of a library of subroutines to parse and validate moves expressed in English Descriptive Chess Notation (EDCN). The author's intention was to patch these routines into an existing chess-playing program so that it could be made more “user friendly”. As it turns out, the author is currently re-writing the algorithms in 6502 machine language as a cover for Microchess.

The routines that provide the “possible moves” function are designed to interface with a speech synthesizer and articulate the moves through a speaker. For now, another routine is simulating the synthesizer by printing the words character by character on a Teletype. Each “word” in the chess vocabulary (the 6 piece names, the 8 numbers, “moves to”, “captures”. etc., 24 in all) is represented by a single byte of data. Just as the synthesizer's driver software would use the byte as an index into a table of “phoneme” strings, the simulator uses a table of ASCII character strings.

This dialog represents a practical implementation of the POSLGL algorithm based on Harrod's Chess Axiom. The program will not allow illegal moves, but it is smart enough to allow abbreviated input, i.e., “B/QB4xP/KB7” can be input as “BxP”, assuming there is no ambiguity in the actual board configuration. Ambiguities occur frequently in printed chess games, and sometimes you must play several moves ahead to resolve which bishop captured which pawn. The parser demonstrated here will inform you of the ambiguous choices, display the current board configuration, and terminate abnormally, but the 6502 version will prompt for resolution (“Which PAWN?”) and continue.

This work has been done in the process of developing a vocal input/output system for interfacing applications programs to speech recognizers and synthesizers. EDCN is just an example of a Well Formed Language that can be used to alter the state of a finite automata, in this case, a chess-playing program.

Note that the game replayed here is the one that Microchess 1.0 plays against itself.

1. e4 e5
2. ♕h5 ♘f6
3. ♕×e5+ ♗e7
4. ♗c4 ♘g4
5. ♕×g7 ♗c5
6. ♕×f7#

Virtual chessboard (FORTRAN)

!CHESS.

*** VIRTUAL CHESSBOARD *** VER. A03
*** 10:09:10  Wed Nov 21, 1979

do you want the initial board? YES

***************************

white's 1st move? P-K4
black's 1st move? P-K4

***************************

white's 2nd move? Q-R5
black's 2nd move? N-B3

*** NOT SPECIFIC ENOUGH

-R-N-B-Q-K-B-N-R
-P-P-P-P *-P-P-P
 . * . * . * . *
 * . * .-P . * Q
 . * . * P * . *
 * . * . * . * .
 P P P P . P P P
 R N B . K B N R

	1st	N/QN1-Q83
	2nd	N/KN1-KBS

black’s 2nd move? N-KB3

***************************

white's 3rd move? Q*P/K5
black's 3rd move? B-K2

***************************

white's 4th move? B-B4
black's 4th move? N-N5

***************************

white's 5th move? Q*P/N7
black's 5th move? B-B4

 
***************************

white's 6th move? BOARD

-R-N-B-Q-K * .-R
-P-P-P-P *-P Q-P
 . * . * .-B . *
 * . * . * . * .
 . * B * P *-N *
 * . * . * . * .
 P P P P . P P P
 R N B . K . N R

white's 6th move? POSSIBLE

*** GENERATE ALL POSSIBLE MOVES

 1st	King on King One moves to King Two
 2nd	                 moves to King Bishop One
 3rd	                 moves to Queen One

 4th	Queen on King Knight Seven captures Rook on King Rook Eight CHECK
 5th	                           moves to King Knight Eight CHECK
 6th	                           moves to King Bishop Eight CHECK
 7th	                           captures Pawn on King Rook Seven
 8th	                           captures Pawn on King Bishop Seven MATE
 9th	                           moves to King Rook Six
19th	                           moves to King Knight Six
11th	                           moves to King Knight Five
12th	                           captures Knight on King Knight Four
13th	                           captures Bishop on King Bishop Six

14th	Knight on Queen Knight One moves to Queen Bishop Three
15th	                           moves to Queen Rook Three

16th	Knight on King Knight One moves to King Rook Three
17th	                          moves to King Bishop Three
18th	                          moves to King Two

19th	Bishop on Queen Bishop Four moves to Queen Five
20th	                            moves to King Six
21st	                            captures pawn on King Bishop Seven CHECK
22nd	                            moves to Queen Knight Five
23rd	                            moves to Queen Rook Six
24th	                            moves to Queen Three
25th	                            moves to King Two
26th	                            moves to King Bishop One
27th	                            moves to Queen Knight Three

28th	Pawn on Queen Rook Two moves to Queen Rook Three
29th	                       moves to Queen Rook Four

30th	Pawn on Queen Knight Two moves to Queen Knight Three
31st	                         moves to Queen Knight Four

32nd	Pawn on Queen Bishop Two moves to Queen Bishop Three

33rd	Pawn on Queen two moves to Queen Three
34th	                  moves to Queen Four

35th	Pawn on King Four moves to King Five

36th	Pawn on King Bishop Two moves to King Bishop Three
37th	                        moves to King Bishop Four

38th	Pawn on King Knight Two moves to King Knight Three

39th	Pawn on King Rook Two moves to King Rook Three
40th	                      moves to King Rook Four

white's 6th move? Q*P/B7

CHECKMATE

-R-N-B-Q-K * .-R
-P-P-P-P * Q *-P
 . * . * .-B . *
 * . * . * . * .
 . * B * P *-N *
 * . * . * . * .
 P P P P . P P P
 R N B . K . N R

Added March 2, 1982

The author's KIM-1 system acquired a speech-synthesizer in August 1981. The portion of Microchess which had been displaying text-strings on a TTY 33ASR was modified to make use of this new hardware (a VOTRAX SPEECH-PACr), and with somewhat of a “Cylon” accent, it can now articulate “bishop on queen bishop four captures pawn on king bishop seven”, or whatever move was just made, either by the human or the machine.

This new automaton, which, in deference to its ability, has been christened WDPSHR (i.e., WooD-PuSHeR), uses a bit-mapped video display with 320x200 pixel resolution. Each board square is 24x24 pixels, each piece is 16x16, and each piece has a “mask” which allows it to cover only the outline of the piece.

In conjunction with a joystick, users may “pick-up” a piece, and then move it smoothly about the board in a direction and velocity proportional to the displacement of the joystick. Simply returning the joystick to the center-position stops the movement of the piece, and after a 0.25 second delay, the piece is “snapped” to the center or the square within which most of the piece lies. This system has proven to be very user-friendly, with only minimal explanation required to operate, and after the tenth move by a novice, no supervision is required.

WDPSHR 2.5 represents the egonomist’s delight, in that the software is designed to use “black-boxes”, and the joystick can be replaced by electro-galvanic skin-response sensors (such devices used for lie-detectors, electro cardiograms, and bio-feedback) which would enable individuals with limited motor skills to interact with the system simply by “thinking” about the move. While the author has yet to implement such hardware, the design in no way precludes such a mechanism.

A future version will contain a speech-recognizer, but the “virtual joystick” approach seems to be the best input mechanism since it can also be used by the verbally impaired. Most hearing-impaired computer users will never be able to use voice-input systems, because they will invariably mispronounce the words that they have only read, and never heard.

Added 2009-04-12

Krinitskii's Upper Bound

The number of ways all arbitrary combinations of chess pieces may be arbitrarily placed on a chessboard. (There must always be at least the two kings on the board.)

$\sum _{k=0}^{30}C_{30}^{k}\cdot P_{64}^{k+2}$

Combinations: How many ways can you randomly select k out of m things, e.g., 5 out of 32 pieces?

$C_{m}^{k}={k! \over (m-k)!k!}$

Permutations: How many ways can you randomly place k objects in m locations, e.g., 5 pieces on 64 squares.

$P_{m}^{k}={m! \over (m-k)!}$

Factorial: The product of all positive integers less than or equal to n.

n! = 1 × 2 × 3 × ... × (n-1) × (n)

There must be at least two pieces (the kings) in play for a valid board position.

With just 2 pieces (the kings), there are 249,984 possible ways to arrange them on 64 squares. However, not all of them are legal configurations, e.g., any board where the two kings are on adjacent squares.

With 3 pieces, there are only 30 ways to select one piece besides the two kings, but there are over 15 million ways that 3 pieces can be arranged on a chessboard, so that’s over 450 million possible board configurations.

With 4 pieces, there are 435 ways to select 2 out of 30, and over 914 million ways to arrange them, for a total of nearly 400 billion configurations.

You get the idea … suffice to say that the upper bound is in the range of 1.54x10⁵⁵.

# 	k	k!	        C(k,30)	P(k+2,64)	C(k,30)*P(k+2,64)

2	0	1       	1	249,984	        249,984
3	1	1	        30	15,249,000	457,471,000
4	2	2	        435	914,941,000	398,000,000,000
5	3	6	        4060	53,981,500,000	219,165,000,000,000
6	4	24	        27405	3.13E+012	8.58E+016
 	 	 	 	 	 
28	26	4.03E+026	27405	1.23E+047	3.37E+053
29	27	1.09E+028	4060	4.30E+050	1.74E+054
30	28	3.05E+029	435	1.46E+052	6.36E+054
31	29	8.84E+030	30	4.82E+053	1.45E+055
32	30	2.65E+032	1	1.54E+055	1.54E+055

See also

• Standard chess diagram
• {{chess diagram}}
• Chess symbols in Unicode
• Portable Game Notation
• Forsyth–Edwards Notation

External links

• MS-Word .DOC version
• Play Kim-1 Microchess on your PC
• Kim-1 Simulation
• Dennette's Computer Chess Page
• Tightrope 1600x1200 wallpaper
• Najdorf/SpaFis72 1600x1200 wallpaper
• Portable Game Notation Specification and Implementation Guide, Steven J. Edwards
• Translate FEN Chess positions into Wikipedia format