# Draw an infinite chessboard in perspective, using straightedge only

I’d like to explain to you how to draw chessboards by hand in perfect perspective, using only a straightedge.  In this post, I’ll explain how to construct chessboards of any size, starting with the size of the basic unit square.

This post follows up on the post I made yesterday about how to draw a chessboard in perspective view, using only a straightedge.  That method was a subdivision method, where one starts with the boundary of the desired board, and then subdivides to make a chessboard. Now, we start with the basic square and build up. This method is actually quite efficient for quickly making very large boards in perspective view.

I want to emphasize that this is something that you can actually do, right now. It’s fun! All you need is a piece of paper, a pencil and a straightedge. I’ll wait right here while you gather your materials. Use a ruler or a chop stick (as I did) or the edge of a notebook or the lid of a box. Sit at your table and draw a huge chessboard in perspective. You can totally do this.

Start with a horizon, having two points at infinity (orange), at left and right, and a third point midway between them (brown), which we will call the diagonal infinity. Also, mark the front corner of your chess board (blue).

Extend the front corner to the points at infinity. And then mark off (red) a point that will be a measure of the grid spacing in the chessboard. This will the be size of the front square.

You can extend that point to infinity at the right. This delimits the first rank of the chessboard.

Next, extend the front corner of the board to the diagonal infinity.

The intersection of that diagonal with the previous line determines a point, which when extended to infinity at the left, produces the first square of the chessboard.

And that line determines a new point on the leading rank edge. Extend that point up to the diagonal infinity, which determines another point on the second rank line.

Extend that line to infinity at the left, which determines another point on the leading rank edge.

Continuing in this way, one can produce as many first rank squares as desired. Go ahead and do that. At each step, you extend up to the diagonal infinity, which determines a new point, which when extended to infinity at the left determines another point, and so on.

If you should now reflect on the current diagram, you may notice that we have actually determined many further points in the grid than we have mentioned — and thanks to my daughter Hypatia for noticing this simplification — for there is a whole triangle of further intersection points between the files and the diagonals.

We can use these points (and we do not need them all) to construct the rest of the board, by drawing out the lines to infinity at the right. Thus, we construct the whole chessboard:

One can construct a perspective chessboard of any size this way, and one can simply continue with the construction and make it larger, if desired.

It will look a little better if you add a point at infinity down below (and do so directly below the diagonal point at infinity, but a good distance down below the board), and extend the board downward one level. The corresponding diagram on yesterday’s post might be helpful.

You can now color the tile pattern, and you’ll have a chessboard in perfect perspective view.

If you keep going, you can make extremely large chessboards. In time, I hope that you will come to learn how to complete an infinite chess board in finite time.

# A position in infinite chess with game value $\omega^4$

• C.~D.~A.~Evans, J. D. Hamkins, and N. L. Perlmutter, “A position in infinite chess with game value $\omega^4$,” Integers, vol. 17, p. Paper No.~G4, 22, 2017.
@ARTICLE{EvansHamkinsPerlmutter:APositionInInfiniteChessWithGameValueOmega^4,
author = {C.~D.~A.~Evans and Joel David Hamkins and Norman Lewis Perlmutter},
title = {A position in infinite chess with game value $\omega^4$},
journal = {Integers},
FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
year = {2017},
volume = {17},
number = {},
pages = {Paper No.~G4, 22},
eprint = {1510.08155},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://wp.me/p5M0LV-1c5},
month = {},
note = {},
abstract = {},
keywords = {},
source = {},
newton = {ni15065},
}

Abstract.  We present a position in infinite chess exhibiting an ordinal game value of $\omega^4$, thereby improving on the previously largest-known values of $\omega^3$ and $\omega^3\cdot 4$.

This is a joint work with Cory Evans and Norman Perlmutter, continuing the research program of my previous article with Evans, Transfinite game values in infinite chess, namely, the research program of finding positions in infinite chess with large transfinite ordinal game values. In the previous article, Cory and I presented a position with game value $\omega^3$. In the current paper, with Norman Perlmutter now having joined us accompanied by some outstanding ideas, we present a new position having game value $\omega^4$, breaking the previous record.

A position in infinite chess with value $\omega^4$

In the new position, above, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value omega^4, which exceeds the previously largest known values of omega^3.

