Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
64

I claim that Player A has a winning strategy in your game, and furthermore, it is a winning strategy for her simply to play the smallest available number. Let me consider the game along with several natural variations. Player A wins the original arithmetic progression game. To be a little more specific about the game, let us consider what I should like ...


58

Here is my first try at a solution. Your idea was a good one, but bishops are better than rooks, I surmise. The two pictures here are placed in some distinct parts of the infinite board. The first just ensures it is White to move (in check), and that White's king will never play a role, as capturing a black unit, which are nearly stalemated as is, will ...


55

Consider the following open knight's tour on a $5\times 5$ board, starting at position $1$ and then touring the $5\times 5$ board in the indicated move order. The final position is $25$, from which the knight can exit at either $A$ or $B$. A 5 22 17 12 7 B 16 11 6 25 18 21 4 23 8 13 ...


45

Thanks to Richard Stanley and Kevin Buzzard for independently drawing my attention to this thread. Such constructions are often easier on a half- or quarter-infinite board: the board edges are useful and also let us adapt more patterns known from the orthodox $8 \times 8$ game. I'll show that a known theoretical position with only two men on each side ...


41

I computed the nimbers of a few rings, for what it's worth. I don't see any sensible pattern so perhaps the general answer is hopelessly hard. This wouldn't be surprising, because even for very simple games like sprouts starting with $n$ dots no general pattern is known for the corresponding nimbers. OK so the way it works is that the nimber of a ring $A$ ...


38

