Monday, November 30, 2015

Tic-Tac-Toe (with Xs only)



I'll need to dig into this series a bit further when I get a chance.



Wednesday, November 18, 2015

Perfecting the imperfect [repost]


[disclaimer -- I've only field tested the first of these, so I can't guarantee that all of the variations will play smoothly. On the bright side, there ought to be plenty of room for improvement. As with all discussions of game variants, you should probably assume that countless people have already come up with any idea presented here.]

When the subject of perfect information games comes up, you probably think of chess, checkers, go, possibly Othello/Reversi and, if you're really into board games, something obscure like Agon. When you think of games of imperfect information, the first things that come to mind are probably probably card games like poker or a board game with dice-determined moves like backgammon and, if you're of a nostalgic bent, dominoes.

We can always make a perfect game imperfect by adding a random element or some other form of hidden information. In the chess variant Kriegspiel, you don't know where your opponent's pieces are until you bump into them. The game was originally played with three boards and a referee but the advent of personal computing has greatly simplified the process.

For a less elaborate version of imperfect chess, try adding a die-roll condition to certain moves. For example, if you attempt to capture and roll a four or better, the capture is allowed, if you roll a two or a three, you return the pieces to were they were before the capture (in essence losing a turn) and if you roll a one, you lose the attacking piece. Even a fairly simple variant such as this can raise interesting strategic questions.

But what about going the other way? Can we modify the rules of familiar games of chance so that they become games of perfect information? As far as I can tell the answer is yes, usually by making them games of resource allocation.

I first tried playing around with perfecting games because I'd started playing dominoes with a bluesman friend of mine (which is a bit like playing cards with a man named Doc). In an attempt to level the odds, I suggested playing the game with all the dominoes face up. We would take turns picking the dominoes we wanted until all were selected then would play the game using the regular rules. (We didn't bother with scoring -- whoever went out first won -- but if you want a more traditional system of scoring, you'd probably want to base it on the number of dominoes left in the loser's hand)

I learned two things from this experiment: first, a bluesman can beat you at dominoes no matter how you jigger the rules; and second, dominoes with perfect information plays a great deal like the standard version.

Sadly dominoes is not played as widely as it once was but you can try something similar with dice games like backgammon. Here's one version.

Print the following repeatedly on a sheet of paper:

Each player gets as many sheets as needed. When it's your turn you choose a number, cross it out of the inverted pyramid then move your piece that many spaces. Once you've crossed out a number you can't use it again until you've crossed out all of the other numbers in the pyramid. Obviously this means you'll want to avoid situations like having a large number of pieces two or three spaces from home.

If and when you cross off all of the numbers in one pyramid you start on the next. There's no limit to the number of pyramids you can go through. Other than that the rules are basically the same as those of regular backgammon except for a couple of modifications:

You can't land on the penultimate triangle (you'd need a one to get home and there are no ones in this variant);

If all your possible moves are blocked, you get to cross off two numbers instead of one (this discourages overly defensive play).

I haven't had a chance to field test this one, but it should be playable and serve as at least a starting point (let me know if you come up with something better). The same inverted pyramid sheet should be suitable for other dice based board games like parcheesi and maybe even Monopoly (though I'd have to give that one some thought).

I had meant to close with a perfected variant of poker but working out the rules is taking a bit longer than I expected. Maybe next week.

In the meantime, any ideas, improvement, additions?

Originally posted in West Coast Stat Views

Monday, November 16, 2015

Hexagonal Reversi