In the throne room, if either black or white places a bishop on the corresponding diagonal entryway, then checkmate is very close. A key feature is that for white to place a white-square white bishop on the diagonal marked in red, it is immediate checkmate, whereas if black places a black-square black bishop on the blue diagonal, then checkmate comes three moves later.  The bishop cannon battery arrangement works because black threatens to release a bishop into the free region, and if white does not reply to those threats, then black will be three steps ahead, but otherwise, only two.

The throne room

The rook towers are similar to the corresponding part of the previous $\omega^3$ position, and this is where white undertakes most of his main line progress towards checkmate.  Black will move the key bishop out as far as he likes on the first move, past $n$ rook towers, and the resulting position will have value $\omega^3\cdot n$.  These towers are each activated in turn, leading to a long series of play for white, interrupted at every opportunity by black causing a dramatic spectacle of forced-reply moves down in the bishop cannon battery.

The rook towers

At every opportunity, black mounts a long distraction down in the bishop cannon battery.  Shown here is one bishop cannon. The cannonballs fire out of the cannon with force, in the sense that when each green bishop fires out, then white must reply by moving the guard pawns into place.

Bishop cannon

Upon firing, each bishop will position itself so as to attack the entrance diagonal of a long bishop gateway terminal wing.  This wing is arranged so that black can make a series of forced-reply threats successively, by moving to the attack squares (marked with the blue squares). Black is threatening to exit through the gateway doorway (in brown), but white can answer the threat by moving the white bishop guards (red) into position. Thus, each bishop coming out of a cannon (with force) can position itself at a gateway terminal of length $g$, making $g$ forced-reply moves in succession.  Since black can initiate firing with an arbitrarily large cannon, this means that at any moment, black can cause a forced-reply delay with game value $\omega^2$. Since the rook tower also has value $\omega^2$ by itself, the overall position has value $\omega^4=\omega^2\cdot\omega^2$.

Bishop gateway terminal wing

With future developments in mind, we found that one can make a more compact arrangement of the bishop cannon battery, freeing up a quarter board for perhaps another arrangement that might lead to a higher ordinal values.

Alternative compact version of bishop cannon battery

Read more about it in the article, which is available at the arxiv (pdf).

# An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014

This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, is not currently known.

# The theory of infinite games: how to play infinite chess and win, VCU Math Colloquium, November 2014

I shall speak at the Virginia Commonwealth University Math Colloquium on November 21, 2014.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite chessboard stretching without bound in every direction—as a central example. Since chess, when won, is always won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values, which provide a measure in a position of the distance remaining to victory. I shall exhibit several interesting positions in infinite chess with very high transfinite ordinal game values. Some of these positions involve large numbers of pieces, and the talk will include animations of infinite chess in play, with hundreds of pieces (or infinitely many) making coordinated attacks on the board. Meanwhile, the precise ordinal value of the omega one of chess is an open mathematical question.

# Transfinite game values in infinite chess and other infinite games, Hausdorff Center, Bonn, May 2014

I shall be very pleased to speak at the colloquium and workshop Infinity, computability, and metamathematics, celebrating the 60th birthdays of Peter Koepke and Philip Welch, held at the Hausdorff Center for Mathematics May 23-25, 2014 at the Universität Bonn.  My talk will be the Friday colloquium talk, for a general mathematical audience.

Abstract. I shall give a general introduction to the theory of infinite games, using infinite chess—chess played on an infinite edgeless chessboard—as a central example. Since chess, when won, is won at a finite stage of play, infinite chess is an example of what is known technically as an open game, and such games admit the theory of transfinite ordinal game values. I shall exhibit several interesting positions in infinite chess with very high transfinite game values. The precise value of the omega one of chess is an open mathematical question.

# Infinite chess and the theory of infinite games, Dartmouth Mathematics Colloquium, January 2014

This will be a talk for the Dartmouth Mathematics Colloquium on January 23rd, 2014.

Abstract. Using infinite chess as a central example—chess played on an infinite edgeless board—I shall give a general introduction to the theory of infinite games. Infinite chess is an example of what is called an open game, a potentially infinite game which when won is won at a finite stage of play, and every open game admits the theory of transfinite ordinal game values. These values provide a measure of the distance remaining to an actual victory, and when they are known, the game values provide a canonical winning strategy for the winning player. I shall exhibit