Update. (Oct 28, 2015) See below, for a position with game value $\omega^4$. This is a great question, which I have been pondering for some time. I have just completed a joint article Transfinite game values in infinite chess with C. D. A. Evans, which describes several new positions exhibiting high transfinite game values in infinite chess. (Follow the ...


38

Update. I made a blog post about Infinite Sudoku and the Sudoku game, following up on ideas in this post and the comments below. I claim that the second player wins the even-sized empty Sudoku boards and the first player wins for odd-sized empty Sudoku boards, including the main $9\times 9$ case. (The odd-case solution uses a key idea of user orlp in the ...


36

This is a really great question! Previous attempts to make sense of infinite Go have sometimes had problems because it wasn't clear how to define the winner of a game of Go after transfinite play. The problem was that perhaps a black group was surrounded by a white group, which was surrounded by a black group, and so on forever in such a way that the ...


32

There is a positive solution for the decidability of the mate-in-$n$ version of the problem. Many of us are familiar with the White to mate in 3 variety of chess problems, and we may consider the natural analogue in infinite chess. Thus, we refine the winning-position problem, which asks whether a designated player has a winning strategy from a given ...


30

Let us call a Noetherian commutative ring $R$ an $\mathcal{N}$-position if the next player has a winning strategy; otherwise the previous player has a winning strategy and we will call it a $\mathcal{P}$-position. The zero ring is allowed and hence we will choose the misère play rule, i.e. the player with the last move loses (see Tom Goodwillie's comment). ...


30

Here are two more vanishing 12-plets similar to yours: $$ \substack{ \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} \cr \displaystyle{◻◻◼◼◼◼} \cr \displaystyle{◼◼◼◼◻◻} \cr \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} } \quad \substack{ \displaystyle{◻◻◼◻◻◻} \cr \displaystyle{◻◻◻◼◻◻} \cr \displaystyle{◻◻◼◼◼◼} \cr \displaystyle{◼◼◼◼◻◻} \cr \displaystyle{◻◻...


28

Here's an example on the edgeless ${\bf Z}^2$ board that shows "mate in $3\omega$ moves" and, I think, can be extended to arbitrarily large multiples $N\omega$ by moving the outlying Knight about $N/2$ squares to the left. FEN = 14/5p4/5Pp3/4p1B1p1/N3p1Prrp/2p1p1prkp/2p1p1prpp/2PpN1B1np/3P1B3p/4P4p/9p/9p/9Pr/11K/1: (source: harvard.edu) Black to move. ...


25

Let me prove, for example, that the following 7-piece position is a draw. 7-piece positions are about the borderline of what's doable by brute force: they were tabulated around 2010. Black draws as follows: 1) if white queen captures the rook or the pawn, recapture. 2) else, in the event of check, move the king to h7, h8, or g8 (cannot all be ...


24

(Moved from a comment.) Questions 2, 3, and 4 are answered negatively by [W], which decomposes the plane into concentric annuli of width two. OP observes that this construction is still spiral (every move after the first rotates the direction vector from the origin to the knight clockwise). However, note that the move to transition from one ring to the ...


23

The existence of a "superstable configuration" is a long-standing open question in the Game of Life community. Years ago I saw Conway ask it as follows: Is there a finite $N$ and a configuration $C$ in an $N \times N$ square that contains some live cell $c$ and guarantees that $c$ will remain live for all time, regardless of what is placed outside the $N \...


21

The most rigorous analysis of this that I know of is in: N. M. Gotts. Self-organized construction in sparse random arrays of Conway's Game of Life. New Constructions in Cellular Automata, pp. 1–53. Oxford University Press, 2003. In order to be able to actually prove something about what happens (in the face of undecidability results for general Life ...


21

Yes, there are others, such as the alternative $n=9$ example $$\substack{ \displaystyle{◻◼◻◻◻} \cr \displaystyle{◻◻◼◻◼} \cr \displaystyle{◻◼◼◼◻} \cr \displaystyle{◼◻◼◻◻} \cr \displaystyle{◻◻◻◼◻} }$$ and this orthogonally connected example with $n=10$ (i.e. a dekomino (sp?)): $$\substack{ \displaystyle{◻◻◼◼◻◻} \cr \displaystyle{◼◼◼◼◼◼} \cr \displaystyle{◻◻◼...


20

The first study of the game of life with random initial conditions that I could find was this paper: F. Bagnoli, R. Rechtman and S. Ruffo, Some Facts of Life, Physica A 171, 249 (1991) doi:10.1016/0378-4371(91)90277-J. In it they attempt a kind of mean-field analysis (which I haven't digested) as well as do some numerical experiments which suggest that ...


19

Here's an "irreversible chess" construction that's fundamentally different from the ones so far based on Ed Dean's scheme. The essential pieces and pawns are in boldface: Position A: White Kh1, Ra1, Nd1, pawns b2,b3,c3,d2,e3,f2,g2,h7, Bg8; Black Kh8, Bb1, Bg1, pawns f7,g7,h2. http://www.janko.at/Retros/d.php?ff=6Bk/5ppP/8/8/8/1PP1P3/1P1P1PPp/Rb1N2bK ...


19

The consequence relation $\models$ defined in Emil Jeřábek's answer is a matroid. In fact, it is a linear matroid. Let $X=\{r_1,\ldots,r_9,c_1,\ldots,c_9,b_1,\ldots,b_9\}$ be the set of possible checks. Recall that given $S \subset X$ and $x \in X$, the notation $S \models x$ means that every Sudoku grid which is valid on $S$ is also valid on $x$. We may ...


19

$\DeclareMathOperator\span{span}$Here is an argument which works for general $n\times n$ Sudokus, $n\ge 2$, using some ideas from the other answers (namely, casting the problem in terms of linear algebra as in François Brunault’s answer, and the notion of alternating paths below is related to the even sets as in Tony Huynh’s answer, attributed to Zack Wolske)...


19

What I get from an X of size $11121\times11121$ at just around the point where information travels to the tips. Even from Xs ten times as long, there is Methuselah-like ebbing and flowing of debris near the center amid a pool of still lifes and blinkers still thousands of generations on. Just going from experience working on the Busy Beaver of 5, I would ...


19

This game can be described as an impartial edge colouring game on $K_n$ where creating a monochrome $K_k$ is not allowed, and the last player to make a move wins (normal play). Hence, it is equivalent to a nimber. I use the terms $P$-position and $N$-position sporadically to mean "a game state where the previous (resp. next) player has a winning strategy". I ...


18

I believe the game you describe is two-person single suit whist and was solved by Johan Wastlund in this paper.


18

[Edited to include some 8-unit variations and a new 7-unit setting] [...and to report on another 7-unit setting by N.Predrag, and 6-unit variations by H.Reddmann] Ed Dean already gave a good example (the White bishop can go to d7 and e8 too but it doesn't change the outcome). I follow up only to point out some variations, all with a much smaller ...


18

Here is a partial answer. I'll assume $m$ and $n$ are the number of intersections rather than the number of squares. If both values are even, then the second player can always win by rotating the first player's previous move by 180 degrees. If precisely one value is odd, then the first player can win by removing one row or column, making it even by even. ...


17

One can use information theoretic considerations to obtain lower bounds for the number of checks. I'll prove that at least 15 checks are necessary. Proof. First note that for any two rows $r_i$ and $r_j$ (contained in the same band), it is easy to construct a Sudoku which is correct everywhere except $r_i$ and $r_j$. Thus, one must check at least 2 rows ...


16

Eleven moves suffice. François Brunault commented that the maker can get two moves to start on some hexagonal lattice (a lattice generated by unit vectors with an angle of $60$ degrees). In fact, by the fourth move, the maker can get three moves to start in a hexagonal lattice, and can choose these to be the vertices of an equilateral triangle of side $1$ ...


16

For even $n$, I claim that nobody has a winning strategy, and therefore both players have drawing strategies. To see this, observe first that by the fundamental theorem of finite games, we know that either one of the players has a winning strategy, or both players have drawing strategies. Next, I claim that Bob has a drawing strategy, which is simply to ...


15

I couldn’t find all my original notes, but I have reconstructed the gist of it. First, validity of Sudoku grids is preserved by transposition, permutations of bands, permutations of rows within bands, permutations of stacks, and permutations of columns within stacks. Below I will use “Sudoku permutation” as a short-hand for permutations from the group ...


Only top voted, non community-wiki answers of a minimum length are eligible