Simultaneous Strategy 1: Cosmic Blocks

In the chess-like game Cosmic Blocks, by Narcissa Wright, and available through the Discord server at https://discordapp.com/invite/szpznUj , players each start with a 1-square base on an 11-by-21 grid. That base spreads influence, represented by coloured shading of squares, to the 3-by-3 area surrounding the base. The goal is to spread this influence into the opposing base.

AlphaZero, Stockfish, and flexibility regarding chess variants.

Recently there was a high-profile set of matches between reigning champion chess AI stockfish and a newcomer called AlphaZero. AlphaZero was created with the same deep learning System that created AlphaGo, an AI that beat the world's best at the game Go. In the 50 matches that AlphaZero played as white, it won 24 of them and drew on the other 26. In the 50 games that it played as black it won three of them and drew on the other 47.

This advantage towards the white player may seem startling, however it's not out of line with other matches between artificial intelligence programs at the world-class level, nor is it out of line between matches between world-class human players. Stockfish, which evaluates positions in a chess game in terms of pawns of advantage starts the game with an advantage towards white of 0.1 pawns. AlphaZero, on the other hand, has no idea how many pawns of advantage white has, because it looks at the game holistically which is a radically different method of analysis compared to other modern AIs.

Part of the reason I bring up issues of artificial intelligence is to look at how well the these various systems will carry over to different chess variants rather than just the orthrodox version of the game.

Let's start with Stockfish: Stockfish is a system very much like Deep Blue and many of the other ones that came between it and Stockfish. The difference being that Stockfish is open source, meaning anyone can examine the code and edit it. This and many of the artificial intelligence programs that came before it run on a minimax principle, meaning that they try to choose the move on the assumption that their opponent will choose the best counter move in response to it, thus they try to pick the move which has the worst best counter-solution. (They try to minimize their opponent's maximum move quality.

To simplify, consider this abstract game. You have two options: Option A allows your opponent to score 5 points. Option B allows your opponent to choose between a move that scores 6 points, and a move that scores 2 points. Assuming that your opponent will choose their best move, your best choice is to select Option A, because it limits their score to 5. The fact that Option B provides the possibility for your opponent to score only 2 points is irrelevant. This is the minimax principle.

Most of what a traditional chess AI does when selecting a move is to evaluate a particular position is worth in terms of some abstract score, such as 'number of pawns'. The value of pieces is straightfoward: a pawn is worth approximately 1, a bishop or knight is worth about 3, and a queen is worth roughly 9. However the position of these pieces also matters. Having a piece in the middle or able to reach the middle at any point is worth a premium. A 'passed pawn', or one which has no opposing pawn directly ahead of it, is worth more than it would otherwise be, because of its greater potential to be promoted. The alpha-beta algorithm (not related to AlphaZero) contains set of parameters which decide how much each board piece is worth on each square. Different machine learning methods such as neural networks can be used to determine what these parameters should be.

For variants of chess that are very close to the original game such as Chess 960 (a.k.a Fischer Random Chess) or Really Bad Chess, which both feature 8 by 8 grids, 16 pieces per side, and only the orthodox six pieces, an AI using the alpha-beta algorithm should be able to play such games with few if any complications.

These AIs work even after pieces have been removed from the game so variants that use fewer pieces don't produce any difficulties either. In practice, variants with different board sizes are different arrangements such as Martin Gardener's mini chess or Romanchenko Chess (shown in the figure, source: Jocly) work well too as long as the value of any squares beyond the board are hard-coded to zero. This also means in practice that an alpha-beta algorithm can produce a viable chess AI on a board that is not a perfect square or rectangle. However it can increase the computational load the non-viable squares are considered, as they are in Jocly's implementation of alpha-beta on Romanchenko Chess.

Some systems, including Deep Blue, take advantage of chess literature, specifically for the orthodox game also take advantage of openings and their reputations methods for winning particular and games such as when you have a rook and a bishop against an opponent who just has a rook. However, after the opening and before the end game it's pretty much alpha-beta all the way. [1]

Variants that included new pieces such as fairy chess, or non-linear board movement such as Smess, the Ninny's Chess, can also be supported by AI programs that uses the alpha-beta algorithm. However these programs will need additional manual training to be able to evaluate the value of different pieces and space.

AlphaZero works on an entirely different principle; it does not assume that its opponent is the best possible opponent, one which will make the best possible counter move. Instead, AlphaZero evaluates a candidate position by simulating games of weighted random moves starting from the position to be evaluated. The evaluation is simply the proportion those random-move games that win* from AlphaZero's side. It evaluates the position this way for each move that it could make, and simply chooses the move that results in the best win proportion.

In these simulation games that AlphaZero uses, the weighting of the moves is based on moves that are likely to lead to a win based on games that AlphaZero played against itself. For example, AlphaZero may assign more weight towards a move that takes a piece over one that doesn't. It may also assign greater weight towards moves that give it control of the centre of the board. But these weight assignments would not be the result of any human supervision.

