Thursday, 16 February 2017

I read this: Chess Variants - Ancient, Regional and Modern

Chess Variants - Ancient, Regional, and Modern by John Gollon is a book published in 1968 that describes 33 different versions of chess, and includes sample games for most of them. It is the closest source I have yet encountered to answering the 'why chess' questions.

In the author's words, it is intended to be a Hoyle's Book of Games, but for chess. It also asrved as a humbling reminder to look outside university resources sometimes. The Bennett library may have nearly every book one could want on statistics, but it has perhaps 10 on chess, and those are mostly about artificial intelligence.

There's a lot of useful information from this book, much of the subtler implications are beyond me. Here's the gist of what I learned:

The earlier known chess comes from India and was called Chaturanga. It came in 2-handed and 4-handed (i.e 2-player and 4-player) formats, both played on an 8x8 grid. In the 4-player version, each player had 8 total pieces and starts in a 2x4 square in the corner. The 2-player version looks, on the surface, surprisingly close to modern chess. However, some pieces are much weaker than they are now. The equivalent of the bishop moves exactly 2 spaces diagonally. The equivalent of the queen moves only 1 space diagonally. The pawn is the same, except it can't move 2 spaces in its first move. The knight, and even the rook are the same as they are in the modern game.

Throughout all the versions shown in this book, the knight changes little, occasionally getting 'stretched' into a 3-and-1 move, or even an unlimited-and-1 move. The rook, however, is extremely stable and unchanging, like some sort of castle.

The next set of versions covered are the Arabic adaptations of Chaturanga, called Shatranj. In several of these versions, an oblong four-sided die is used to determine which type of piece a player may move on that turn. For example, a player may only move their rook whenever a '3' is rolled. In these dice-based versions, a player has the option of making no move at all, as they would otherwise be often forced to move into a worse position, or to move a piece they don't have. Amongst the Shatranj variations, other board sizes are considered, including a 4x16 board where each player starts with two rows of pawns in the from.

In Timur's chess and a couple other versions like citadel chess, the board has two single-square offshoot spaces in opposing corners. These spaces are called 'bastions' or 'citadels', and the restrictions around them or the rewards for reaching them changes from game to game. Typically they offer defensive advantages and/or promotions for secondary king-like pieces called princes. In citadel chess, if the king reaches an opposing citadel, a draw is forced.

In 'Hsang Chi', or Chinese Chess, there are the same staple of weaker versions of bishops and pawns, pieces similar to knights and modern rooks, However, the board is 9x9 and the 5th rank is entirely occupied by a central river. On each side of the river is a 3x3 fortress. The king piece cannot leave the fortress, and certain pieces cannot cross the river. There is a 3-player version of this played on a hexagon in which the river forks in the centre of the board and each player has a fortress. In both the two- and three-player versions, pieces are placed on the intersections of the lines, rather than in the middle of the squares. Playing on the lines rather than the spaces is especially useful in the 3-player version because, by necessity, the spaces are not squares of equal size. Korean chess is similar to 'Hsang Chi', except there is no central river.

Burmese chess has a 'draft phase' of sorts, which precedes the part of the game where pieces are moved.

The draft phase starts with both players having a row of pawns in the front of their territory (the two ranks nearest them). Then players alternate placing their other pieces - either by putting them in the back rank or replacing a pawn in the front rank. The removed pawn goes into reserve to be placed later in the draft. Even after all pieces have been placed, a player can continue the draft phase by removing a piece to place it elsewhere. The draft continues until one player makes a move, after which play proceeds only with moving.

This 'draft phase' seems unique, and I'm surprised to not see it elsewhere. However, there's variant currently being sold called 'Shuuro' that advertises a similar mechanic.

Apparently there are more variants buried in fiction. Edgar Rice Burroughs, author of Tarzan, also described a game of Martian Chess in one of his other books. A skim of the Wikipedia article on this game, also called 'Jetan', reveals four other variants in fiction books.