[If you don't have a hexboard lying around the house, you might consider going by the Amazon store for the board game Kruzno.]

Hexagonal Reversi is very similar to regular Reversi (which is suspiciously similar to Othello, but that's a subject for another post).

Here are the starting positions:


Each player takes turns placing one of his or her pieces on the board so that at least one row of the opponent's pieces lie between the newly placed piece and another piece already on the board at which point the row of opponent's pieces are replaced with the player's pieces.



This figure above shows the possible initial moves if black goes first (B) or if white goes first (W).


[repostedd from 2014]

Thursday, November 12, 2015

MOOCs -- this time it's different

Timothy Taylor highlights an interesting passage from this paper by Michael S. McPherson and Lawrence S. Bacow.
     "Berland (1992), citing a popular commentator named Waldeman Kaempffert writing in 1924, reported that “there were visions of radio producing ‘a super radio orchestra’ and ‘a super radio university’ wherein ‘every home has the potentiality of becoming an extension of Carnegie Hall or Harvard University.’” Craig (2000) reports that “the enthusiasm for radio education during the early days of broadcasting was palpable. Many universities set up broadcast stations as part of their extension programs and in order to provide their engineering and journalism students with experience in radio. By 1925 there were 128 educational stations across the country, mostly run by tertiary institutions” (p. 2831). The enthusiasm didn’t last—by 1931 the number of educational stations was down to 49, most low-powered (p. 2839). This was in part the result of cumbersome regulation, perhaps induced by commercial interests; but the student self-control problem ... likely played a role as well. As NBC representative Janice Waller observed, “Even those listeners who clamored for educational programs, Waller found, secretly preferred to listen to comedians such as Jack Benny. These “intellectually dishonest” people “want to appear very highbrow before for their friends . . . but down inside, and within the confines of their own homes, they are, frankly, bored if forced to listen to the majority of educational programs” (as quoted in Craig 2000, pp. 2865–66).

    "The excitement in the late 1950s about educational television outshone even the earlier enthusiasm for radio. An article by Schwarzwalder (1959, pp. 181–182) has an eerily familiar ring: “Educational Television can extend teaching to thousands, hundreds of thousands and, potentially, even millions. . . . As Professor Siepman wrote some weeks ago in The New York Times, ‘with impressive regularity the results come in. Those taught by television seem to do at least as well as those taught in the conventional way.’ . . . The implications of these facts to a beleaguered democracy desperately in need of more education for more of its people are immense. We shall ignore these implications at our national peril.” Schwartzman goes on to claim that any subject, including physics, manual skills, and the arts can be taught by television, and even cites experiments that show “that the discussion technique can be adapted to television.”"


Tuesday, November 10, 2015

Rutgers vs. DeVry

Dean Dad has some interesting (and, based on my experience, valid) observations on teaching at both ends of the prestige spectrum.
Prestigious places tend to be selective, which is to say, they tend only to let in students who have shown the ability to be very successful in traditional high school settings.  These are the students who take lots of Honors classes, run clubs, volunteer, and get high grades.  Students like that are good at school; if they weren’t, they wouldn’t get in.  That frees up faculty to spend relatively little time worrying about pedagogy; they can just present the material and trust that most of the students will get it.  At Rutgers, for example, many undergraduate classes were so large that there wasn’t much choice but to lecture.  Lectures can be “cognitively complex” at a very high level.

When I taught at DeVry, though, I had to unlearn the teaching methods I had picked up at Rutgers, and pick up a whole new set.  These students generally weren’t good at school, or if they were, they didn’t know it.  They didn’t need to have certainties deconstructed; they needed to feel like there was a point in even trying.  I learned quickly, and the hard way, the difference between “what I say” and “what they hear.”  I had to shift focus.  Instead of showing unexpected nuance and depth to a seemingly simple issue (in the ‘90’s, we called that “problematizing”), I had to bring clarity to what was otherwise a frustrating fog.  That’s a different task, requiring different methods.  Lecture had to be cut into small pieces, interspersed among as many applications as possible. 

After a couple of years of teaching at DeVry, I was a far better teacher than I had ever been at Rutgers.  At a basic level, it mattered more.  The top students there -- and there were some -- got some pretty terrific classes, if I do say so myself, and I wasn’t the best teacher there. 

At research universities, faculty are hired and promoted based on research.  I had professors in grad school tell me openly and without shame to minimize the amount of time I spent on teaching, in order to spend more time writing.  In a culture like that, I’m not shocked to discover that much of the teaching is done by lecture. 

Where the “prestige” piece is more relevant is outside of class.  That’s where the ‘signaling’ piece of a selective degree comes into play.  But inside class, I’m not shocked to hear that the gap is small, when it exists at all.  And given the academic job market of the last twenty years, teaching-intensive places have been able to hire from the same pool that the elites have; by now, you can get “cognitively complex” faculty at every level. 



Monday, November 9, 2015

The Blue and the Gray

[Reprinted from 2012]

The famous game designer,* Sid Sackson, had over eighteen thousand games in his personal collection so making his short list was quite an accomplishment, particularly for a game that almost nobody has ever heard of.

On this alone, the Blue and the Gray would be worth a look, but the game also has a number of other points to recommend it: it only takes about three minutes to learn (you can find a complete set of rules here); it is, as far as I know, unique; it raises a number of interesting and unusual strategic questions; and for the educators out there, its Turn-of-the-Century** origins provide some opportunities for teaching across the curriculum. My only major complaint is that it requires a dedicated board, but making your own shouldn't take more than a few minutes.

The object of the game is to be the first to get your general to the center by moving along the designated path while using your soldiers to block your opponent's progress. Since soldiers can capture each other, the game has two offensive options (capturing and advancing) compared to one defensive option (blocking). (Something I learned from developing my own game was the more the designer can shift the focus to offense, the better and faster the game will play.)

I don't know of any attempt to do a serious analysis of the Blue and the Gray. Might be fun to look into. If someone out there finds anything interesting, make sure to let us know.


* Yes, I did just use the phrase, 'famous game designer.'

** I'm going off memory here about the age of the game. You should probably double check before building a lesson plan around this. (see update)

From West Coast Stat Views

UPDATE:

Via the good people at the University of Maryland, here's the original patent from 1903.

Friday, November 6, 2015

Facade Chess [reprint]

[disclaimer -- there are no new chess variants. I don't know who came up with this idea first but I'm pretty sure it wasn't me.]

By most reasonable standards, there are too many chess variants out there already. A few are actually worth playing (such Gliński's hexagonal game), the rest are of interest, if it all, more as thought experiments and programming problems.

One potentially promising area for the latter is variants of imperfect information, which leads us to familiar games like kriegspiel and this variant, facade chess.

Start with a standard board and pieces. When I say standard pieces I mean that you will have one piece that moves like a king, one piece that moves like a queen, two pieces that move like bishops and so on.

The pieces' appearance, however, will not be standard. They will look like tiny replicas of those A-frame signs restaurants put out on the sidewalk, with slots for pictures of chess pieces on either side. On most of the pieces, the picture is the same on the front and the back, but on up to three (or some other agreed on number), the pictures have been switched.

Pieces are lined up in standard position based the picture in the front but they have to move in accordance with the picture on the back (like kriegspiel, this game definitely needs a referee). If for example, the queen had a rook's picture on front of it, you would put it in a corner but you could move it any distance vertically, horizontally or diagonally.

Each move has to be weighed in terms of both position achieved and information revealed -- as soon as that rook moves diagonally, the other player will know something's up. In addition to deduction you can also find out the true identity of a piece by capturing it. Capturing a disguised piece also provides useful information about the disguised pieces still on the board.

I'm not sure how playable facade chess would be -- players would probably tend to under utilize their pieces (moving rooks like pawns or queens like bishops so as not to give away their identities) -- making for a slow game but from an analytic standpoint, the variant could still provide interesting problems. Chess strategies are complex to start with; imagine adding a layer of uncertainty and questions about how much value to put on concealing information.

Thursday, November 5, 2015

The Humble Checker


Yet to calculate is not in itself to analyze. A chess-player, for example, does the one without effort at the other. It follows that the game of chess, in its effects upon mental character, is greatly misunderstood. I am not now writing a treatise, but simply prefacing a somewhat peculiar narrative by observations very much at random; I will, therefore, take occasion to assert that the higher powers of the reflective intellect are more decidedly and more usefully tasked by the unostentatious game of draughts than by all the elaborate frivolity of chess. In this latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound. The attention is here called powerfully into play. If it flag for an instant, an oversight is committed, resulting in injury or defeat. The possible moves being not only manifold but involute, the chances of such oversights are multiplied; and in nine cases out of ten it is the more concentrative rather than the more acute player who conquers. In draughts, on the contrary, where the moves are unique and have but little variation, the probabilities of inadvertence are diminished, and the mere attention being left comparatively what advantages are obtained by either party are obtained by superior acumen.
Edgar Allan Poe -- "The Murders in the Rue Morgue"

Poe's opinion on this matter is more common than you might expect. It's not unusual to hear masters of both chess and checkers (draughts) to admit that they prefer the latter. So why does chess get all the respect? Why do you never see a criminal mastermind or a Bond villain playing in a checkers tournament?

Part of the problem is that we learn the game as children so we tend to think of it as a children's game. We focus on how simple the rules are and miss how much complexity and subtlety you can get out of those rules.

Chess derives most of its complexity through differentiated pieces; with checkers the complexity comes from the interaction between pieces. The result is a series of elegant graph problems where the viable paths change with each move of your opponent. To draw an analogy with chess, imagine if moving your knight could allow your opponent's bishop to move like a rook. Add to that the potential for traps and manipulation that come with forced capture and you have one of the most remarkable games of all time.

There have been any number of checkers variants.* You could even argue that all checkers games are variants since, unlike chess, there is no single, internationally recognized version. Here are some of the best and best-known.



Spanish Checkers

Considered by many connoisseurs to be the best of the national variants. It is distinguished from the American version by a queen's (analogous to a king) ability to jump long. This makes a queen powerful but, since captures are mandatory, easier to capture.






Dama (Turkish Checkers)

Also known as Greek checkers. In this variant, pieces move vertically and horizontally instead of diagonally. Among other things this doubles the playing field.



Lasca

This variant was invented by the second World Chess Champion Emanuel Lasker. It's worth noting that Lasker (who is considered one of the best chess players of all time) would look to checkers when designing his own game.

In Lasca, captured pieces are added to the bottom of columns controlled by whichever player has the top piece. Since jumping only captures the piece on top of the column, players have to take into account not only position but also height and position.

You can get a detailed write-up by following the link or you can see Lasker's original patent application here. He comes off as rather immodest, but he was the world's best chess player and a close friend of Einstein so I guess we can let him slide.


Misère checkers

This one you probably know as suicide or give-away checkers. The object is either to lose all your pieces or have them blocked so that you can't move.



Endless Checkers (or whatever the damned thing is called)

I'm certain I've read about this somewhere though I can't seem to find any record of it. Here, when a piece reaches the last it can move to an appropriate space on the first row (think of a board wrapped around a cylinder). There are no kings in endless checkers.


I have a feeling I'm missing something. Any suggestions?

* Including one I'm particularly fond of, but that's a topic for another post.

[This is a repost.]

Wednesday, November 4, 2015

Kriegspiel and Dark Chess

[I'm going to be doing a math games retrospective for the next few weeks mixing new posts with reprints of some old favorites. The following first appeared in 2013.]

I've been talking about games of perfect information and I have another post on the subject coming up so this seems like a good time to mention two of the best known chess variants of imperfect information.

From the nice people at Wikipedia:
Kriegspiel (German for war game) is a chess variant invented by Henry Michael Temple in 1899 and based upon the original Kriegsspiel developed by Georg von Rassewitz in 1812.[1][2] In this game each player can see their own pieces, but not those of their opponent. For this reason, it is necessary to have a third person (or computer) act as a referee, with full information about the progress of the game. When it is a player's turn he will attempt a move, which the referee will declare to be 'legal' or 'illegal'. If the move is illegal, the player tries again; if it is legal, that move stands. Each player is given information about checks and captures. They may also ask the referee if there are any legal captures with a pawn.
and
Dark chess is a chess variant with incomplete information, similar to Kriegspiel. It was invented by Jens Bæk Nielsen and Torben Osted in 1989. A player does not see the entire board, only their own pieces (including pawns), and squares where these pieces could move.
I've never actually played either of these games (I have enough trouble with unvaried chess), but they raise all sorts of interesting questions about forming a strategy with incomplete information.


Monday, November 2, 2015

Risky Business -- board game math lessons

[I'm going to be doing a math games retrospective for the next few weeks mixing new posts with reprints of some old favorites. The following first appeared in 2012.]




"Let's play Twister; let's play Risk."

No, seriously, let's play Risk, or at least talk about playing Risk. In case you're not familiar with the game, here's the Wikipedia summary
Risk is a turn-based game for two to six players. The standard version is played on a board depicting a political map of the Earth, divided into forty-two territories, which are grouped into six continents. The primary object of the game is "world domination," or "to occupy every territory on the board and in so doing, eliminate all other players."[1] Players control armies with which they attempt to capture territories from other players, with results determined by dice rolls.
(invented by the director of the Red Balloon -- who knew?)




Risk can be a good taking off point for a number of lessons and assignments like:

1. Strategic thinking -- break the class into groups, have them write up rules and recommendations for the game then test these ideas in a tournament

2. (not math but why should that stop you?) -- what modern countries and provinces correspond to the regions on the board? What are they like? You might add naming these countries as a condition for conquering a region.

3. Probability -- what are the chances of taking a country with j attackers and k defenders? What's the expected strength of j if there is a conquest, k if the attack is repulsed?

But the main lesson I'd like to suggest is an introduction to graphs. We have other graph based games and puzzles in our tool chest such as doublets and the six degrees game but Risk is probably the most familiar to the kids. More importantly, it requires actually working with graphs as part of a larger problem.

After the students are acquainted with the game, explain the basic terms of graph theory then show them something like this subgraph of North America




Ask the students to do the following (After checking to make sure I got this right) :

1. Fill in the other countries

2. Explain what's special about nodes like Alaska and Greenland

3. Draw subgraphs of each continent

4. Find the shortest path between various pairs of countries
  4b Find the shortest path between various pairs of countries when certain territories (particularly Russia) are blocked
  4c (advanced) With randomly placed armies, see which path would be easiest to conquer

5. Play a game on a node and edge board

6. Make up new node and edge boards. Give the territories real or mythical names. Try playing a few games on them.