3020: Infinite Armada Chess

|< < Prev Comic #3020 (December 4, 2024) Next > >|

Infinite Armada Chess

Title text: Stockfish 16 suggests the unconventional opening 1. RuntimeError: Out of bounds memory access

Explanation

This explanation may be incomplete or incorrect: Created by an infinite armada of Stockfish BOTS - Please change this comment when editing this page. Do NOT delete this tag too soon. If you can address this issue, please edit the page! Thanks.

Chess is a board game played between two players on an 8x8 chessboard. In standard chess, each player has 8 pawns and 8 other pieces: 2 rooks, 2 knights, 2 bishops, a queen, and a king. Chess variants are chess games in which the rules, board sizes, and/or piece behaviors are altered. In the chess game presented here, a non-standard chessboard is used, which extends vertically past the original 1st and 8th ranks off the page to infinity in both directions. Each square beyond the 8 standard ranks is filled by an additional queen. The queen is the most powerful piece on the chessboard, having the powers of a bishop and a rook combined. With an infinite armada of queens, each player will have more resources to call on. Sometimes having a bunch of queens doesn't go very well, however (here, try knight to d6).

Infinite Armada is a spaceship combat game with customizable ships in a massive map that runs on the Roblox online game platform. It's unclear whether its map and number of spaceships are actually unbounded (infinite), or merely very large.

In the title text, Stockfish is a chess engine designed to evaluate a chessboard and find the best move. However, it is designed to handle finite boards, so it's likely that some problem will occur as it runs on an infinite one. Here that problem shows up as the game's move #1, "RuntimeError: Out of bounds memory access". This error message is unique to the cross-browser WebAssembly implementations of WebGL, so there was probably not enough memory to render an infinite board in a web browser window.

All but a finite number of pieces are stuck at every step, and thus there are only a finite number of possible moves, but the game is unbounded (each capture resets the draw clock) and each capture also increases the number of possible pieces which can move by opening up more space on the board. No finite amount of space is guaranteed to suffice to analyze the game — contrast with standard chess in which surprisingly little memory (given impossibly vast, but finite, amounts of time) is needed to play perfectly. Still, as in regular chess, a program which understood that only a finite number of pieces are accessible could play the same way programs play conventional chess.

However, without specifically coding Stockfish to be aware of the logical certainty of the infinite number of queens being blocked, it is likely to still be checking every piece in turn, long after it has successfully prepared to establish (or perhaps actually explored) the relative strategical advantages of undertaking the twenty initial moves that White could make. Or, in the algorithm's worst case scenario, it has tried to start its movement-checking process at the 'rearmost rank', and has encountered the error before managing to establish (let alone assess) any valid opening moves. By easy induction, the human player should be able to establish an intrinsic understanding that everything behind two full ranks of undisturbed pieces (or beyond them, when applied to the opponent's position on the other side of the board) is unable to move, where no gaps exist to shuffle around in, but the code (if designed for finite, though perhaps arbitrary, boards) is unlikely to natively have the complexity to derive this computational detail from first principles, or even establish that it might hit a halting problem failure should it somehow avoid the issue of resources.

This comic was published in the middle of the 2024 World Chess Championship, between the World Champion Ding Liren and the Challenger Gukesh Dommaraju.

Transcript