Similarly, AlphaZero has no concept of chess theory such as openings or their refutations, and it doesn't have a book of endgames to rely upon. AlphaZero was trained simply by giving the system the rules of chess, and letting it play many games against different versions of itself. It's reasonable to assume from here that AlphaZero would be able to handle many chess variants without any additional modifications other than informing it of the new rules. Furthermore a very similar training system could be given to nearly any chess variant to produce an AI program that could play that particular game.

* More exactly, the evaluation is (Proportion of Wins) + 1/2*(Proportion of Ties)

[1] Beyond Deep Blue: Chess in the Stratosphere, Monty Newborn

A Long term vision for a Master's Degree in Data Science Program

I was recently asked to write a statement of vision for a potential one-year coursework master's program. A colleague was kind enough to look at it for me; he said was 'a bit too bombastic'.

This statement has already been submitted to its intended destination.





----------

Successful data scientists need to be able communicate not just verbally and in writing, but also
visually by way of graphs, dashboards, and animations. They need to have working knowledge of
modern database languages like SQL and big data architectures like Hadoop. They need to be able to
determine when to use modern statistical, machine learning, and optimization methods like the LASSO, neural networks, and random forests.

But successful students won't just have a practitioner's knowledge of these tools, because these tools
will be replaced eventually. They also need the depth in their backgrounds to evaluate and adapt to
additional systems and methods as they become available.

Therein lays the challenge: the demands upon a data scientist are broad, whereas a Master's degree is
typically a structured, focused, deep exploration of a single field. There simply isn't enough time to
cover all that's necessary to develop a prospective student starting with a bachelors degree in
Mathematics or Computer Science into a consummate data scientist in ten months. 

Some topics will need to be sacrificed for the sake of brevity, but what? Different students will bring
diverse skills and affinities into such a degree program, and they will be good judges of what they
should focus on. However, a degree is essentially a set of requirements, which is another way of saying it's a set of guarantees. The better defined those requirements are, the clearer the guarantee of skill that the bearer of such a degree brings to future employers.

In the face of program that will inevitably be stretched thin across many competencies, there are two
competing needs: the need for students to develop the subset of these competencies that maximize their personal return, and the need for standardization across the program to make its value and quality obvious to all stakeholders. To reconcile these two needs, I envision a specialization system. Graduates from the ideal Master in Data Science program will also graduate with one of four specialties: visual analytics, databases, methodology, or algorithms.

Under this specialization program, all MDS candidates will be required to take a core of data scraping, imputation, R or SAS programming with an SQL component, modern regression such as GLMs, and scientific writing. This totals 15 graduate credits. The remaining 9 credits form a specialty.

Database experts would be most akin to software engineers. The courses for this specialty would
include one focused on the extract-transform-load paradigm, one focused on handling big data tools
like Hadoop. Graduates from this specialty would be expected to be able to implement automated tasks
for gathering, cleaning, and summarizing information from the web or some other digital sensor.

Methologists would take applied statistical courses like design of experiments, sampling, dimension
reduction, time series, and spatial statistics. What separates this specialty from a Master's degree in
statistics is the lack of emphasis on proofs. Students in these courses need not understand why a
method works, only how to assess through diagnostics and checklists that it is working and when it is
appropriate.

Visual analytics specialists would take courses focused on user interfaces and communication,
including graphing and data cartography, dashboards, and additional writing work such as survey
design. Graduates from this specialty would be expected to demonstrate familiarity with popular
database interface like Jaspersoft and Tableau.

Algorithm experts would focus their additional coursework on new ways to find meaning from the
data deluge. Their corpus would include machine learning, optimization methods like quadrature and
simulated annealing, text processing concepts such as regular expressions and edit distance, image
processing, clustering, compression and information theory.

A graduate with skills in any one of these four specialties fits nicely under what we know as a data
science today.  This vision is a grand one, and far too large for a new master's program to take on, but
it's the endgame i have in mind for this program.

I read this: Chess Metaphors: Artificial Intelligence and the Human Mind

Chess Metaphors: Artificial Intelligence and the Human Mind, by Diego Rasskin-Gutman uses chess to explain concepts of intelligence both organic and artificial. The first part of the book is about the human mind, and cognitive models like schema and memory chunking, which I only skimmed. The second part discusses how an AI program can efficiently explore all the relevant consequences of any given chess move.

In the AI portion, 'Metaphors' explained how minimax algorithms worked, and discussed the Alpha-Beta algorithm, a chess playing staple, in particular. Minimax algorithms are useful for zero-sum two player games, like chess and most other head-to-head games.

