Chess fascinates me; it's a
very pure board game, and it has existed in some recognizable form
for centuries. There's a couple of general questions I have about
chess that I return to occasionally, but haven't formally approached
until now.
1) Why is the game that
we consider chess the orthodox game and not some variant or
alternative?
2) How robust is existing
artificial intelligence to changes in chess?
Chess, at least in the
western world, fills a niche in the game market. It's a competitive
game between two players with no random chance and no physical
requirement. The rules of the game take an hour to learn, a day to
understand, a lifetime to master. In game design terms, chess has a
great deal of depth, but limited complexity.
It's not the only such game.
The game of Go, for example, has fewer rules, comparable depth, and
an effective and convenient method to handicap.
Also, what about variants of
chess? Would the game be less interesting or deep if the knight moved
in a 3-and-1 jump instead of a 2-and-1 jump? What if the board
dimensions were different? Chess has changed before, however slowly.
Is it just an accident of history that this is the particular game we
got, or is there something optimal about it?
I've been playing games of
different variations of chess starting with those available on the
Android app Chess Variants. Several of the variants avialable in this
app are games that use the same kinds of pieces as orthodox chess but
fewer of them, and on a smaller, simpler board. One clear pattern has
emerged after 50 plays across 3 variants: I'm horrible. I am
embarrassingly bad at chess compared to a computer opponent.
Mini chess (original).
The first variant I tried
was Martin Gardner's 5x5 variant, made in 1969. I played as white
(first) against an AI opponent (to be discussed in part 2) about 20
times. The result was 0 wins, 2 draws, and a heap of losses. The app
allows you to play as black, or even as both for local play, but I'm
stubborn.
The layout, shown in Figure
1, suggests a major advantage to black to a naive player like myself.
There are 7 possible moves white can make at the beginning of the
game. All of these moves let a piece be captured right away. What
else could explain my tremendous defeat?
Figure 1 – Martin Garner's
original Minichess
I looked up the game to see
if my suspicions on white's disadvantage were correct. They were not.
It turns out the Gardner's 1969 version of 5x5 chess is a weakly
solved problem. Each player can play perfectly and always draw or
win. If both are playing perfectly, the game ends in a draw.
Furthermore, the perfect play algorithm (also called the 'oracle'),
is a mere ~10 pages of if-then instructions.
The "weakly" in
weakly solved refers to the fast that a perfect strategy exists and
is known from the starting position of the game, but not necessarily
every position. So if you play sub-optimally to start a game, the
'oracle' doesn't necessarily cover your situation.
A paper by Mhalla, M., &
Prost, F. (2013) outlines this perfect strategy and talks about the
winning rates of each side in a sample of historical correspondence
games. The white player won slightly more of these games than black
did.
Mini chess (updated).
This is a 1989 update to
Gardner's 5x5 chess. It is identical except that the knight and
bishop have been swapped on the black side.
I played 5 games on this
version after playing the 1969 version. Games lasted longer and were
closer, but with a small sample and an experience confound, I'm not
confident in explaining why.
Micro Chess
This seems to be as minimal
as chess gets without being a chess puzzle instead of a game. The
layout, shown in Figure 2, only has one pawn per side. The pawn can
be moved two squares in its first move. However, the pawn cannot be
promoted to a queen. This seems reasonable as no player starts with a
queen.
Figure 2 – Micro Chess
There is a one move
checkmate for black:
White bishop to C2
Black knight to C3
White is in checkmate.
I was unable to win any
match at this (again as white) either, but I did reach a draw quite
often. My suspicion is that the knight is the most powerful piece,
and that this change in the relative strength of pieces could cause
an AI opponent to make poor trades if it was using piece valuations
from classic chess. No such luck.
The Alpha-Beta Algorithm
The AI used in this app
employs the alpha-beta tree algorithm, which is good for quick
computation, like on a phone, because it eliminates large sets of
possible actions quickly. It's also non-deterministic; it will choose
different actions in identical situations if there is no single
obviously best solution.
The alpha-beta algorithm is
not specific to chess. It could be used for any discrete choice
system, like Shogi or Go. However, it relies on a heuristic scoring
system. To use the algorithm, an AI needs a way to evaluate how good
or bad a consequence of that action is. Last time, I talked about
throwing off the AI by assuming it would under-value a knight. That
is, I was assuming that the value assigned to the consequence "lose
your knight" would be copied over from classic chess to micro
chess, and that this value could be exploited.
The Alpha-Beta algorithm
also has some tuning parameters that determine the quality of the
decisions made by it. By changing the number or depth (turns removed
from the current situation) of the possibilities that the algorithm
will evaluate. These parameters can be manipulated indirectly in the
Chess Variants app by a difficulty setting with four options: easy,
medium, hard, and fast.
The last setting, fast, was
the one I was using. In this case, the algorithm will evaluate
solutions until 1 second of processor time has been used. This means
the algorithm becomes harder to beat when it is provided more
processing power, so I can blame my equipment for my losses. The AI
may have been playing a close-to-perfect game on the simplified
boards, because the space of possible states was much smaller. I also
noticed that in orthodox chess matches, the AI got better as the game
progressed and pieces were removed from the board. I could frequently
take the opponent's queen without a sacrifice only to be crushed in
the end-game.
For existing pieces, the
value of retaining each piece, and having them in various positions
relative to an opposing king is well established by humans. That, I
suspect, is why Jocli, the platform used to make all these chess
variants online, only has variants that use pieces that exist in
orthodox chess and which alter the board - because the heuristics for
these (combinations of) pieces are well-established.
Next, I intend to look into
Chess 960, which is a variant played on an 8x8 board in which the
starting positions of non-pawn pieces are randomized. There are 960
possible starting arrangements that fit the restrictions (King is
between rooks, bishops are on opposite colours, black mirrors white,
etc. ), hence the name.
An AI may not be able to
adapt a few opening strategies from orthodox chess to chess 960, but
it fares well by treating any starting as a game already in progress
(even if that progress was impossible). If you introduced a common
chess puzzle piece, such as the grasshopper or princess, would an
entirely new set of heuristics be needed?
Relevant links:
Mhalla, M., & Prost, F.
(2013). Gardner’s minichess variant is solved. ICGA Journal,
36(4), 215-221.
https://jocly.com
The platform used for the Chess Variants app. Also playable in a web
browser.
https://en.wikipedia.org/wiki/Minichess
including Gardner's Minichess, and Microchess.
https://en.wikipedia.org/wiki/Fairy_chess_piece
list of unorthodox chess pieces used in puzzles and variants.
Still to explore:
Onitama
The Duke
Nightmare Chess
Alice Chess
The Encyclopedia of Chess
Variants, by David Pritchard
The Classified
Encyclopedia of Chess Variants, by
John Derek Beasley
No comments:
Post a Comment