Finally, in the 'modern' section of the book, the author describes two versions of chess with the modern orthodox pieces and two additional pieces: the chancellor who has the move the of the rook and the knight, and the cardinal who has the moves of the bishop and the knight. The author predicts that if the predominant version of chess ever changes, it would be to one of these other versions. He considers a natural progress to the modern version, also called 'queen's chess' because it was marked by the creation of the modern queen - a combination of the rook and bishop.

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.


Saturday, 11 February 2017

Creating Homework Material for Statistical Writing Classes and Workshops.

This summer, I'll be offering a workshop on statistical writing to the graduate students in the SFU Stats department. In the year that follows, I hope to teach SFU's Stat 300 course, an undergraduate writing course that is mandatory for all statistics majors. I want this course to be offered at more universities, but since the typical undergrad degree in stats is already overloaded, this would need some additional motivation, so here's my anecdotal hook:

When graduate schools ask for a letter about your motivations for applying, or about your general background, there's a few things that are being examined. First, different graduate supervisors have different specialties, and they may be looking at your letter for signs of a good match. Second, the letter is a means of seeing firsthand your personal ability to communicate in English. They ask for something personal rather than a set topic to discourage plagiarism. They are not interested in your level of motivation; everyone says they are highly motivated.

I've recently been writing reference letters and filling out graduate school reference forms for students that have been in my previous 300-level classes. All of these schools are asking about the ability to write. Many statistics undergrads are applying to fields outside of pure statistics, for example economics, medical science, and business. All of them are asking their references about skills in English, often spoken English and always written. Likewise, the Statistical Society of Canada asks referees about spoken English as a part of their A.Stat accreditation.

In order to develop these skills in a program that usually focuses on mathematical theory and programming ability, I've sketched out some projects and exercises that could fit into a workshop or course.

The instructor (me) would ask colleagues from other fields that use quantitative data, such as sociology, anthropology, biology, business, ecological restoration, and history for reports from previous or current projects.

The students would read the reports and identify what the sampling method was, what analysis was done, and to check the assumptions on those methods to the data. They would interpret the results in their own words (not in the words of the discussion or conclusion section), and compose a couple of questions about the research that weren't answered. These questions don't have to pertain to the domain; they should pertain to the methodology. These would be questions like: were there any outliers that affected your results? Did you consider multiple testing? Did you consider regression/anova?

For example, for this research report, Water Quality of Stoney Creek and its Effects on Salmon Spawning, by SFU undergrads by Oak, Tony; Thai, Michelle; Orgil, Indra; Ngo, Kevin; Lu, Jerry , available at http://summit.sfu.ca/item/12770

A writing assignment could be:

  • What were the parameters to be estimated?
  • What biologically important thresholds or critical values are mentioned for the parameters being estimated?
  • What sampling method was used? How many sampling units are there?
  • Were there any null hypotheses being tested? If so, were they rejected? Should they have been?
  • Describe the qualitative differences between the four sites. Use the map and Figs 4,5,6, and 7.
  • In your own words, summarize the quantitative data described in Figures 2 and 3.
  • Compose two suggestions or questions about the analysis that may not have been considered.
  • Describe one way you could build upon (e.g. expand, follow up) this study, the type of information you would collect from this new work, and what additional conclusions you could make if the data matched your expectations.

(Note: Please don't take these questions as a criticism of this research report. It was selected to show how material is available within one's on campus. Even a quick skim of the report will show it's truly excellent work for undergrads.)


Another exercise I'm thinking of doing is to have students copy edit some scientific writing. This could be a publication or a blog post. I would do this twice; once with a well written work, and once in something of questionable quality like the unedited papers that come out of discount publishers. If I used something from ArXiv, with the authors' permission, I could use later, more complete versions of the same work as a 'key'. However using ArXiv is untenable for graded work because the 'key' is publicly available.


Also, there are the reading comprehension exercises.The ones I had posted earlier (here and here) were meant to be done in less than 2 hours, and had questions focused on specific statistical topics. Another possibility is to write more such assignments that require less statistical expertise, but more in-depth composition.