Algorithms of this type work by compiling a set of possible moves, and for each move a set of possible responses by the opponent. The consequences of the response (e.g. the board state) is evaluated for each considered response. The worst (from the perspective of the AI) board state possible is assumed to be the response, and the evaluation (e.g. how 'good' that board state is) is recorded as the value of making that move. This repeats for each possible move, such that the AI has the worst case that comes from each possible move (each max). It then chooses the move that produces the best of the worst cases (the minimax). If someone playing against this AI doesn't respond with that optimal response, all the better.

The algorithm described above would only work for looking one move (one ply) ahead for each team. To consider deeper strategies, the process is repeated in an exponential explosion of possibilities. Reasonably, many of these algorithms differ in their focus on finding ways to avoid evaluating unnecessary positions, which is what Alpha-Beta does.

What really surprised me is how simple the evaluations can be. A very common evaluation method is to assign a value for each piece and a value for each square that piece can move to. This implies that such an AI would be functional, although not optimal, for a wide range of chess variants. In fact, if only the orthodox pieces are used, no additional programming would be required other than alter the possible moves to the new board. An algorithm like alpha-beta could be applied 'out of the box' to variants that don't use new pieces. This would explain why the 'chess variants' app that has the smaller boards like Garner's Minichess, and rearranged boards like Chess960 uses Alpha-Beta.

Including new pieces would involve programming in their possible moves and assigning them a material value (e.g. worth 4 pawns). Therefore, adapting existing AI to many of the variations seen in John Gollon's "Ancient, Regional, and Modern" book should be feasible. There are many ways to tune the relative value of pieces and immediate movement ability, including pitting AIs with different parameter values against each other in an evolutionary pool.


Footnote: Judging by http://www.chessvariants.com/ and the chess variants subreddit, it's much easier to make a variant than to drum up support and playerbase for it.

To consider later: Smess (also available as an app):
https://boardgamegeek.com/boardgame/1289/smess-ninnys-chess
In this game, the pieces have very simple moves and the board itself defines the difference in moves.

Why Chess? Part 1: Smaller Boards

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://www.researchgate.net/publication/252932724_Gardner's_Minichess_Variant_is_Solved

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

http://www.chessvariants.com/

The Encyclopedia of Chess Variants, by David Pritchard

The Classified Encyclopedia of Chess Variants, by John Derek Beasley

Prediction Assisted Streaming

The online game path of exile has a trick for reconciling a game that requires quick reaction times with the limitations of servers: it predicts the actions of the players. It doesn't have to predict far ahead - a couple hundred milliseconds - to keep the action running smoothly most of the time.

Prediction on this time frame isn't hard in principle; play often involves performing the same short 

action repeatedly, such as firing an arrow, so the default prediction is just more of that. When the server predicts incorrectly, it usually has enough time to 'rewind' to the present and handle things as they come. The prediction is just an extra buffering layer that's in place when there is a lot of server lag.

Does video or music streaming do this? Could it?

In a song with a repetitive baseline, could the information to the client computer include: "repeat the sound from time x with the following deviations included in the buffer", rather than "play the following sound"? The "sound at time x" in this case is a note from the baseline and the deviations being the result of a human playing an instrument and not hitting the note exactly the same every time. In a case like that, potentially less data would need to be sent to reproduce the song, allowing for longer buffers or higher sound quality.

 

Likewise for video. Consider a live video feed of a soccer match, in which a player is running across the field. Video prediction may determine there is an object moving at some speed in some direction and predict a few frames ahead where that object will be, and thus what pixels to draw in that spot. Then the streaming service, making the same prediction, could just send the video information that deviates from this prediction.

For repetitive patterns like an animation of a like a spinning wheel or sparkling logo of a sports team. If the wheel spins in a predictable fashion, internet bandwidth could be saved by describing the movement of the wheel as "spinning as expected", where matching prediction software on the server and client sides both recognize that that part of the screen is taken up by an object in 10-frame loop. 

This is different from encoding only the pixels that change from frame to frame. This prediction would incorporate likely changes in a picture based on simple movement patterns or on repetitive animations.

Consider a streaming game of hearthstone, like the last time I pretended to know about video encoding. There are certain animations that regularly impact video quality, such as sand sweeping across the entire screen, that involve a many pixels changing for a non-trivial amount of time. The video encoder does fine when the picture is mostly the same from frame to frame, but introduce one of these effects that causes a lot of pixels change at once, and the quality of the live stream. 

However, the sand effect is one of sand moving slowly across the screen, its movement is predictable in that any one pixel of the effect is likely to follow the same trajectory as it did in the last few frames. Predictive video encoding is more scalable than the application specific encoding I mentioned before, but with time it could achieve the same effect if it was able to recognize frequently used pre-rendered effects such as lightning all over the screen. A predictive video encoder could recognize the first few frames of the 'lightning storm' effect and predict the rest without having to send any information about that part of the screen.

 I'm no expert on video encoding, so this may all be jibberish.

Previous post on video encoding in Twitch, the possibility of application specific codecs.