several interesting positions in infinite chess with high transfinite game values. The precise value of the omega one of chess, however, the supremum of all such ordinal game values, is an open mathematical question; in the case of infinite three-dimensional chess, meanwhile, Evans and I have proved that every countable ordinal arises as a game value. Infinite chess also illustrates an interesting engagement with computability issues. For example, there are computable infinite positions in infinite chess that are winning for white, provided that the players play according to a computable procedure of their own choosing, but which is no longer winning for white when non-computable play is allowed. Also, the mate-in-n problem for finite positions in infinite chess is computably decidable (joint work with Schlicht, Brumleve and myself), despite the high quantifier complexity of any straightforward representation of it. The talk will be generally accessible for mathematicians, particularly those with at least rudimentary knowledge of ordinals and of chess.

# The theory of infinite games, with examples, including infinite chess

This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the  Yeshiva University Philosophy Club.  The event will take place in 5:45 pm in Furst Hall, on the corner of Amsterdam Ave. and 185th St.

Abstract. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers.  What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game?  Is there any reason to think that every game should have a winning strategy for one player or another?  Could there be a game, such that neither player has a way to force a win?  Must every computable game have a computable winning strategy?  I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.

# Transfinite game values in infinite chess

• C.~D.~A.~Evans and J. D. Hamkins, “Transfinite game values in infinite chess,” Integers, vol. 14, p. Paper No.~G2, 36, 2014.
@ARTICLE{EvansHamkins2014:TransfiniteGameValuesInInfiniteChess,
AUTHOR = {C.~D.~A.~Evans and Joel David Hamkins},
TITLE = {Transfinite game values in infinite chess},
JOURNAL = {Integers},
FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
YEAR = {2014},
volume = {14},
number = {},
pages = {Paper No.~G2, 36},
month = {},
note = {},
eprint = {1302.4377},
archivePrefix = {arXiv},
primaryClass = {math.LO},
url = {http://jdh.hamkins.org/game-values-in-infinite-chess},
ISSN = {1553-1732},
MRCLASS = {03Exx (91A46)},
MRNUMBER = {3225916},
abstract = {},
keywords = {},
source = {},
}

In this article, C. D. A. Evans  and I investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values—the omega one of chess—denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.

The article is 38 pages, with 18 figures detailing many interesting positions of infinite chess. My co-author Cory Evans holds the chess title of U.S. National Master.

Let’s display here a few of the interesting positions.

First, a simple new position with value $\omega$.  The main line of play here calls for black to move his center rook up to arbitrary height, and then white slowly rolls the king into the rook for checkmate. For example, 1…Re10 2.Rf5+ Ke6 3.Qd5+ Ke7 4.Rf7+ Ke8 5.Qd7+ Ke9 6.Rf9#.  By playing the rook higher on the first move, black can force this main line of play have any desired finite length.  We have further variations with more black rooks and white king.

Next, consider an infinite position with value $\omega^2$. The central black rook, currently attacked by a pawn, may be moved up by black arbitrarily high, where it will be captured by a white pawn, which opens a hole in the pawn column. White may systematically advance pawns below this hole in order eventually to free up the pieces at the bottom that release the mating material. But with each white pawn advance, black embarks on an arbitrarily long round of harassing checks on the white king.

Here is a similar position with value $\omega^2$, which we call, “releasing the hordes”, since white aims ultimately to open the portcullis and release the queens into the mating chamber at right. The black rook ascends to arbitrary height, and white aims to advance pawns, but black embarks on arbitrarily long harassing check campaigns to delay each white pawn advance.

Next, by iterating this idea, we produce a position with value $\omega^2\cdot 4$.  We have in effect a series of four such rook towers, where each one must be completed before the next is activated, using the “lock and key” concept explained in the paper.

We can arrange the towers so that black may in effect choose how many rook towers come into play, and thus he can play to a position with value $\omega^2\cdot k$ for any desired $k$, making the position overall have value $\omega^3$.

Another interesting thing we noticed is that there is a computable position in infinite chess, such that in the category of computable play, it is a win for white—white has a computable strategy defeating any computable strategy of black—but in the category of arbitrary play, both players have a drawing strategy. Thus, our judgment of whether a position is a win or a draw depends on whether we insist that players play according to a deterministic computable procedure or not.

The basic idea for this is to have a computable tree with no computable infinite branch. When black plays computably, he will inevitably be trapped in a dead-end.

In the paper, we conjecture that the omega one of chess is as large as it can possibly be, namely, the Church-Kleene ordinal $\omega_1^{CK}$ in the context of finite positions, and true $\omega_1$ in the context of all positions.

Our idea for proving this conjecture, unfortunately, does not quite fit into two-dimensional chess geometry, but we were able to make the idea work in infinite **three-dimensional** chess. In the last section of the article, we prove:

Theorem. Every countable ordinal arises as the game value of an infinite position of infinite three-dimensional chess. Thus, the omega one of infinite three dimensional chess is as large as it could possibly be, true $\omega_1$.

Here is a part of the position. Imagine the layers stacked atop each other, with $\alpha$ at the bottom and further layers below and above. The black king had entered at $\alpha$e4, was checked from below and has just moved to $\beta$e5. Pushing a pawn with check, white continues with 1.$\alpha$e4+ K$\gamma$e6 2.$\beta$e5+ K$\delta$e7 3.$\gamma$e6+ K$\epsilon$e8 4.$\delta$e7+, forcing black to climb the stairs (the pawn advance 1.$\alpha$e4+ was protected by a corresponding pawn below, since black had just been checked at $\alpha$e4).

The overall argument works in higher dimensional chess, as well as three-dimensional chess that has only finite extent in the third dimension $\mathbb{Z}\times\mathbb{Z}\times k$, for $k$ above 25 or so.

# The mate-in-n problem of infinite chess is decidable, Cambridge, June 2012

This will be a contributed talk at the Turing Centenary Conference CiE 2012 held June 18-23, 2012 in Cambridge, UK.

Abstract.  The mate-in-$n$ problem of infinite chess—chess played on an infinite edgeless board—is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. Although a straightforward formulation of this problem leads to assertions of high arithmetic complexity, with $2n$ alternating quantifiers,  the main theorem of this article nevertheless confirms a conjecture of the second author and C. D. A. Evans by establishing that it is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess $\frak{Ch}$, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. The structure is also definable in Presburger arithmetic. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.

# The omega one of infinite chess, New York, 2012

This will be a talk on May 18, 2012 for the CUNY Set Theory Seminar.

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate.  The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves.  A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—there is a move for white, such that for every black reply, there is a countermove for white, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth. Nevertheless, in joint work with Dan Brumleve and Philipp Schlicht, confirming a conjecture of myself and C. D. A. Evans, we establish that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable.  An equivalent account of the result arises from the realization that the structure of chess is interpretable in the standard model of Presburger arithmetic $\langle\mathbb{N},+\rangle$.  Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known. I will also discuss recent joint work with C. D. A. Evans and W. Hugh Woodin showing that the omega one of infinite positions in three-dimensional infinite chess is true $\omega_1$: every countable ordinal is realized as the game value of such a position.

article | slides

# Infinite chess: the mate-in-n problem is decidable and the omega-one of chess, Cambridge, March 2012

I have just taken up a visiting fellow position at the Isaac Newton Institute for mathematical sciences in Cambridge, UK, where I am participating in the program Syntax and Semantics:  the legacy of Alan Turing.   I was asked to give a brief introduction to some of my current work, and I chose to speak about infinite chess.

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—there is a move for white, such that for every black reply, there is a countermove for white, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, in joint work with Dan Brumleve and Philipp Schlicht, confirming a conjecture of myself and C. D. A. Evans, we establish that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-n problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.  I will also discuss recent joint work with C. D. A. Evans and W. Hugh Woodin showing that the omega one of infinite positions in three-dimensional infinite chess is true $\omega_1$: every countable ordinal is realized as the game value of such a position.

# The mate-in-n problem of infinite chess is decidable

• D. Brumleve, J. D. Hamkins, and P. Schlicht, “The Mate-in-$n$ Problem of Infinite Chess Is Decidable,” in How the World Computes, S. Cooper, A. Dawar, and B. Löwe, Eds., Springer, 2012, vol. 7318, pp. 78-88.
@incollection{BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable,
year= {2012},
isbn= {978-3-642-30869-7},
booktitle= {{How the World Computes}},
volume= {7318},
series= {Lecture Notes in Computer Science},
editor= {Cooper, S.~Barry and Dawar, Anuj and Löwe, Benedikt},
doi= {10.1007/978-3-642-30870-3_9},
title= {The Mate-in-$n$ Problem of Infinite Chess Is Decidable},
url= {http://wp.me/p5M0LV-f8},
publisher= {Springer},
author= {Brumleve, Dan and Hamkins, Joel David and Schlicht, Philipp},
pages= {78-88},
eprint = {1201.5597},
archivePrefix = {arXiv},
primaryClass = {math.LO},
}

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\frak{Ch}}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?