[A chess board in the starting position, except it extends further at the top and bottom, going beyond the panel. The extra squares are filled with queens of the sides' respective colors.]

[Caption below the panel:]

Infinite armada chess

 add a comment! ⋅  add a topic (use sparingly)! ⋅  refresh comments!

Discussion

Did I do well? Added a very very basic explanation. 172.68.147.132 04:25, 5 December 2024 (UTC)

Well, yes but I wonder if just one tiny fix is needed. If you replace the white side with a simplyfied artillery tower, you reinvented space invaders. 172.71.160.70 (talk) 04:57, 5 December 2024 (UTC) (please sign your comments with ~~~~)

I was personally hoping for an explanation of the Infinite Armada thing, and I feel like a link to the TV Tropes page doesn't really. Explain that at all. So I would love a bit of an expansion on that part! Just want to be sure I didn't miss some reference or something. 172.68.23.91 05:48, 5 December 2024 (UTC)

Likewise. I get the comic, but I assumed the 'armada' part was a reference that I just did not get. But it seems it is just a word choice. 172.71.102.105 09:39, 5 December 2024 (UTC)

The only "Infinite Armada" reference I can think of is Star Wars: Knights of the Old Republic, which kind of makes sense because if you have a Star Forge to make chess pieces with, why wouldn't you make them all queens? 162.158.167.159 18:47, 5 December 2024 (UTC)

I think that since the error was "out of bounds", not "out of memory", it's referring to indexing outside of the region of memory that the program allocated to deal with the board. This would happen since instead of addressing rank 1..8, you could address rank 9, 10, 0, or -1. Unless bounds checking is performed when converting the board coordinates into linear array indices, you'd get an out-of-bounds error (or worse, succeed in reading or modifying memory that you weren't intending to). --172.71.30.253 05:45, 5 December 2024 (UTC)

It was "Out of Bounds memory access". That means it was trying to access a memory address that was out of the bounds of the computer, as if it were trying to access the ω-th index of the board array, which would put it out of the memory range of any computer guess who (if you want to | what i have done) 06:15, 5 December 2024 (UTC)

There is no hint that the bounds are those of the computer, the simplest explanation really is that the bounds are those of an array. The error message does come up. In addition, to try to access the memory at the ω-th index, you would need to construct the ω-th index itself first (which would fail or not terminate) Jmm (talk) 07:01, 5 December 2024 (UTC)

The specific message, "RuntimeError: Out of bounds memory access", is a WebGL error issuing from its WASM cross-platform browser implementation. This implies to me that an attempt to render an infinite chessboard failed in a fairly trivial way, because of a poor implementation. It's very unlikely that there had been a problem with the Stockfish playing algorithm yet, which would have failed with a different message if it ran out of memory, such as "Killed", which is all that shells like Bash print when one of their job processes is killed by the kernel's OOM killer, or by anything else for that matter. 172.70.215.21 12:58, 5 December 2024 (UTC)

If it were trying to access an index that was out of the range of the array, then it would probably have mentioned an index somewhere in the message, like "Out of Bounds index". However, it says that the "memory address" was "Out of Bounds," implying that it tried to access a physical memory address that was out of bounds. Anyways, it wouldn't make sense to use an unmodified version of Stockfish that would still expect on 8 rows for a larger chess board, as it's not a close approximation to having an infinite number of queens. guess who (if you want to | what i have done) 20:30, 8 December 2024 (UTC)

The 8x8 board geometry is hardcoded entirely throughout Stockfish and its data structures. It would be easier to introduce new kinds of pieces with different kinds of moves than change the board size. 162.158.186.10 01:11, 10 December 2024 (UTC)

I have no insights into Stockfish (had I programmed it, I'm sure I'd also use its handy 8x8ness to highly optimise the way data was stored, i.e. hardcode 1 byte for any 'free' location and probably pack tight the "possible moves from this spot by this piece" bit of the record, where possibly... eight possibilities for a King, etc). I interpret the comic as being of a heavily modified version, though, effectively rewritten to allow arbitrary (if not truly boundless) fairy-boards that aren't square.

Tying the error down is tricky. It'll be a compiler-added failover, either of the custom Stockfish or even of the OS's virtual memory subsystem, to deal with one or more problems that is probably more than exceeding the index bounds of any malloced array structure. It could even be some issue (getting past various initial handling layers, betwixt application and hardware) that tries to access a physical RAM address that doesn't exist, which finally gets caught and 'explained' back down the line by an error-code response that gets translated into the text we see by a less hardware-aware level of application code that just knows that it's an out-of-rangeish exception that's raised.

Back when I regularly did assembler programming, you'd get very good ideas of what you were doing, what you could do and what would happen if you did slightly odd things. Sometimes to your advantage (i.e. directly peeking/poking memory locations beyond the overflow limit could 'wrap around', which was an interesting shortcut to save the need to detect when you'd go out of bounds and then loop back to the start yourself), if you were careful enough about it. These days, all programming I do is softened and "cotton wool"ed by several Hardware Abstraction Layers (and obscure compiler settings, where it's too much trouble to get to know every individual handling option quite so intimately).

It'd be interesting to find the actual word-for-word inspiration, but I suspect that it's just a conceptual paraphrasing of the kind of thing that only exists (as needed) in Randall's imagination, so has a fictionality and/or composite source model to it. 172.70.90.5 05:28, 10 December 2024 (UTC)

Is this a reference to infinite chess by Naviary? HaruruChanDesu (talk) 11:21, 5 December 2024 (UTC)

"it does not really need to consider the infinitely many pieces" => a chess Engine would need to consider the infinitely many pieces (or have a way to abstract them), even if some pieces are currently stuck because the engine recursively evaluates moves and counter-moves (i.e. evaluates the game up to some depth). 162.158.95.184 (talk) 13:44, 5 December (UTC) (please sign your comments with ~~~~)

Is the cardinality of the set of all the pieces smaller than the cardinality of the set of all possible moves? My gut instinct says yes but I don't have the energy to muck around and see if I can prove it. If I did try I think that matrix diagonalization would be the first thing I'd try. Anybody less lazy than me on this? --Tomb (talk) 21:30, 5 December 2024 (UTC)

The number of games is at least Beth one (cardinality of the continuum so uncountable). After some preliminary moves you can have a black queen on an otherwise empty row and a white queen in the black pawn row. Now on pairs of moves the black queen moves in its row so its column mode four is a base four digit while the white queen moves up one row to give the digits position. So we can map real numbers uniquely into games.

The number of pieces is obviously countable.172.70.230.60 18:59, 6 December 2024 (UTC)

Thanks! --Tomb (talk) 19:12, 8 December 2024 (UTC)

Can someone explain the linked joke with all the extra queens? I don't understand why it's a bad position. 172.69.59.126 16:49, 5 December 2024 (UTC)

Knight to d6. 162.158.167.175 17:09, 5 December 2024 (UTC)

...is checkmate by black. White can't capture the knight with either of the two queens that attack it because they're both pinned, by black's bishop and rook. (And we know it's black's turn to move because the colored squares indicate white just moved.) DKMell (talk) 17:54, 5 December 2024 (UTC)

Expected some discussion here already on the best opening moves given a infinite board or at least the board depicted. 1. e3 e6 2. Qh5 seems a logical start, but not entirely sure what would happen after that? Any ideas? Flekkie (talk) 22:56, 5 December 2024 (UTC)

I think games will generally end in a draw by perpetual check that's something like:

1. Qxd7+ Qxd7

2. Qxd7+ (etc)

It's tricky to prevent a player at a disadvantage from repeatedly sacrificing queens from further and further away down some file. 172.68.54.138 02:43, 6 December 2024 (UTC)

However, the rules of chess wouldn't cause this game to end in a draw since there are captures every turn, and captures reset the 50-move counter that triggers a draw. The players could agree to a draw - or perhaps the player at a disadvantage could hope to win by exhaustion, that is, by following this strategy indefinitely and hoping the other player collapses from weariness first. DKMell (talk) 03:27, 6 December 2024 (UTC)

This assumes no chess clock. Alas, what I just wrote assumes a classic chess clock. Some games use time rules that require a modern electronic clock and add time every move, which in this case brings back the "recaptures go on forever" problem. 172.70.207.149 11:49, 7 December 2024 (UTC)

Hit me up when this becomes real. I would like to try this out. Caliban (talk) 12:29, 5 December 2024 (UTC)

It should be easy enough. You will rarely get the queens out in play from deep in the array. So maybe just put two chess boars together and put some placeholder in for queens in the extra fields. If ever a queen in the bottom row is moved, place extra queens that can now be moved into the 2-3 squares that would be outside the board...--Kynde (talk) 12:39, 5 December 2024 (UTC)

It might be something one could set up in Infinite Chess, although having limits on the chessboard may be difficult. 172.68.150.67 14:01, 5 December 2024 (UTC)

Here's a finite approximation in ChessCraft: https://www.chesscraft.ca/design?id=5KM4 Promethean (talk) 15:37, 5 December 2024 (UTC)

While I understand how to play chess, I don't get the bit about "having a bunch of queens doesn't go very well". At first glance, the linked chess layout looks pretty solid. Can someone please enlighten me? Also, what does the TV Tropes link about Title Drop have to do with Infinite Armada, aside from that being the title of the comic? 172.70.230.77 13:10, 5 December 2024 (UTC)

... Nd6. 172.70.91.246 13:31, 5 December 2024 (UTC)

Ah, thanks. Moving the knight there puts the king in check, and moving either queen to take it exposes the king to the bishop or rook, so checkmate. 162.158.63.38 15:05, 5 December 2024 (UTC)

You are assuming that the opponent makes no moves while you spend at least three moves advancing your knight. Looks like either side can draw by always moving the king backwards whenever a queen has moved and made a hole he can move to and otherwise trying to make a new, deeper hole. Eventually he gets so far back that any attack turns into an infinite sequence of queens taking each other, with the attacker only having file attacks while the defender can retake from a rank, file, or diagonal. Any time the attacker breaks off the infinite sequence of queens taking each other to set up something else, the defender takes advantage of the break to move the king deeper and put more queens in front of him or to create more empty spaces to sidestep into when attacked. To me, this looks like a certain draw. 172.69.33.252 16:21, 5 December 2024 (UTC)

They're talking about the linked layout at https://x.com/chesscom/status/1841540380363211164, not the layout in the comic. It only takes one move for the black knight to move to Nd6 and put the white king in checkmate. 141.101.109.167 20:59, 5 December 2024 (UTC)

You might be able to get the developer of fairy stockfish ( https://fairy-stockfish.github.io/ ) to add this if you ask nicely. I have seen them add several reader requests. 172.70.211.143 15:46, 5 December 2024 (UTC)

Could this be a reference to the meme about "eating an infinite armada of pizza"? The wording seems too similar to be a coincidence. 172.70.114.46 14:46, 5 December 2024 (UTC)

Would this guarantee a draw between two competent players who'd played the variant before, or would there be more nuance to it than there appears to be?

Can someone explain the linked joke with all the extra queens? I don't understand why it's a bad position. 172.69.59.125 16:48, 5 December 2024 (UTC)

The explanation of the linked joke is that the king appears safe at first glance, but in reality there is a simple move that wins the game for black. Moving the black knight to the top left corner of the queen square checks the king. The king cannot move to escape. Two queens are in position to take the knight and save the white king, but both of those moves expose the king to attack from other black pieces (the rook or the bishop).

Wow. Not only did White give Black a mate in one, they also blundered a mate in one. 162.158.167.176 20:21, 5 December 2024 (UTC)

Really? This comic specifically references some obscure roblox game with like 350k visits? That can't be right. 172.71.154.247 02:31, 6 December 2024 (UTC)

I agree, it seems out of character for Randall to use something like that as a punchline. 172.71.166.18 14:01, 9 December 2024 (UTC)

Referencing a geeky, obscure subculture computer game that isn't (yet!) particularly well known..? Nope. Can't at all think why he'd suddenly do that out of the blue, just as a Genius Bonus... /s 172.71.26.100 15:30, 9 December 2024 (UTC)

This was the variant played at the chess tournament held at David Hilbert's Grand Hotel. You'd think they would have struggled to fit infinitely large boards in the conference room, but they just kept moving the tables until they had enough space. RegularSizedGuy (talk) 08:01, 6 December 2024 (UTC)

Clarifying "Surprisingly little memory to analyze conventional Chess": Without trying to "golf" the memory requirements, a board can be represented in 64 bytes, a reversible move in three bytes (start square, end square, piece captured). 40 moves without a pawn move or a capture is a draw, so the search stack is less than 5,680 moves. Two copies of the board (current search position, a board for looking back for detecting repeated positions), a few pointers for searching for moves to try: 20K of memory is plenty to search the entire Chess tree. And a truly unimaginably huge finite amount of time. (Golfers, start your carts!) 172.68.55.12 12:08, 6 December 2024 (UTC)

Queen to A9.56x10^14 -P?sych??otic?pot??at???o (talk) 13:47, 6 December 2024 (UTC)

Seems like a trivial win for white? Start w/ scholar's mate 1. e5 ... 2. Qh6, and just keep throwing queens at the king. It's much easier for the infinite queens to attack than to block and defend. 172.71.154.76 18:21, 6 December 2024 (UTC)

The problem is 1. e5 h6 2. Qxh6 Rxh6, if you keep trying to win h6 you’ll run out of queens that can move diagonally and black has an infinite supply moving vertically. 2. Qg4 Ng6 3. Qce2 seem like the logical next three moves? Except now black has a free move and a knight out. So at least it doesn’t seem trivial. I do think these games will be shorter than regular chess if they lead to a result, because long series of moves will tend to release the infinite queens. -- Geoffk01 (talk) (please sign your comments with ~~~~) 23:13, 6 December 2024 (UTC)

I cannot image this is not trying to reference https://www.youtube.com/watch?v=rSCNW1OCk_M , which recently resurfaced again. 172.70.114.35 (talk) 18:57, 6 December 2024 (UTC) (please sign your comments with ~~~~)

I can't help but wonder if this might be in some way related to a known issue with stockfish, where if there are too many available moves in a given position, it causes a buffer overflow (see https://github.com/official-stockfish/Stockfish/pull/4558). This doesn't actually apply here, but it feels like there could be a relation 172.69.79.191 (talk) 09:50, 11 December 2024 (please sign your comments with ~~~~)