Red, Yellow, and Green Hats
15 hours ago
Friday, December 10, 2010
Card Game: Xactika
I'm a fan of card games. Rook and Euchre were common activities growing up in my family (though I probably play both a bit too haphazardly). When I first learned about Magic: the Gathering in 1994, I quickly jumped on board and became an addict. Every time I find myself in Germany, I relearn how to play Skat. It was easy, then, for the Xactika box to lure me in by advertising "Calling all Euchre players!" (Note: this quote is likely wrong. I don't know where my box is anymore. Does anyone have the actual quote?)
Xactika is a card game with an amazing slice of combinatorics. In this game, each card has four different kinds of "shapes" drawn on it: balls, stars, boxes and cones. For each of these shapes, the card has either one, two, or three included. Thus, one card might have three cones, one ball, two stars and two boxes. No two cards have the same numbers of shapes. Thus, there are 81 cards in the deck. Each card also has a number which is the sum of all the shapes drawn on it. Thus there is one 4-card (one of each shape), four 5-cards (two of one shape, one each of the rest), all the way up to one 12-card (three of each shape). The example with three cones, one ball, two stars and two boxes would have the number 8. Having a knowledge of how many cards have which numbers of shapes becomes very useful during play!
Each card belongs to four different suits represented by the shapes on it (there are twelve in total). Our example belongs to the suits of Three Cones, One Ball, Two Stars and Two Boxes.
Xactika is a trick-taking game. The first player to start each trick chooses a card from their hand and picks one of the suits on that card as they play it. Everyone else must play a card in the called suit if they have one (or playing another card from their hand if they don't). The highest-numbered card played that follows suit wins the trick. In the case of a tie, the last-played card takes priority. Thus, if two 10's were played in one trick (and both followed suit), the second one would win the trick.
In some situations, you can be sure to win a trick. For instance, if I have the 10 with three balls, three cones, three boxes and one star, and I'm leading, I can play the card and confidently say "One star", knowing I'll win the trick; there are no other cards with that value (or higher) that only have one star!
However, it often happens that you don't want to win a trick. After dealing out all the hands, but before play begins, each player "bids" the number of tricks they think they will take. After the hand is played, each player scores points if they made their bid exactly, otherwise you lose points! Thus, you often play a card, intentionally hoping you will lose the trick. In this case, it's better to play a low-valued card and call the suit with the most shapes. A 6 with three of one shape is a great move; any other card in the suit will be above it.
Although this deviates a bit (again) from our topic of combinatorial games, this is an excellent card game with a real unique twist. After learning Xactika, I often would rather play that than other trick-taking games! The box does not lie; I highly recommend this for card game fans!
Note: My Faculty Aide, Ernie, found this excellent video, explaining how to play Xactika.
Have a great Winter Break! I plan to post again the week of January 16, 2011.
Xactika is a card game with an amazing slice of combinatorics. In this game, each card has four different kinds of "shapes" drawn on it: balls, stars, boxes and cones. For each of these shapes, the card has either one, two, or three included. Thus, one card might have three cones, one ball, two stars and two boxes. No two cards have the same numbers of shapes. Thus, there are 81 cards in the deck. Each card also has a number which is the sum of all the shapes drawn on it. Thus there is one 4-card (one of each shape), four 5-cards (two of one shape, one each of the rest), all the way up to one 12-card (three of each shape). The example with three cones, one ball, two stars and two boxes would have the number 8. Having a knowledge of how many cards have which numbers of shapes becomes very useful during play!
Each card belongs to four different suits represented by the shapes on it (there are twelve in total). Our example belongs to the suits of Three Cones, One Ball, Two Stars and Two Boxes.
Xactika is a trick-taking game. The first player to start each trick chooses a card from their hand and picks one of the suits on that card as they play it. Everyone else must play a card in the called suit if they have one (or playing another card from their hand if they don't). The highest-numbered card played that follows suit wins the trick. In the case of a tie, the last-played card takes priority. Thus, if two 10's were played in one trick (and both followed suit), the second one would win the trick.
In some situations, you can be sure to win a trick. For instance, if I have the 10 with three balls, three cones, three boxes and one star, and I'm leading, I can play the card and confidently say "One star", knowing I'll win the trick; there are no other cards with that value (or higher) that only have one star!
However, it often happens that you don't want to win a trick. After dealing out all the hands, but before play begins, each player "bids" the number of tricks they think they will take. After the hand is played, each player scores points if they made their bid exactly, otherwise you lose points! Thus, you often play a card, intentionally hoping you will lose the trick. In this case, it's better to play a low-valued card and call the suit with the most shapes. A 6 with three of one shape is a great move; any other card in the suit will be above it.
Although this deviates a bit (again) from our topic of combinatorial games, this is an excellent card game with a real unique twist. After learning Xactika, I often would rather play that than other trick-taking games! The box does not lie; I highly recommend this for card game fans!
Note: My Faculty Aide, Ernie, found this excellent video, explaining how to play Xactika.
Have a great Winter Break! I plan to post again the week of January 16, 2011.
Tuesday, December 7, 2010
Length of Games
How quickly can a game end? This question came up during a presentation on Thursday of the game Mad Rooks. In this game, Chess-Rook-Like pieces from two teams move around, capturing each other until only one color of rooks remains (then that player wins). If the board starts completely full, then on an 8x8 board, 63 rooks might need to be taken before the game ends.
The presenter noted that he found a scenario where the game could end in 64 moves. Naturally, I wondered whether it could be done in one less. In general, the questions of how fast a game can end, or how long a (short) game can be drawn out are very interesting. I'd also like to know how long a Mad Rooks game can be drawn out. This does not seem trivial!
I could spend tons of class time talking about this last point. Mad Rooks is one of Mark Steere's games (these have been very popular amongst my students for these projects) which are carefully designed to avoid loops. This is often implemented by enforcing the continued reduction of some potential function on the game state from each move. In Mad Rooks, the potential function could map game states into two-element vectors: f(S) = [x, y], where x is the number of uncaptured rooks in the state S, and y is the number of unengaged rooks in the state S. (A rook is "engaged" if it is in line with an opposing rook.) Our potentials can be measured by giving x priority in comparisons, so [x1, y1] < [x2, y2] if: (x1 < x2) or (x1 = x2 and y1 < y2). Now, if for each move, the potential value of the game drops AND we show it can only drop a finite number of times, then at some point the number of uncaptured rooks will be small enough that the game is over.
The rules enforce that if a player moves an engaged rook, it must capture an opposing piece, and if they move an unengaged rook, it must become engaged. Thus, we see that any move must either decrement x (potentially increasing y) or decrement y but leave x alone. Since capturing a rook can only increase y by a bounded value, there is a maximum number of states that can occur during the play of a game.
What is an upper bound we can derive from this? Well, the game starts off with all 64 rooks engaged. Thus, our potential is: [64, 0]. At any given point in the game, capturing a rook could (at most) cause three engaged rooks to no longer be engaged (x decrements, y increases by 3). Also, an engagement move could only cause one previously unengaged piece to be engaged (x remains the same, y decrements). Thus, for each capture, there could be three additional moves to engage pieces. If 63 pieces need to get captured, we see that at most 252 (4 x 63) moves are required.
This is, however, an unreachable upper bound; no matter which piece is killed first, no pieces become unengaged. Also on that last kill, there are no more moves, so three additional engagements are not available; the game is just over. By how much is this upper bound too high, though? In general, for an nxn board, what are the upper and lower bounds on the number of moves?
The presenter noted that he found a scenario where the game could end in 64 moves. Naturally, I wondered whether it could be done in one less. In general, the questions of how fast a game can end, or how long a (short) game can be drawn out are very interesting. I'd also like to know how long a Mad Rooks game can be drawn out. This does not seem trivial!
I could spend tons of class time talking about this last point. Mad Rooks is one of Mark Steere's games (these have been very popular amongst my students for these projects) which are carefully designed to avoid loops. This is often implemented by enforcing the continued reduction of some potential function on the game state from each move. In Mad Rooks, the potential function could map game states into two-element vectors: f(S) = [x, y], where x is the number of uncaptured rooks in the state S, and y is the number of unengaged rooks in the state S. (A rook is "engaged" if it is in line with an opposing rook.) Our potentials can be measured by giving x priority in comparisons, so [x1, y1] < [x2, y2] if: (x1 < x2) or (x1 = x2 and y1 < y2). Now, if for each move, the potential value of the game drops AND we show it can only drop a finite number of times, then at some point the number of uncaptured rooks will be small enough that the game is over.
The rules enforce that if a player moves an engaged rook, it must capture an opposing piece, and if they move an unengaged rook, it must become engaged. Thus, we see that any move must either decrement x (potentially increasing y) or decrement y but leave x alone. Since capturing a rook can only increase y by a bounded value, there is a maximum number of states that can occur during the play of a game.
What is an upper bound we can derive from this? Well, the game starts off with all 64 rooks engaged. Thus, our potential is: [64, 0]. At any given point in the game, capturing a rook could (at most) cause three engaged rooks to no longer be engaged (x decrements, y increases by 3). Also, an engagement move could only cause one previously unengaged piece to be engaged (x remains the same, y decrements). Thus, for each capture, there could be three additional moves to engage pieces. If 63 pieces need to get captured, we see that at most 252 (4 x 63) moves are required.
This is, however, an unreachable upper bound; no matter which piece is killed first, no pieces become unengaged. Also on that last kill, there are no more moves, so three additional engagements are not available; the game is just over. By how much is this upper bound too high, though? In general, for an nxn board, what are the upper and lower bounds on the number of moves?
Friday, December 3, 2010
Alleviating (some) Partiality Confusion
Perhaps it would be best for me to tell future classes: if at any place in a game, one player has a move that the other doesn't, then the game is not impartial. This seems like something very intuitive that one should be able to impart with a quick sentence, but there are many layers of confusion on this point. Perhaps one has to see many examples of impartial games first!
I often see an impartial game defined as one which has the same options for both players. Does that mean {1 | 1} is impartial? No... this is game is in Positive (L), and all impartial games should be in Fuzzy (N) or Zero (P).
In our text, impartial games are defined as follows (page 135 of Lessons in Play):
There could be some confusion here also. Is G = {{1|1} | {1|1}} an impartial game? Certainly the left options equal the right options. Additionally, of the options of G, the same is also true: the left options equal the right options. However, to see that it is not impartial, we have to go down one level further (the options of the options of the options). The necessary recursion of a definition of an impartial game may be implied, but it is probably important to note that the options must all also be impartial.
Is there some middle ground here? On Tuesday, I referred to the game {-1 | 2} being equal to 0, though not impartial. Being an element of either the class N (fuzzy) or P (zero) does not make a game impartial. Other games that aren't impartial:
G: {0 | 0, 1}. Even though G = * (0 dominates 1 for the right player) the options aren't strictly the same.
G: {0, 1 | 0, 1}. Even though the children are the same, those children are not impartial.
G: {X | -X} (where X is a set of games). Here, even though this game MUST be in either N or P, and any strategy for Left translates into a strategy for Right, the game is not impartial.
G: {* | *, *2}. G is in Zero, and all options are impartial, but Left does not have *2 as an option.
For one I'm not sure about, what about the Domineering game consisting of three open boxes in an L-shape? Both players can move to 0 as their only option (so the game is equal to *) but they move there in different ways. Is this game considered impartial?
I apologize above for not figuring out how to use nice and fancy letters for much of my notation!
Have a great weekend! Next week is our last week of classes here and will be my last week posting until next semester.
I often see an impartial game defined as one which has the same options for both players. Does that mean {1 | 1} is impartial? No... this is game is in Positive (L), and all impartial games should be in Fuzzy (N) or Zero (P).
In our text, impartial games are defined as follows (page 135 of Lessons in Play):
"If for a game and all its options, the left options equal the right options, then the game is dubbed impartial."
There could be some confusion here also. Is G = {{1|1} | {1|1}} an impartial game? Certainly the left options equal the right options. Additionally, of the options of G, the same is also true: the left options equal the right options. However, to see that it is not impartial, we have to go down one level further (the options of the options of the options). The necessary recursion of a definition of an impartial game may be implied, but it is probably important to note that the options must all also be impartial.
Is there some middle ground here? On Tuesday, I referred to the game {-1 | 2} being equal to 0, though not impartial. Being an element of either the class N (fuzzy) or P (zero) does not make a game impartial. Other games that aren't impartial:
G: {0 | 0, 1}. Even though G = * (0 dominates 1 for the right player) the options aren't strictly the same.
G: {0, 1 | 0, 1}. Even though the children are the same, those children are not impartial.
G: {X | -X} (where X is a set of games). Here, even though this game MUST be in either N or P, and any strategy for Left translates into a strategy for Right, the game is not impartial.
G: {* | *, *2}. G is in Zero, and all options are impartial, but Left does not have *2 as an option.
For one I'm not sure about, what about the Domineering game consisting of three open boxes in an L-shape? Both players can move to 0 as their only option (so the game is equal to *) but they move there in different ways. Is this game considered impartial?
I apologize above for not figuring out how to use nice and fancy letters for much of my notation!
Have a great weekend! Next week is our last week of classes here and will be my last week posting until next semester.
Tuesday, November 30, 2010
Confusion over partiality
Perhaps the confusion over partiality is not just limited to myself... or perhaps I'm just teaching it poorly.
For our presentations, most students have chosen partisan games, but somehow many students have declared that their games are impartial during the presentations. The reasoning, it seems, is that these games are "impartialish" from the initial position, since both players have similar moves and the value is either in N or P. This has a bit of logic to it; the strategies for each side is independent of the player's identification (Left, Right, Blue, Red, etc). This "fake impartiality" only exists for this initial state, however. Once a move has been made, the game is nearly always partisan.
I feel like there is more to think about here, but perhaps I'm headed down the path of trying to trisect an angle...
When we consider partiality of a game, it does not seem that this is consistent through equivalence. For example:
{ | } is impartial and is equal to zero, but
{ -1 | 2} is not impartial, but is still equal to zero.
Perhaps I'm wrong and we can consider {-1 | 2} to be impartial, but it seems dirty somehow.
Having now studied partisan games to the point where I could teach them for a semester (as far as we got, anyways) I'm very ready to retreat back to my happy, impartial-only world. Nimbers are fairly easy to work with; Ups and Switches and Dyadic Rationals and 3+DoubleUp+* is a bit more frightening. My respect for the effort needed to get Aaron Siegel's CGT Suite to work properly is moon-bound. This stuff is crazy-interesting, but I'll be happy to resume needing only a knowledge of mex and XOR to get some research done.
(As a side note, our presenter won a game today, so the record is now: 6-1 for the audience.)
For our presentations, most students have chosen partisan games, but somehow many students have declared that their games are impartial during the presentations. The reasoning, it seems, is that these games are "impartialish" from the initial position, since both players have similar moves and the value is either in N or P. This has a bit of logic to it; the strategies for each side is independent of the player's identification (Left, Right, Blue, Red, etc). This "fake impartiality" only exists for this initial state, however. Once a move has been made, the game is nearly always partisan.
I feel like there is more to think about here, but perhaps I'm headed down the path of trying to trisect an angle...
When we consider partiality of a game, it does not seem that this is consistent through equivalence. For example:
{ | } is impartial and is equal to zero, but
{ -1 | 2} is not impartial, but is still equal to zero.
Perhaps I'm wrong and we can consider {-1 | 2} to be impartial, but it seems dirty somehow.
Having now studied partisan games to the point where I could teach them for a semester (as far as we got, anyways) I'm very ready to retreat back to my happy, impartial-only world. Nimbers are fairly easy to work with; Ups and Switches and Dyadic Rationals and 3+DoubleUp+* is a bit more frightening. My respect for the effort needed to get Aaron Siegel's CGT Suite to work properly is moon-bound. This stuff is crazy-interesting, but I'll be happy to resume needing only a knowledge of mex and XOR to get some research done.
(As a side note, our presenter won a game today, so the record is now: 6-1 for the audience.)
Tuesday, November 23, 2010
A Homework Worksheet
I am surprised by the success of my class audiences! They continue to be unbeaten against the speaker in our presentations. The class is now 5-0!
This week is Thanksgiving; there will be no post on Friday and today's post will be light.
As I mentioned, I have been making worksheets for homeworks for my class. I just finished the last (fourth) one this week. I won't hand it out to my students until next week. In case anyone's interested in seeing what these look like, here is the first one.
For those of you in the states, have a great thanksgiving!
This week is Thanksgiving; there will be no post on Friday and today's post will be light.
As I mentioned, I have been making worksheets for homeworks for my class. I just finished the last (fourth) one this week. I won't hand it out to my students until next week. In case anyone's interested in seeing what these look like, here is the first one.
For those of you in the states, have a great thanksgiving!
Friday, November 19, 2010
Point-Value end states
Student presentations have been a huge success so far! Competition is a funny thing, though. Somehow the audience is unbeaten (through four presentations) even though things always begin with the students collaborating: "We shouldn't try too hard to win; we should let win so they can earn the bonus points!" By the middle of the game, this has been forgotten; the audience is trying to optimize their moves. For hard games, the collaborating audience apparently has the advantage here!
Today, during our Reversi presentation, the question came up about the value of the final game states. I mentioned that one interpretation was that the result is equal to the number of blue circles minus the number of red circles. Another way to think of it was to consider that immediately after the Reversi game ends, a new game is played equal to that number value. This avoids ties: if the score is the same at the end, then the last player to move on the original game wins.
The students grabbed on to this idea and ran with it, chatting about it as the game continued. This method extends to other similar games that normally end by comparing point scores: Dots 'n' Boxes, Flume, etc. Even Hex can be conceived like this: the "score" for the winner could be the number of uncolored hexagons remaining on the board. Thus, the faster you win, the more the game is worth.
Notice that this doesn't make a difference if this is not part of a game sum. Without other attached games (or bragging rights) the only important part is whether or not you can win this game. In this case, it is instead equivalent to say that after game play is finished, we just append a game of value either -1 or 1 after the original game ends, depending on who "earned more points".
Does anyone ever play game sums with either of these methods? Anyone prefer one over the other?
Today, during our Reversi presentation, the question came up about the value of the final game states. I mentioned that one interpretation was that the result is equal to the number of blue circles minus the number of red circles. Another way to think of it was to consider that immediately after the Reversi game ends, a new game is played equal to that number value. This avoids ties: if the score is the same at the end, then the last player to move on the original game wins.
The students grabbed on to this idea and ran with it, chatting about it as the game continued. This method extends to other similar games that normally end by comparing point scores: Dots 'n' Boxes, Flume, etc. Even Hex can be conceived like this: the "score" for the winner could be the number of uncolored hexagons remaining on the board. Thus, the faster you win, the more the game is worth.
Notice that this doesn't make a difference if this is not part of a game sum. Without other attached games (or bragging rights) the only important part is whether or not you can win this game. In this case, it is instead equivalent to say that after game play is finished, we just append a game of value either -1 or 1 after the original game ends, depending on who "earned more points".
Does anyone ever play game sums with either of these methods? Anyone prefer one over the other?
Tuesday, November 16, 2010
Lectures are over... how to make them better!
Thursday was our last "regular" class period. From today until the end of the semester, students will be presenting games they've researched on their own. If there is any extra time, I will fill in by attacking some of the topics we didn't cover throughout the semester.
There's a lot we didn't cover. Just on Thursday, I skipped ahead and covered Nimbers. We had only just started to cover infinitesimals: Up and Down. We hadn't quite gotten to DoubleUp = Up + Up. We were close to covering Switches.
I hope to teach this class again, but how could I improve things?
First off, Lessons in Play is an excellent text, but there are a number of things that should just be skipped. My students are not (all) math seniors, but instead a mix of computer science and math majors from sophomores to seniors. This means I should just skip more of the proofs in class. Many of the theorems are intuitive, and students are so hungry to learn how to evaluate these games, they want more statements of what is true and less explanations why. I think it's a shame I didn't get all the way to switches, these students really wanted to know what to do with {x | y} when x > y!
Second, I should use more worksheets. The last two weeks I started making worksheets for my students for their homework assignments. That worked really well. Somehow I didn't hammer it in hard enough that a game tree is the best proof. These worksheets take the students through the steps to prove the result, enforcing all the steps that are necessary.
Also, I think I need to choose better games to play during class time. Better doesn't mean more exciting, but instead more relevant to the topics we've chosen. Some games have more infinitesimals, while others are really great examples of employing the Simplest Number Theorem.
One thing that worked really well were the programming projects I assigned in class. For our last project, students must find the Grundy values of Cram games, implementing these properties straight from the definitions.
Exciting! I can't wait to teach this again!
There's a lot we didn't cover. Just on Thursday, I skipped ahead and covered Nimbers. We had only just started to cover infinitesimals: Up and Down. We hadn't quite gotten to DoubleUp = Up + Up. We were close to covering Switches.
I hope to teach this class again, but how could I improve things?
First off, Lessons in Play is an excellent text, but there are a number of things that should just be skipped. My students are not (all) math seniors, but instead a mix of computer science and math majors from sophomores to seniors. This means I should just skip more of the proofs in class. Many of the theorems are intuitive, and students are so hungry to learn how to evaluate these games, they want more statements of what is true and less explanations why. I think it's a shame I didn't get all the way to switches, these students really wanted to know what to do with {x | y} when x > y!
Second, I should use more worksheets. The last two weeks I started making worksheets for my students for their homework assignments. That worked really well. Somehow I didn't hammer it in hard enough that a game tree is the best proof. These worksheets take the students through the steps to prove the result, enforcing all the steps that are necessary.
Also, I think I need to choose better games to play during class time. Better doesn't mean more exciting, but instead more relevant to the topics we've chosen. Some games have more infinitesimals, while others are really great examples of employing the Simplest Number Theorem.
One thing that worked really well were the programming projects I assigned in class. For our last project, students must find the Grundy values of Cram games, implementing these properties straight from the definitions.
Exciting! I can't wait to teach this again!
Friday, November 12, 2010
Game Description: NoGo
I don't yet know how to play go. I just got my set in the mail last Monday, and I'm looking forward to finding someone at Wittenberg to help me get started. Luckily, there is the game NoGo. I may not know just how much this game is related to Go, but at least it is teaching me to play pieces on the intersections of lines instead of the boxes.
NoGo works in the following way: players alternate placing white or black stones on a grid. Each intersection is adjacent to the four connected intersections. In the game, a turn consists of adding one of your stones to the board on an empty intersection. Plays are otherwise restricted only by the following rule: each contiguous group of stones of one color must be adjacent to an empty intersection. Thus the board resulting from any move must have this property, both for your color and stones of the opposing color.
For example, look at these two game states:
On the left-hand-side board, neither player has a move, placing any stone in the lower-left corner will prevent all connected regions from touching an empty intersection. On the right-hand board, the Left player has a move: they can add a black stone. This move connects the two regions, which has two pieces still touching the empty spot. Right does not have a move; no white stone can be placed which will connect to any blank spots.
This game is a bit tricky. Sometimes you want to have more of a presence so that your components are large. Other times, you wish you had smaller connected pieces, feeding off of an empty space.
I don't know how this relates to the grand game of Go (I hope to soon) but NoGo has already been fun to play!
Tuesday, November 9, 2010
MCURCSM
Exciting news for my department: we are hosting the Midstates Conference for Undergraduate Research in Computer Science and Mathematics (MCURCSM) in just a few weeks on November 20th!
Liberal-arts undergraduate students often find themselves performing excellent research, and conferences such as these are perfect outlets for our students to show off their work. We're very excited to be holding this year's conference here at Wittenberg.
Unfortunately, I will be out of town that Saturday and will not be attending. Please come for the great student presentations and enjoy the awesome work performed by many first-time researchers!
Liberal-arts undergraduate students often find themselves performing excellent research, and conferences such as these are perfect outlets for our students to show off their work. We're very excited to be holding this year's conference here at Wittenberg.
Unfortunately, I will be out of town that Saturday and will not be attending. Please come for the great student presentations and enjoy the awesome work performed by many first-time researchers!
Friday, November 5, 2010
Tuesday, November 2, 2010
Impossible Game States
While preparing some old work to go into my thesis two years ago, I realized a potential hole in my construction: could the Atropos boards described always occur in the midst of a game? I had built some convoluted board pieces, then glued them together in PSPACE reductions. But could these monstrosities actually be the state of a half-played game? Atropos has a requirement that players must play adjacent to the last play (if possible, otherwise you may play anywhere). Thus, some game states are impossible to reach.
Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.
Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.
A cookie in Chomp cannot be missing when any cookies up and to the right are also present.
Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!
Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?
Are there any games where it is difficult to determine whether the game is in an impossible state?
Here, the lone red circle and the green and blue to the right are disjoint sections that could not have occurred without a colored circle surrounded by colored circles.
Does this ever happen with other games? Naturally, we need to consider a game that has regular starting position(s). Assuming we always start from a full n-by-m grid in Chomp, we will never see a board that is missing cookies in the wrong places.
A cookie in Chomp cannot be missing when any cookies up and to the right are also present.
Some games aren't quite so clear-cut. In Domineering, we would never have a board with an odd number of checkers covered. However, we might have that board as a piece of a more complex partition of boards, so it could be a legitimate subsection!
Consider Alice and Bob, who sit down to play a game of Chess. After a while, Bob thinks he is winning, and gets up to find a snack in another room. He returns and looks at the game board, realizing that he is actually in a bad state. What happened? Perhaps Alice switched pieces around, or perhaps Bob does not correctly recall the position of pieces. If Bob knows that no pawns have reached the opposite edge of the board, does Bob have any chance to prove that the current board state is illegal?
Are there any games where it is difficult to determine whether the game is in an impossible state?
Friday, October 29, 2010
Breaking Symmetry
Right away while teaching combinatorial games, my students latched on to the idea of symmetric arguments. It comes early in the book and is more convincing of a good plan of attack than greedy strategies (and is easier to use than finding transformations to other games). Whenever we play a new game, the students first look for ways to play symmetrically and then how to escape such a situation. This is an excellent pattern, since symmetry is not always a trivial venture, and likely a good indicator you are competing with a gamester.
Okay, so say your opponent in a game is employing a symmetry-based strategy, which will be successful unless you break it. You see an opportunity to break the symmetry, but it's something you can do now or later. When should you do it?
I bring this up because Neil McKay noticed a flaw in the symmetry argument for the first player in Flume. Gasp! I have amended the game table but hope to have the matter resolved. I will present Neil's illuminating break at a later date (after it is not immediately relevant to my class; some students are actually reading this!) but it's great that he found a counterexample to the strategy.
This event makes me curious about symmetric strategies in general. Flume was a bit of a special case, because the symmetry employs two steps each turn: first be greedy and take all the free spots, then turn around and make the same move your opponent did, allowing them to make the same great moves you just did. (Luckily, you should always be ahead by one piece.) This seems to me as a bit of an "impure symmetry" (perhaps more so now that there's an escape). I still hope that there is a method to restore the symmetric state in Flume, though I'm likely biased at finding out I was wrong.
Even more so, I'm interested in other surprising examples of symmetric strategies. Are there any examples of games where symmetry can win you the day, even when you wouldn't expect it? Are there any other examples of impure symmetry that wind out working great? Are there any examples of breakable symmetry strategies that are actually robust enough to be restored?
I'd love to hear about them!
Okay, so say your opponent in a game is employing a symmetry-based strategy, which will be successful unless you break it. You see an opportunity to break the symmetry, but it's something you can do now or later. When should you do it?
I bring this up because Neil McKay noticed a flaw in the symmetry argument for the first player in Flume. Gasp! I have amended the game table but hope to have the matter resolved. I will present Neil's illuminating break at a later date (after it is not immediately relevant to my class; some students are actually reading this!) but it's great that he found a counterexample to the strategy.
This event makes me curious about symmetric strategies in general. Flume was a bit of a special case, because the symmetry employs two steps each turn: first be greedy and take all the free spots, then turn around and make the same move your opponent did, allowing them to make the same great moves you just did. (Luckily, you should always be ahead by one piece.) This seems to me as a bit of an "impure symmetry" (perhaps more so now that there's an escape). I still hope that there is a method to restore the symmetric state in Flume, though I'm likely biased at finding out I was wrong.
Even more so, I'm interested in other surprising examples of symmetric strategies. Are there any examples of games where symmetry can win you the day, even when you wouldn't expect it? Are there any other examples of impure symmetry that wind out working great? Are there any examples of breakable symmetry strategies that are actually robust enough to be restored?
I'd love to hear about them!
Monday, October 25, 2010
Nothing Tomorrow
I hope your tomorrow is full of wonderful things. Sadly, a post here will not be one of them.
I have spent lots of time out of the office due to unexpected appointments. Teaching is my number-one work priority, and so other things must fall to the wayside a bit.
Also... I need to figure out how to get Blogger to report the post as being dated with the day I actually Post it, not the day I first start editing it.
I do hope to return on Friday with another post!
I have spent lots of time out of the office due to unexpected appointments. Teaching is my number-one work priority, and so other things must fall to the wayside a bit.
Also... I need to figure out how to get Blogger to report the post as being dated with the day I actually Post it, not the day I first start editing it.
I do hope to return on Friday with another post!
Friday, October 22, 2010
Chickening out on Chess
I haven't played a game of Chess in years. I was recently approached by some students asking to start a Chess Club, and we're going ahead with that. I hope I'll be able to learn to play moderately from them!
Yesterday we were set to have another "Game Day" in class where students would find values (and outcome classes) of different game states. I was hoping to do Chess, and had been flipping through Noam Elkies' paper on Chess end games. A lot of stuff in there was excellent and would really get my class thinking.
But I chickened out. I know that most of my students know how Chess works, but I wasn't sure if they'd be able to see some of the acceptable moves quickly. I was nervous teams might spend half the class figuring out what was going on in one example. Worse, I was afraid I wouldn't be able to cook up new examples on the fly as I have the rest of the year. I have to really be careful with Chess to avoid instances that are not short games.
Instead, I introduced Konane (I'll write separately about this game some time; it's very nice). I played a few times with my aide the day before, then threw a bunch of boards up on the whiteboards. The students dove in immediately; writing up outcome classes, values, and questioning or confirming the results of other teams. I stopped every so often to explain how to derive some values and to switch up partners.
So far, we have only covered Nimbers (defined only via equivalence to Nim heaps) and positive and negative integers, so some of the boards were not given explicit values by the students, as expected. It is almost equally rewarding when students express frustration over not knowing the value of Up---I know they're interested to hear more from our lecture days.
We really should do Chess, though. There are only a few more weeks before we get deep into the student presentations, so I'll have to introduce it soon! Hopefully I'll have good news to report then.
Yesterday we were set to have another "Game Day" in class where students would find values (and outcome classes) of different game states. I was hoping to do Chess, and had been flipping through Noam Elkies' paper on Chess end games. A lot of stuff in there was excellent and would really get my class thinking.
But I chickened out. I know that most of my students know how Chess works, but I wasn't sure if they'd be able to see some of the acceptable moves quickly. I was nervous teams might spend half the class figuring out what was going on in one example. Worse, I was afraid I wouldn't be able to cook up new examples on the fly as I have the rest of the year. I have to really be careful with Chess to avoid instances that are not short games.
Instead, I introduced Konane (I'll write separately about this game some time; it's very nice). I played a few times with my aide the day before, then threw a bunch of boards up on the whiteboards. The students dove in immediately; writing up outcome classes, values, and questioning or confirming the results of other teams. I stopped every so often to explain how to derive some values and to switch up partners.
So far, we have only covered Nimbers (defined only via equivalence to Nim heaps) and positive and negative integers, so some of the boards were not given explicit values by the students, as expected. It is almost equally rewarding when students express frustration over not knowing the value of Up---I know they're interested to hear more from our lecture days.
We really should do Chess, though. There are only a few more weeks before we get deep into the student presentations, so I'll have to introduce it soon! Hopefully I'll have good news to report then.
Friday, October 15, 2010
Updated Game Table
I updated this table of Combinatorial games and some of their known properties. This time I added a column to list variants of games. I still want to add more games and properties, please inform me of more results to add! These could include:
More Games! I'd love to add more rows.
Properties! I'm sure there are some incomplete cells that could be updated. This time I added "Open" if the problem is known to be open (there must be more of these).
References! I added a bunch of links, but there must be more (or better) supporting documentation for some things. I would love to add more links.
More Games! I'd love to add more rows.
Properties! I'm sure there are some incomplete cells that could be updated. This time I added "Open" if the problem is known to be open (there must be more of these).
References! I added a bunch of links, but there must be more (or better) supporting documentation for some things. I would love to add more links.
Wednesday, October 13, 2010
Game Description: Toads and Frogs
Prior to this semester, I got a lot of helpful suggestions for preparing to teach Combinatorial Games. One reader, Joshua Biedenweg (instructing at UC Santa Barbara while an undergrad!), was in the middle of teaching his own CGT class and suggested I include Toads and Frogs in the class. I liked his reasoning, but wound up using Domineering as the main guiding example, as it is used throughout our text.
For our recent "game day" class, I tried out his suggestion, and Toads and Frogs worked out really well. Students quickly figured out the value of many games, including some games of arbitrary sizes!
Toads and Frogs is a game invented by Richard Guy. A game state consists of a horizontal row of "spaces", each of which either empty or inhabited by a Toad or Frog. Toads face right (but are controlled by the Left player), and Frogs face left (controlled by Right), and may only move in the direction they are facing(Toads move "to", Frogs move "fro"). Each turn, a player chooses one of their amphibians and moves it. An amphibian may move one space if that space is empty, or may instead jump over an adjacent opposing piece if the space behind that piece is empty.
For example, in the following situation a T is a Toad, an F is a Frog, and an underscore, _ is a blank space. Then in this game:
Left can move both of his amphibians, resulting in either _ T _ T F _ or T _ _ _ F T. Right only has one frog to move, and can move to T _ F T _ _. As my class found out, it is fairly easy to evaluate a lot of different positions, and as Josh explained to me, this is a great demonstration of different game values. Sums are also very easy to do: just draw the rows on top of each other.
Simple rules, simple game description. And, fortunately, this game is hard to play well! Jesse Hull showed that NP-hard instances of the game exist (using techniques I am not familiar with). I wonder whether it can be shown that determining a winner is also PSPACE-complete.
The best challenge I came up with for my class was to add two games together:
Where the top row has one more space between amphibians than the bottom. The result is very nice (* = {0|0}) especially since students' intuition had them first thinking it depended on whether the top or bottom game had the odd number of spaces.
Thanks Josh, for telling me to check this game out!
For our recent "game day" class, I tried out his suggestion, and Toads and Frogs worked out really well. Students quickly figured out the value of many games, including some games of arbitrary sizes!
Toads and Frogs is a game invented by Richard Guy. A game state consists of a horizontal row of "spaces", each of which either empty or inhabited by a Toad or Frog. Toads face right (but are controlled by the Left player), and Frogs face left (controlled by Right), and may only move in the direction they are facing(Toads move "to", Frogs move "fro"). Each turn, a player chooses one of their amphibians and moves it. An amphibian may move one space if that space is empty, or may instead jump over an adjacent opposing piece if the space behind that piece is empty.
For example, in the following situation a T is a Toad, an F is a Frog, and an underscore, _ is a blank space. Then in this game:
T _ _ T F _
Left can move both of his amphibians, resulting in either _ T _ T F _ or T _ _ _ F T. Right only has one frog to move, and can move to T _ F T _ _. As my class found out, it is fairly easy to evaluate a lot of different positions, and as Josh explained to me, this is a great demonstration of different game values. Sums are also very easy to do: just draw the rows on top of each other.
Simple rules, simple game description. And, fortunately, this game is hard to play well! Jesse Hull showed that NP-hard instances of the game exist (using techniques I am not familiar with). I wonder whether it can be shown that determining a winner is also PSPACE-complete.
The best challenge I came up with for my class was to add two games together:
T _ _ ... _ _ _ F
+
T _ _ ... _ _ F
+
T _ _ ... _ _ F
Where the top row has one more space between amphibians than the bottom. The result is very nice (* = {0|0}) especially since students' intuition had them first thinking it depended on whether the top or bottom game had the odd number of spaces.
Thanks Josh, for telling me to check this game out!
Tuesday, October 12, 2010
Still no post...
I just returned to the office today and have been busy all day catching up. I am planning on having a new post ready on Friday.
Sorry again!
Sorry again!
Friday, October 8, 2010
Friday, October 1, 2010
Nearly Shooting Myself in the Foot with Misere Sums
Oops!
Last week, in an effort to relive my success with finding negative games by summing to zero, I tried the same thing with a new game. The plan was to add states of a new game to states of games we had already covered, then see if they sum to zero. I wrote up states of the new game, and challenged students to find states in Clobber, Amazons, Nim, etc, that summed with the original game to get zero. Unfortunately, I hadn't had a good idea for a new game, so instead I decided we would play Misere Clobber.
Pretty quickly, students asked me: "Wait, how do we add a normal play game to a misere game?"
Oops!
Somehow I did some quick thinking (I usually can never seem to do this in front of a class) and reminded myself of how to make this "legitimate". I wound up writing two options on the board:
Either players are not allowed to make the last play in the misere game, or whenever a player makes the last move in the misere game, they immediately lose.
Whew! Things progressed pretty nicely at that point. Still, I was wary of teaching them that games can have the misere property instead of attaching that property to the method for playing a game. At least this took care of covering all the mechanics we needed to find negative games.
I took a number of wonderful pictures of the boards and of my students playing, but my new phone seems to have trouble with its camera and the pictures were never stored. Instead, enjoy these pictures one of my art-minded students drew on my whiteboard after we covered the definition of a game negative. :)
Last week, in an effort to relive my success with finding negative games by summing to zero, I tried the same thing with a new game. The plan was to add states of a new game to states of games we had already covered, then see if they sum to zero. I wrote up states of the new game, and challenged students to find states in Clobber, Amazons, Nim, etc, that summed with the original game to get zero. Unfortunately, I hadn't had a good idea for a new game, so instead I decided we would play Misere Clobber.
Pretty quickly, students asked me: "Wait, how do we add a normal play game to a misere game?"
Oops!
Somehow I did some quick thinking (I usually can never seem to do this in front of a class) and reminded myself of how to make this "legitimate". I wound up writing two options on the board:
Either players are not allowed to make the last play in the misere game, or whenever a player makes the last move in the misere game, they immediately lose.
Whew! Things progressed pretty nicely at that point. Still, I was wary of teaching them that games can have the misere property instead of attaching that property to the method for playing a game. At least this took care of covering all the mechanics we needed to find negative games.
I took a number of wonderful pictures of the boards and of my students playing, but my new phone seems to have trouble with its camera and the pictures were never stored. Instead, enjoy these pictures one of my art-minded students drew on my whiteboard after we covered the definition of a game negative. :)
Tuesday, September 28, 2010
Searching for Games
There is no final exam in my combinatorial games class. Instead, the last four or so weeks will consist of student presentations. Each student is tasked with choosing a combinatorial game (that we haven't covered heavily in class) and researching "something interesting" about that game. Students will then present their findings.
The interesting thing does not need to be something super heavy, but should be non-trivial. So far I have three students who have chosen their games: Flume, Reversi and Hex. Of those three, two students have picked their "interesting things": one will code a playable version of Hex, while the other will describe the first-player winning strategy in Flume. In addition to these sort of options, students could write a program to determine the outcome class of their game, or just describe some interesting property (for example, that Hex cannot end in a tie or that the first player has a winning strategy in Chomp).
Part of my hope here is to learn more combinatorial games myself. I continue to work on expanding this table of games.
The other ten students have yet to choose a game. I have directed them to check out some resources such as Mark Steere's extensive list of creations, as well as the long appendix of games in our text, Lessons in Play.
Do you know of any other places I can point them to to find games? Certainly there is also a degree of procrastination, but it would also be great to give my students more resources. Also, it might come down to the point where I am forcing games upon the students. In that case, suggestions will be very helpful! Perhaps you've developed a game you'd like someone to check out!
The interesting thing does not need to be something super heavy, but should be non-trivial. So far I have three students who have chosen their games: Flume, Reversi and Hex. Of those three, two students have picked their "interesting things": one will code a playable version of Hex, while the other will describe the first-player winning strategy in Flume. In addition to these sort of options, students could write a program to determine the outcome class of their game, or just describe some interesting property (for example, that Hex cannot end in a tie or that the first player has a winning strategy in Chomp).
Part of my hope here is to learn more combinatorial games myself. I continue to work on expanding this table of games.
The other ten students have yet to choose a game. I have directed them to check out some resources such as Mark Steere's extensive list of creations, as well as the long appendix of games in our text, Lessons in Play.
Do you know of any other places I can point them to to find games? Certainly there is also a degree of procrastination, but it would also be great to give my students more resources. Also, it might come down to the point where I am forcing games upon the students. In that case, suggestions will be very helpful! Perhaps you've developed a game you'd like someone to check out!
Monday, September 27, 2010
Two turning points in my Games Class
Teaching this combinatorial games class has been tough. I am simultaneously teaching Software Engineering and Algorithms, and while both are challenging courses for students, they are going pretty smoothly. I know what I can expect from those students and know what I need to get across to them.
Combinatorial Games, on the other hand, is an adventure into some tricky territory. Since I have a wide variety of math and computer science students, I'm having a hard time making the correct assumptions about what my students already know. Since this is a new-fangled elective, I also don't have specific goals I need to communicate.
The structure of the course has been to spend one of the two class periods each week focusing on playing a new game. (Here is the class schedule so far.) The first week we played Domineering, then Clobber, then Toppling Dominoes. Students would play a bit amongst themselves, and do a great job answering questions I posed. But, after a few games and a few opponent-switches, they would get a bit bored. The 1.5 hour class started to drag on and a few students would actually ask me to return to lecturing. (Luckily, I brought some notes with me!)
Then, in the fourth week, we played Amazons. Wow. The students responded to this by actively getting into the game and trying to figure out good moves. The idea of outcome classes started to click and when I called for a change of opponents, very few people got up in the first minute.
Last week, we did something even better. I had the students play game sums (Note to me: I should have done this sooner!) and try to find different games that summed to zero. The base game was Amazons, and I drew different instances on the whiteboard and challenged the students to find different Domineering, Clobber and Toppling Dominoes games that, when added to the Amazons board, summed to zero. The result was possibly the best class period I have ever taught... even though I personally did very little. Students quickly took to their game boards, reasoned about some sums, then started filling up the marker board. Almost immediately some things written on the board were challenged (though no one was brash enough to erase another student's work without permission) and some excellent discussion began to take place.
Wow.
It's hard to describe that level of engagement by students. Everyone was knee-deep in advanced mathematical material, experiencing it first-hand. We haven't yet defined many possible game values (I'm not sure we've defined anything rigorously yet) but students were quickly clamoring for an explanation of different fuzzy games and non-number values.
As I continue this semester, I think I need to make sure that every topic is motivated, and perhaps play games in each class (instead of every other). These last two game days have made an amazing argument for that!
Combinatorial Games, on the other hand, is an adventure into some tricky territory. Since I have a wide variety of math and computer science students, I'm having a hard time making the correct assumptions about what my students already know. Since this is a new-fangled elective, I also don't have specific goals I need to communicate.
The structure of the course has been to spend one of the two class periods each week focusing on playing a new game. (Here is the class schedule so far.) The first week we played Domineering, then Clobber, then Toppling Dominoes. Students would play a bit amongst themselves, and do a great job answering questions I posed. But, after a few games and a few opponent-switches, they would get a bit bored. The 1.5 hour class started to drag on and a few students would actually ask me to return to lecturing. (Luckily, I brought some notes with me!)
Then, in the fourth week, we played Amazons. Wow. The students responded to this by actively getting into the game and trying to figure out good moves. The idea of outcome classes started to click and when I called for a change of opponents, very few people got up in the first minute.
Last week, we did something even better. I had the students play game sums (Note to me: I should have done this sooner!) and try to find different games that summed to zero. The base game was Amazons, and I drew different instances on the whiteboard and challenged the students to find different Domineering, Clobber and Toppling Dominoes games that, when added to the Amazons board, summed to zero. The result was possibly the best class period I have ever taught... even though I personally did very little. Students quickly took to their game boards, reasoned about some sums, then started filling up the marker board. Almost immediately some things written on the board were challenged (though no one was brash enough to erase another student's work without permission) and some excellent discussion began to take place.
Wow.
It's hard to describe that level of engagement by students. Everyone was knee-deep in advanced mathematical material, experiencing it first-hand. We haven't yet defined many possible game values (I'm not sure we've defined anything rigorously yet) but students were quickly clamoring for an explanation of different fuzzy games and non-number values.
As I continue this semester, I think I need to make sure that every topic is motivated, and perhaps play games in each class (instead of every other). These last two game days have made an amazing argument for that!
Thursday, September 23, 2010
Out again tomorrow
Unfortunately I will be out again tomorrow. With any luck I'll be back in action next week.
Wednesday, September 15, 2010
Quantum Chess
Recently there was some cool board game buzz about combining quantum super-positions and chess: Quantum Chess.
The game was designed by Selim Akl as a response to the brute-force superiority of computers in standard chess. Alice Wismath, working with Dr. Akl, implemented a non-quantum version (they point out: "a true quantum board may be a few years in the future") as a Java 1.6 applet (I had to upgrade my browser's Java).
The basic idea behind this game is that the identity of each piece (aside from Kings) exists in a super-position before it is moved. The actual piece will be one of two different options (for example, either a rook or a knight) which is only known once you decide to move that piece. Thus, each turn consists of first choosing a piece to move, then determining what type of piece it actually is, then moving that piece.
Naturally, since the value of the pieces is based on some randomness (quantumness is considered randomness, right?) this is not strictly a combinatorial game. Until we have quantum boards, it's not exactly a board game either... Still, we can implement this in a non-quantum way using a big checkerboard and two sets of chess pieces. By putting two pieces on the same square to indicate the super-position for non-collapsed pieces, you can then decide the actual value by flipping a coin once the piece is chosen.
In any case, this is an extremely original game and an excellent work by Akl and Wismath. With any luck this will bring interest into both games and general quantum... ness. As you can see, I need a lesson on quantum mechanics and quantum computing!
Note: I will be out of action on Tuesday, so the next post will probably not occur until next Friday.
The game was designed by Selim Akl as a response to the brute-force superiority of computers in standard chess. Alice Wismath, working with Dr. Akl, implemented a non-quantum version (they point out: "a true quantum board may be a few years in the future") as a Java 1.6 applet (I had to upgrade my browser's Java).
The basic idea behind this game is that the identity of each piece (aside from Kings) exists in a super-position before it is moved. The actual piece will be one of two different options (for example, either a rook or a knight) which is only known once you decide to move that piece. Thus, each turn consists of first choosing a piece to move, then determining what type of piece it actually is, then moving that piece.
Naturally, since the value of the pieces is based on some randomness (quantumness is considered randomness, right?) this is not strictly a combinatorial game. Until we have quantum boards, it's not exactly a board game either... Still, we can implement this in a non-quantum way using a big checkerboard and two sets of chess pieces. By putting two pieces on the same square to indicate the super-position for non-collapsed pieces, you can then decide the actual value by flipping a coin once the piece is chosen.
In any case, this is an extremely original game and an excellent work by Akl and Wismath. With any luck this will bring interest into both games and general quantum... ness. As you can see, I need a lesson on quantum mechanics and quantum computing!
Note: I will be out of action on Tuesday, so the next post will probably not occur until next Friday.
Tuesday, September 14, 2010
Oops!
Hmmm, apparently I've been a bit confused recently about getting posts out at the correct time. I somehow posted twice last week on Tuesday without realizing it until Friday.
Hmmm...
Unfortunately, I have just run out of time today.
I will have something new to say on Friday and will get back on my regular schedule.
Sorry!
Hmmm...
Unfortunately, I have just run out of time today.
I will have something new to say on Friday and will get back on my regular schedule.
Sorry!
Tuesday, September 7, 2010
UGrad Course Update and a Mini Course in Amsterdam
So far, things are going well with the combinatorial games course I am teaching this semester. This is an undergraduate level course, aimed at both Math and CS students, and includes sophomores, juniors and seniors. Today it came up that the class feels both like a graduate-level course and the third grade. We are covering advanced material, but at a reasonable pace and with a very excited audience.
The class meets two days a week for 90 minutes. I try to spend the majority of one day letting students play a new game, asking them questions while they are playing. So far, this has gone very smoothly, alternating between game-playing days and note-taking days. I keep track of the games we've played on our class schedule. (Notice I haven't chosen anything in advance!)
I have assigned programming assignments as well as written homework. The students will end the semester giving oral presentations covering games not studied in class. I'm already looking forward to this!
I've already gotten some advice, but I'd naturally love to get more. If you've taught or attended a CGT course (even if you're one of my current students) any comments would be welcome.
On another note, I saw this announcement for a Mini-course in positional games next week in Amsterdam. I have the sudden desire to be in Amsterdam! :)
The class meets two days a week for 90 minutes. I try to spend the majority of one day letting students play a new game, asking them questions while they are playing. So far, this has gone very smoothly, alternating between game-playing days and note-taking days. I keep track of the games we've played on our class schedule. (Notice I haven't chosen anything in advance!)
I have assigned programming assignments as well as written homework. The students will end the semester giving oral presentations covering games not studied in class. I'm already looking forward to this!
I've already gotten some advice, but I'd naturally love to get more. If you've taught or attended a CGT course (even if you're one of my current students) any comments would be welcome.
On another note, I saw this announcement for a Mini-course in positional games next week in Amsterdam. I have the sudden desire to be in Amsterdam! :)
Game Description: Martian Chess
Just last week, I forced my aide to sit down and play Martian Chess with me. This is one of the games I was introduced to at Origins this past year, and have been looking forward to the start of the semester to try it out more.
This game is sort of a more complex version of Clobber: pieces are arranged on a checkerboard, and they "clobber" pieces near them---except that there are 3 different types of pieces and they move in different ways. Pawns move one space in any direction (including diagonal), drones may move up to two spaces (but only horizontally and vertically) and queens may move exactly as queens in Chess. Pieces may not jump over other pieces. Okay, maybe it is more like Chess than Clobber...
Nevertheless, the goal is to take opponents' pieces. 3 points are given for a queen, 2 for each drone and 1 for each pawn captured. The game ends when a player no longer controls any pieces. The twist, however, is that when you capture an opponents' piece, they now take control of your piece on the board. This occurs because each player "owns" two opposite quadrants of the board: they may move any pieces in their quadrant. Capturing an opponents' piece means moving into an opponents' section and surrendering the piece you just owned.
Martian Chess is a really fun game that forces you to think on your toes. Just about when I seemed to be coming up with a strong strategy, Ernie pulled a new trick on me and had me completely second-guessing myself. I would really like to play this game in class, but, alas, I don't think I have enough Icehouse pieces!
Let's use this wacky ownership in a variant of Clobber: Reverse Clobber. Now, when I clobber an opposing piece, I instead lose my own piece. How much fun is this to play? (Maybe not so much...)
This game is sort of a more complex version of Clobber: pieces are arranged on a checkerboard, and they "clobber" pieces near them---except that there are 3 different types of pieces and they move in different ways. Pawns move one space in any direction (including diagonal), drones may move up to two spaces (but only horizontally and vertically) and queens may move exactly as queens in Chess. Pieces may not jump over other pieces. Okay, maybe it is more like Chess than Clobber...
Nevertheless, the goal is to take opponents' pieces. 3 points are given for a queen, 2 for each drone and 1 for each pawn captured. The game ends when a player no longer controls any pieces. The twist, however, is that when you capture an opponents' piece, they now take control of your piece on the board. This occurs because each player "owns" two opposite quadrants of the board: they may move any pieces in their quadrant. Capturing an opponents' piece means moving into an opponents' section and surrendering the piece you just owned.
Martian Chess is a really fun game that forces you to think on your toes. Just about when I seemed to be coming up with a strong strategy, Ernie pulled a new trick on me and had me completely second-guessing myself. I would really like to play this game in class, but, alas, I don't think I have enough Icehouse pieces!
Let's use this wacky ownership in a variant of Clobber: Reverse Clobber. Now, when I clobber an opposing piece, I instead lose my own piece. How much fun is this to play? (Maybe not so much...)
Tuesday, August 31, 2010
Mentionables
A few nice things to note as we head into the weekend!
First, wouldn't it be nice to have all your board games played on an electronic surface? Apparently the iPad might be able to handle this task! I'm not sure whether this is entirely feasible for a few reasons, but it might be good for enforcing playing by the rules for many games.
Also, it's nice to see some engineering sites mentioning board games. In this Ars Technica article, the game Drakon is reviewed. I am a bit easily influenced; perhaps I should add this game to my collection! I wonder if they would ever review a bad game...
My papers didn't make it into FUN 2010, and it was so close to my wedding I couldn't otherwise attend. Sad! I wish I'd been around to hear about these papers!
On a very happy note, I am overjoyed by my students attitude in our games class. This week we learned Clobber, and I encouraged my students to try to work out a strategy based on symmetry. Every student was engaged trying to play this game well! Also, even though we are only in the second week, students have already begun selecting games for their final project. Very exciting!
First, wouldn't it be nice to have all your board games played on an electronic surface? Apparently the iPad might be able to handle this task! I'm not sure whether this is entirely feasible for a few reasons, but it might be good for enforcing playing by the rules for many games.
Also, it's nice to see some engineering sites mentioning board games. In this Ars Technica article, the game Drakon is reviewed. I am a bit easily influenced; perhaps I should add this game to my collection! I wonder if they would ever review a bad game...
My papers didn't make it into FUN 2010, and it was so close to my wedding I couldn't otherwise attend. Sad! I wish I'd been around to hear about these papers!
On a very happy note, I am overjoyed by my students attitude in our games class. This week we learned Clobber, and I encouraged my students to try to work out a strategy based on symmetry. Every student was engaged trying to play this game well! Also, even though we are only in the second week, students have already begun selecting games for their final project. Very exciting!
Friday, August 27, 2010
Writing Game Rules
I often can't stop thinking about board games that are not completely combinatorial (they have some randomness or hidden information, etc). Often this happens in games where I'm trying to figure out exactly how the rules work.
After thinking about programming all day, it's not difficult to pick apart game rules and consider potential ambiguities. I'm teaching my algorithms class to be sure that any algorithm they write by hand be precise, and I often wish game rules were spelled out with a similar notation.
(Example using a property-type board game.)
Using the standard notation for Combinatorial Games, this is not an issue; all rules for play are considered the same! All the necessary information is which moves are available to each player.
Sometimes, the legal moves are not always obvious in board games, however. I've been playing Set Cubed with other members of our department, and this is a very fun game. The basic premise is a mix of Set and Scrabble, where players score points by creating new Sets each turn, filling up a 2 x 2 grid. (A 'Set' is a triple of pieces where, for each property of the pieces, either all three have the same value or all three have different values. (Each property can have one of three values.)) The rules for this game are available here, including many nice pictures.
In the game, an often-occurring move is to play a piece that creates a set in one direction (horizontally or vertically), but doesn't in another, even though it lines up with those pieces. This is perfectly legal, which is clear according to the rules. On a turn, a player may play up to three dice on the board. What is not clear is whether those dice must be played one at a time, pausing in-between to determine the legality of that play alone, or whether a first die may be followed immediately by a second so that the trio form a set, even if the first doesn't create any.
As it turns out, you have to allow this in order to play in other directions besides a straight line, but later on it seems awkward to play a piece that creates one or more non-Set groups of three, then immediately cover that up with a second piece. It could be that this is not legal!
Since it looks like my lunch group will be playing this game a lot, I emailed the makers of Set for a clarification. They responded very quickly and told me that this is legal, as examples were shown in the online tutorial.
Either way, I'd like to try playing under both rules! This is a very nice game that employs a nice amount of randomness without removing all the strategy involved. Also, it is not trivial each turn to see where your available moves are, as it is not trivial to see all set combinations. It also removes the speed aspect of Set, as players take distinct turns instead of calling out the Sets they see.
After thinking about programming all day, it's not difficult to pick apart game rules and consider potential ambiguities. I'm teaching my algorithms class to be sure that any algorithm they write by hand be precise, and I often wish game rules were spelled out with a similar notation.
(Example using a property-type board game.)
Step 1: Set the board up according to the section Setup.
Step 2: Let p be 1.
Step 3: Player p rolls the two dice, then advances their piece clockwise around the board.
Step 4: Let s be the square containing their piece. If s contains an unowned property, continue to step ?.
Step 5: Let h be the number of houses on s and q be the player who owns the property at square s. p owes q $X where $X is the amount listed in the h-th entry of property s. Go to step 7.
Step 6: p may purchase the property... ...
Step 7: Increment p. If p is greater than the number of players, let p = 1. Continue to step 3.
Using the standard notation for Combinatorial Games, this is not an issue; all rules for play are considered the same! All the necessary information is which moves are available to each player.
Sometimes, the legal moves are not always obvious in board games, however. I've been playing Set Cubed with other members of our department, and this is a very fun game. The basic premise is a mix of Set and Scrabble, where players score points by creating new Sets each turn, filling up a 2 x 2 grid. (A 'Set' is a triple of pieces where, for each property of the pieces, either all three have the same value or all three have different values. (Each property can have one of three values.)) The rules for this game are available here, including many nice pictures.
In the game, an often-occurring move is to play a piece that creates a set in one direction (horizontally or vertically), but doesn't in another, even though it lines up with those pieces. This is perfectly legal, which is clear according to the rules. On a turn, a player may play up to three dice on the board. What is not clear is whether those dice must be played one at a time, pausing in-between to determine the legality of that play alone, or whether a first die may be followed immediately by a second so that the trio form a set, even if the first doesn't create any.
As it turns out, you have to allow this in order to play in other directions besides a straight line, but later on it seems awkward to play a piece that creates one or more non-Set groups of three, then immediately cover that up with a second piece. It could be that this is not legal!
Since it looks like my lunch group will be playing this game a lot, I emailed the makers of Set for a clarification. They responded very quickly and told me that this is legal, as examples were shown in the online tutorial.
Either way, I'd like to try playing under both rules! This is a very nice game that employs a nice amount of randomness without removing all the strategy involved. Also, it is not trivial each turn to see where your available moves are, as it is not trivial to see all set combinations. It also removes the speed aspect of Set, as players take distinct turns instead of calling out the Sets they see.
Tuesday, August 24, 2010
Game Description: A Collatz Game
I just learned about the Collatz Conjecture last year, and it is a wonderful problem to play around with in semi-free time.
So much fun, in fact, that it was time to make a game out of it. The plan is to move from one number in a Collatz sequence to another "neighboring" integer, and be the player to reach the number 1. Obviously, the game gets boring if players always have to choose the next number in the sequence, so we let people go "backwards".
As a quick review, the Collatz Conjecture states that the following process will terminate, starting with any positive number. First, check if the number is 1. If so, stop. Otherwise, check the parity of the number. If it's even, divide it by two and start over. If it's odd, instead multiply it by 3, then add 1 and start over. It's not known whether this is actually true for all numbers, but it's been tested up through something astronomical (and continues to be tested for higher numbers).
For the game, we need to be a bit less strict about what the next number is. Instead of always going "forward" we will allow some backwards moves. So, if on your turn the current number is n, you get one of the following options:
Also, to prevent boring back-and-forth strategies, you are not allowed to just reverse the last player's move. Thus, each turn, there are between 1 and 3 possible moves. For many cases, your next move is decided for you.
Last weekend, my brand-new aide, Ernie, and I gave this a shot, and we quickly realized we needed restrictions on when a player could make either of the moves that increase the current value. After a few rules changes, we both realized that players should be forced to move downwards if possible.
On our first try with these rules, played the following game: 11, 34, 17, 52, 26, 13, 4, 1 (a win for the first player!). In this case, only the first move and the last move actually were decision-making points. Curious, we looked at what happened making the other move from 11:
11 -> 22 -> 7 -> 2 -> 1 (second player wins) which didn't have any other decisions available.
This seems like a boring game, until we tried starting at 10: (D's indicate places where decisions were made)
10 D-> 3 -> 6 D->12 D->37 D->74 D->148 ->49 ->16 D->8 ->4 D->1
Then 16:
16 D->5 -> 10 -> 3 ->6 D->12 D->24 D->48 D->145 D->436 ->218 -> 109 -> 36 -> 18 -> 9 -> 28 ->14->7->2->1
Some of the rules need to be ironed out here to prevent the number from getting too big too quickly. We wound up adding a stipulation that the number can't be doubled three times in a row helping enforce that the number will drop at some point. It could be that other additions help out, without completely limiting player choices.
As it is, this is a nice impartial game to play that requires only a pen and paper and some basic arithmetic. Also, it's likely okay to ignore determining the computational complexity when it's still not known whether all Collatz sequences terminate. Give it a try, and let me know which rules worked for you!
So much fun, in fact, that it was time to make a game out of it. The plan is to move from one number in a Collatz sequence to another "neighboring" integer, and be the player to reach the number 1. Obviously, the game gets boring if players always have to choose the next number in the sequence, so we let people go "backwards".
As a quick review, the Collatz Conjecture states that the following process will terminate, starting with any positive number. First, check if the number is 1. If so, stop. Otherwise, check the parity of the number. If it's even, divide it by two and start over. If it's odd, instead multiply it by 3, then add 1 and start over. It's not known whether this is actually true for all numbers, but it's been tested up through something astronomical (and continues to be tested for higher numbers).
For the game, we need to be a bit less strict about what the next number is. Instead of always going "forward" we will allow some backwards moves. So, if on your turn the current number is n, you get one of the following options:
- Move to 2n
- Move to 3n + 1
- Move to n/2, if n is even
- Move to (n-1)/3, if n-1 is divisible by 3
Also, to prevent boring back-and-forth strategies, you are not allowed to just reverse the last player's move. Thus, each turn, there are between 1 and 3 possible moves. For many cases, your next move is decided for you.
Last weekend, my brand-new aide, Ernie, and I gave this a shot, and we quickly realized we needed restrictions on when a player could make either of the moves that increase the current value. After a few rules changes, we both realized that players should be forced to move downwards if possible.
On our first try with these rules, played the following game: 11, 34, 17, 52, 26, 13, 4, 1 (a win for the first player!). In this case, only the first move and the last move actually were decision-making points. Curious, we looked at what happened making the other move from 11:
11 -> 22 -> 7 -> 2 -> 1 (second player wins) which didn't have any other decisions available.
This seems like a boring game, until we tried starting at 10: (D's indicate places where decisions were made)
10 D-> 3 -> 6 D->12 D->37 D->74 D->148 ->49 ->16 D->8 ->4 D->1
Then 16:
16 D->5 -> 10 -> 3 ->6 D->12 D->24 D->48 D->145 D->436 ->218 -> 109 -> 36 -> 18 -> 9 -> 28 ->14->7->2->1
Some of the rules need to be ironed out here to prevent the number from getting too big too quickly. We wound up adding a stipulation that the number can't be doubled three times in a row helping enforce that the number will drop at some point. It could be that other additions help out, without completely limiting player choices.
As it is, this is a nice impartial game to play that requires only a pen and paper and some basic arithmetic. Also, it's likely okay to ignore determining the computational complexity when it's still not known whether all Collatz sequences terminate. Give it a try, and let me know which rules worked for you!
Monday, August 16, 2010
Kicking Off: Fall 2010
I hoped to write a smattering of blog posts this summer, but then a lot of things happened this summer and then I only posted once. Some of these affected me very personally, for example:
Luckily, Wittenberg's fall semester begins early and with that comes a return to a regular schedule. I will plan on two posts per week, and this time I will have some help preparing them. Beyond this, there are other benefits for this semester:
Happy (Academic) Fall!
- I drove back-and-forth across my time zone twice.
- I learned that paying extra for first-class plane seats does not give you more leg room.
- Vinay Deolalikar tried to show that solving Atropos is not in P. There is some disagreement about how close he came (he continues working on this) but it's very nice that everyone cares so much!
- I miss winter.
- I am now happily married.
Luckily, Wittenberg's fall semester begins early and with that comes a return to a regular schedule. I will plan on two posts per week, and this time I will have some help preparing them. Beyond this, there are other benefits for this semester:
- I'm teaching a CGT course! I look forward to chatting about that.
- I will refrain from polluting this blog with mentions of college football, despite the up-and-coming season. Instead, I just started a separate blog dedicated to my automated ranking.
- I have some help prepping things this semester! Hooray!
Happy (Academic) Fall!
Monday, June 28, 2010
Origins 2010
Wooo!
I am back home in Springfield, Ohio, for the first time in a month. The vast majority of the trip was dedicated to getting married, but the tail end was a trip to the Origins Game Fair in Columbus, OH.
Unlike GenCon last year, this year I prepared by registering for a bunch of events and got to play a bunch of games. Many games don't quite fall under the "combinatorial" heading, due to their inclusion of random elements or imperfect information, but they all have elements of looking ahead necessary for playing games well. Sometimes these elements can be modified to either publicize or derandomize information. Othertimes, other combinatorial aspects can be extracted into their own game. In any case, playing any board game can always be a useful exercise for gamesters!
Okay, I'm going to try to recall the games I played. If I forget any and add them later, I'll add a bolded note and a comment. Unfortunately, I don't have pictures now; when I take the initiative to put up all my pictures, I'll add links to the origins pics.
I missed the first few days of the convention and showed up on Friday morning. That morning, I was lured into the Looney Labs room by a bunch of people playing World War 5. I got in on the next game and pulled off a sneaky win with the luck of the dice. This continued a pattern of other games using Treehouse pieces, starting with Volcano, an actual combinatorial game. After this, I sat down and was introduced to Martian Coasters, then Treehouse, the original game for the pieces, then Martian Chess (another combinatorial game!) and finally Pikemen (combinatorial again!). Pikemen was especially fun, since we played on a three-player chess board someone there had!
I stayed extra long at the Looney Lab site, and had to race to my D&D appointment with some other folks from Wittenberg. After that fun excursion, I played Age of Conan, which was a bit disappointing. Saturday started off with my first game of Arkham Horror, which is perhaps the first time I've ever played a co-operative board game. Here, all the players work together to complete a task (sealing away an ancient, Lovecraftian demon) while the game mechanics work to try to unleash the monster into the world. Definitely not combinatorial, but definitely very fun.
Arkham Horror was followed by Robo Rally, which I had played once before. This is a great board game that really uses some programming aspects. In this game, players move robots around a grid by choosing individual move or turn cards from a dealt hand. Those cards are placed face down in an order to be executed, then all players' first cards are revealed and executed, followed by the second, and so on. My first sequence of moves was miscalculated and landed me in a pit obstacle on the grid. Oops! While at Origins, I tried to find a copy, but didn't find one reasonably priced. This is by far one of my favorite games from the weekend.
Heroscape came next, a strategical battle game with very beautiful pieces and an easy-to-understand hexagonal layout. I generally swoon for hexagons, but I didn't expect I would enjoy playing this game as much as I did.
Next, I headed over to the Mayfair room, expecting to get roped into some form of Settlers---I've never played! Instead, I got in on a demo of a not-yet-produced gem, slated to be named Lords of Vegas. This game simulates casino bosses building up the Las Vegas strip. As the rules were described, I thought it was going to be overly complex, but then everything came together as we played. We were easily the loudest table in the whole Mayfair room that night, and the game came down to a roll of dice at the last moment. This was tons of fun, and actually one of those times where some simple probability analysis can really help out.
My last scheduled event was Runewars on Sunday morning. This game did not inspire me (though there were hexagons) as much as others, mostly because there were a few too many things going on all at the same time, and just too many rules to keep track of. Some board elements didn't seem to interact in any way, and I lost interest pretty quickly. I did make up for this by spending the afternoon browsing the dealer hall and demoing a few games that caught my eye. I spent some time at the Out of the Box booth, meeting some people there and trying out some other games. I also met the creator of WEGS and learned the basics for that role-playing system. I made sure to get a set of Treehouse pieces to play around with later.
Did anyone find any great combinatorial (or combinatorialish) games at Origins? If so, I'd love to hear about them!
I am back home in Springfield, Ohio, for the first time in a month. The vast majority of the trip was dedicated to getting married, but the tail end was a trip to the Origins Game Fair in Columbus, OH.
Unlike GenCon last year, this year I prepared by registering for a bunch of events and got to play a bunch of games. Many games don't quite fall under the "combinatorial" heading, due to their inclusion of random elements or imperfect information, but they all have elements of looking ahead necessary for playing games well. Sometimes these elements can be modified to either publicize or derandomize information. Othertimes, other combinatorial aspects can be extracted into their own game. In any case, playing any board game can always be a useful exercise for gamesters!
Okay, I'm going to try to recall the games I played. If I forget any and add them later, I'll add a bolded note and a comment. Unfortunately, I don't have pictures now; when I take the initiative to put up all my pictures, I'll add links to the origins pics.
I missed the first few days of the convention and showed up on Friday morning. That morning, I was lured into the Looney Labs room by a bunch of people playing World War 5. I got in on the next game and pulled off a sneaky win with the luck of the dice. This continued a pattern of other games using Treehouse pieces, starting with Volcano, an actual combinatorial game. After this, I sat down and was introduced to Martian Coasters, then Treehouse, the original game for the pieces, then Martian Chess (another combinatorial game!) and finally Pikemen (combinatorial again!). Pikemen was especially fun, since we played on a three-player chess board someone there had!
I stayed extra long at the Looney Lab site, and had to race to my D&D appointment with some other folks from Wittenberg. After that fun excursion, I played Age of Conan, which was a bit disappointing. Saturday started off with my first game of Arkham Horror, which is perhaps the first time I've ever played a co-operative board game. Here, all the players work together to complete a task (sealing away an ancient, Lovecraftian demon) while the game mechanics work to try to unleash the monster into the world. Definitely not combinatorial, but definitely very fun.
Arkham Horror was followed by Robo Rally, which I had played once before. This is a great board game that really uses some programming aspects. In this game, players move robots around a grid by choosing individual move or turn cards from a dealt hand. Those cards are placed face down in an order to be executed, then all players' first cards are revealed and executed, followed by the second, and so on. My first sequence of moves was miscalculated and landed me in a pit obstacle on the grid. Oops! While at Origins, I tried to find a copy, but didn't find one reasonably priced. This is by far one of my favorite games from the weekend.
Heroscape came next, a strategical battle game with very beautiful pieces and an easy-to-understand hexagonal layout. I generally swoon for hexagons, but I didn't expect I would enjoy playing this game as much as I did.
Next, I headed over to the Mayfair room, expecting to get roped into some form of Settlers---I've never played! Instead, I got in on a demo of a not-yet-produced gem, slated to be named Lords of Vegas. This game simulates casino bosses building up the Las Vegas strip. As the rules were described, I thought it was going to be overly complex, but then everything came together as we played. We were easily the loudest table in the whole Mayfair room that night, and the game came down to a roll of dice at the last moment. This was tons of fun, and actually one of those times where some simple probability analysis can really help out.
My last scheduled event was Runewars on Sunday morning. This game did not inspire me (though there were hexagons) as much as others, mostly because there were a few too many things going on all at the same time, and just too many rules to keep track of. Some board elements didn't seem to interact in any way, and I lost interest pretty quickly. I did make up for this by spending the afternoon browsing the dealer hall and demoing a few games that caught my eye. I spent some time at the Out of the Box booth, meeting some people there and trying out some other games. I also met the creator of WEGS and learned the basics for that role-playing system. I made sure to get a set of Treehouse pieces to play around with later.
Did anyone find any great combinatorial (or combinatorialish) games at Origins? If so, I'd love to hear about them!
Tuesday, May 18, 2010
In-Depth look at Chess (link)
Ken Regan guest posts about solving chess here:
http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/
Enjoy! :)
http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/
Enjoy! :)
Thursday, May 6, 2010
Implementing a Game Class (type, not course)
In the fall of 2009, I taught a software engineering course. As our on-going project for the semester, I had students code up a bunch of different combinatorial games. One of the major goals of the course is to teach students the benefits of employing object-oriented design. As I tack on new aspects to the project each week, code that follows more OO-principles will be easier to upgrade.
Together, this begs the question: how should a game be implemented? More generally, what should be common to the interface for all games? What methods should a Game class contain?
Looking at this from a pure mathematical perspective, there should be only two methods: getLeftChildren and getRightChildren. If those return collections of game objects, then you're done. Everything you really need to know about a game is contained there. Other convenience methods would probably exist, such as leftHasMoves and rightHasMoves, etc., but these two are sufficient.
In the practical view, however, this is a problem. Some games have a very limited number of possible moves from any single state, but other games, such as Phutball, can have an exponential number of children. Yikes! You would never want to generate that collection for big-enough games!
Instead, consider replacing getLeftChildren and getRightChildren with the methods isLeftChild and isRightChild that return whether a given game is a child of the subject game. Could this work as a proper interface?
One obvious advantage is that we do not have to find and return all possible child states. One disadvantage, however, is that for many games, returning that set might be easier to code up than determining the validity of a child. The easiest "cop out" of this argument is to generate those children, then test whether the passed child is an element of those children. This doesn't solve the efficiency problem, however.
Is that problem solvable, though? Again, using Phutball as an example, it is NP-hard to determine whether a player can win on a given turn. Is it also as difficult to determine whether a child of a game exists? It seems trivial that this must also be NP-hard; use a winning position of Phutball as the potential child and ask the same question.
This argument does not immediately prove the hardness, as in Phutball there are potentially an exponential number of final board positions that result in a win. We cannot just test whether the ball ends in the end-zone as our final child state, but must also include whether any prior-existing players also remain on the board.
What is the complexity of this problem? How hard is it to tell whether a game is a child of another game?
This ends the regular posts for the semester! I will make a few posts over the summer (especially if I get a sexier phone) and will return to a regular schedule in the fall. I apologize in advance if those posts are very teaching related...
Thank you to everyone who has chimed in, both via email and in comments! I got a lot of vital advice, including material I may be able to include in teaching next semester. I'll still be listening all summer long! :)
Together, this begs the question: how should a game be implemented? More generally, what should be common to the interface for all games? What methods should a Game class contain?
Looking at this from a pure mathematical perspective, there should be only two methods: getLeftChildren and getRightChildren. If those return collections of game objects, then you're done. Everything you really need to know about a game is contained there. Other convenience methods would probably exist, such as leftHasMoves and rightHasMoves, etc., but these two are sufficient.
In the practical view, however, this is a problem. Some games have a very limited number of possible moves from any single state, but other games, such as Phutball, can have an exponential number of children. Yikes! You would never want to generate that collection for big-enough games!
Instead, consider replacing getLeftChildren and getRightChildren with the methods isLeftChild and isRightChild that return whether a given game is a child of the subject game. Could this work as a proper interface?
One obvious advantage is that we do not have to find and return all possible child states. One disadvantage, however, is that for many games, returning that set might be easier to code up than determining the validity of a child. The easiest "cop out" of this argument is to generate those children, then test whether the passed child is an element of those children. This doesn't solve the efficiency problem, however.
Is that problem solvable, though? Again, using Phutball as an example, it is NP-hard to determine whether a player can win on a given turn. Is it also as difficult to determine whether a child of a game exists? It seems trivial that this must also be NP-hard; use a winning position of Phutball as the potential child and ask the same question.
This argument does not immediately prove the hardness, as in Phutball there are potentially an exponential number of final board positions that result in a win. We cannot just test whether the ball ends in the end-zone as our final child state, but must also include whether any prior-existing players also remain on the board.
What is the complexity of this problem? How hard is it to tell whether a game is a child of another game?
This ends the regular posts for the semester! I will make a few posts over the summer (especially if I get a sexier phone) and will return to a regular schedule in the fall. I apologize in advance if those posts are very teaching related...
Thank you to everyone who has chimed in, both via email and in comments! I got a lot of vital advice, including material I may be able to include in teaching next semester. I'll still be listening all summer long! :)
Tuesday, May 4, 2010
Final Post of Semester: Thursday (not today)
I have been unexpectedly swamped today. I do not want a haphazard post today, so I'm pushing it back until Thursday.
Sorry!
Sorry!
Monday, May 3, 2010
Post with Games on Goedel's Lost Letter
Goedel's Lost Letter has a post with some combinatorial games.
I should start adding more pictures...
I should start adding more pictures...
Friday, April 30, 2010
Game Description: Fjords
First, a few administrative notes. Wittenberg's classes end on Wednesday, so this will be the last Friday post of the semester, and Tuesday will end the regular schedule. I have a list of potential topics on my whiteboard for Tuesday, but if there's something you'd like me to comment on, please let me know.
This summer I will be away from Internet access a great deal and I will not try to keep up any sort of scheduled postings. I'm sure there will be some posts, but not with any regularity.
Thanks also to everyone who has posted or emailed me about content this year! One of these people was Paul Ottaway, who suggested I try playing the game Fjords. He mentioned that this is half non-combinatorial and half combinatorial.
Earlier this month, I got a copy for my birthday and I've already played a bunch of games! It is just as Paul mentioned: the first stage (which actually takes a long time) uses a lot of random elements. The second stage (this goes pretty quick) is a pure combinatorial game. It is not, however, a game that I am aware of. Perhaps it exists and has already been studied! Perhaps you will have heard of it and can let me know! :)
The first stage of the game consists of the players "exploring" the land they will settle. Players flip over hexagons with field, mountain and sea patterns, fitting them together to form the landmass. The result of this is a hexagonal grid graph with some vertices missing (tiles were not placed or do not include any field area) or edges missing (field tiles with mountains or the sea between them are not adjacent). While placing these tiles, a player may elect to place one of their few farms on the most recent tile (it's stuck there for the rest of the game). Thus, the hexagonal graph has some of its vertices labelled either Red or bLue before the second stage.
The second stage of the game is then very simple: a players' turn consists of labelling a vertex. That vertex must be both uncolored and adjacent to a vertex already of that player's color. When one player cannot color a vertex, they lose. In the actual game, these newly colored tiles represent fields spreading from your farms. Also in the actual game, if you both get the same number of farms, it is a tie (instead of a second-player win).
The second half of this game seems very basic, however. I would be astonished if it didn't have a name in combinatorial games. Even if played on any (planar?) graph instead of only a subgraph of a hexagonal grid, this must be studied somewhere.
In any case, I highly suggest giving Fjords a try! It's an excellent game for two people, but do not believe the 30 minute time requirement the box suggests (they want you to play the whole thing three times). All my games take around 30-45 minutes each, meaning a WHOLE game would take around 2 hours!
This summer I will be away from Internet access a great deal and I will not try to keep up any sort of scheduled postings. I'm sure there will be some posts, but not with any regularity.
Thanks also to everyone who has posted or emailed me about content this year! One of these people was Paul Ottaway, who suggested I try playing the game Fjords. He mentioned that this is half non-combinatorial and half combinatorial.
Earlier this month, I got a copy for my birthday and I've already played a bunch of games! It is just as Paul mentioned: the first stage (which actually takes a long time) uses a lot of random elements. The second stage (this goes pretty quick) is a pure combinatorial game. It is not, however, a game that I am aware of. Perhaps it exists and has already been studied! Perhaps you will have heard of it and can let me know! :)
The first stage of the game consists of the players "exploring" the land they will settle. Players flip over hexagons with field, mountain and sea patterns, fitting them together to form the landmass. The result of this is a hexagonal grid graph with some vertices missing (tiles were not placed or do not include any field area) or edges missing (field tiles with mountains or the sea between them are not adjacent). While placing these tiles, a player may elect to place one of their few farms on the most recent tile (it's stuck there for the rest of the game). Thus, the hexagonal graph has some of its vertices labelled either Red or bLue before the second stage.
The second stage of the game is then very simple: a players' turn consists of labelling a vertex. That vertex must be both uncolored and adjacent to a vertex already of that player's color. When one player cannot color a vertex, they lose. In the actual game, these newly colored tiles represent fields spreading from your farms. Also in the actual game, if you both get the same number of farms, it is a tie (instead of a second-player win).
The second half of this game seems very basic, however. I would be astonished if it didn't have a name in combinatorial games. Even if played on any (planar?) graph instead of only a subgraph of a hexagonal grid, this must be studied somewhere.
In any case, I highly suggest giving Fjords a try! It's an excellent game for two people, but do not believe the 30 minute time requirement the box suggests (they want you to play the whole thing three times). All my games take around 30-45 minutes each, meaning a WHOLE game would take around 2 hours!
Tuesday, April 27, 2010
Mall Madness
This weekend I did something I thought I would never do: I played Mall Madness.
Mall Madness is a board game where the players are shoppers, trying to visit different stores and to purchase something from each of them, then be the first to leave the mall. The game has been in production for over 20 years, and is targeted to middle-schoolish-aged girls. Since my sister didn't have a set, I never played. (I did play Pretty Pretty Princess, but that was for a babysitting gig.)
It turns out this game is not just about a shopping spree, but actually about finding the best order to visit different locations. Each of the different shops has an item you want to buy at different prices from the other stores. You could choose a path to purchase all the cheapest items, but those are not all located together. In addition, you don't begin with enough cash to buy everything and must periodically stop by the ATM to withdraw more money. I actually found myself not having enough time between turns to try to figure out the next two or three stops I should make. "I could go buy a 'Compact Disc' at the music store for pretty cheap, but the gift store and department store are a good deal, and they're on the other side of the mall..." I don't know if this is standard rules, but we didn't have to visit all the stores, just a subset of them of some given size.
Additionally, some stores run sales so that the price of their item is even cheaper. These change, so you have to make decisions about whether to try to make it across the mall for a given sale or just to ignore it and hope it changes soon. Thus, the more flexible your plan is, the better.
Unfortunately, this also means it doesn't pay off very much to actually plan ahead. There are a lot of widely varying random factors: you can move between 3 and 12 spaces each turn (or something like that), sometimes the stores have lines that prevent you from buying things, sometimes the stores charge more than they advertised (isn't that illegal?) and sometimes they have secret sales. I'm not sure if you can normally buy things even half the time; these other scenarios kept coming up! (The randomness in the game is controlled by an electronic component, so the probabilities aren't obvious.) Even when you went to the bank, you received a random amount of money somewhere between $50 and $100. (The phrase "Daddy doesn't love you as much as he loves me!" came up a bunch whenever someone received $50.)
Just to really shake things up, at any point the game could have players "warp" across the board to visit the ice cream stand or other random locations.
I'm not entirely sure what lessons this game was teaching young girls. There were certainly some sexist elements, and having to make multiple trips to the ATM in one shopping adventure may be a bit dangerous of a plan. Still, even when you try to look ahead and figure out the next two stores you should visit, you have to do a bit of calculation. Any motivation to get kids to do that is good.
So, Mall Madness, I forgive you for thinking you are a completely ridiculous game since I was a kid and agree that you do have some good qualities.
Now please don't send me to the arcade again!
Mall Madness is a board game where the players are shoppers, trying to visit different stores and to purchase something from each of them, then be the first to leave the mall. The game has been in production for over 20 years, and is targeted to middle-schoolish-aged girls. Since my sister didn't have a set, I never played. (I did play Pretty Pretty Princess, but that was for a babysitting gig.)
It turns out this game is not just about a shopping spree, but actually about finding the best order to visit different locations. Each of the different shops has an item you want to buy at different prices from the other stores. You could choose a path to purchase all the cheapest items, but those are not all located together. In addition, you don't begin with enough cash to buy everything and must periodically stop by the ATM to withdraw more money. I actually found myself not having enough time between turns to try to figure out the next two or three stops I should make. "I could go buy a 'Compact Disc' at the music store for pretty cheap, but the gift store and department store are a good deal, and they're on the other side of the mall..." I don't know if this is standard rules, but we didn't have to visit all the stores, just a subset of them of some given size.
Additionally, some stores run sales so that the price of their item is even cheaper. These change, so you have to make decisions about whether to try to make it across the mall for a given sale or just to ignore it and hope it changes soon. Thus, the more flexible your plan is, the better.
Unfortunately, this also means it doesn't pay off very much to actually plan ahead. There are a lot of widely varying random factors: you can move between 3 and 12 spaces each turn (or something like that), sometimes the stores have lines that prevent you from buying things, sometimes the stores charge more than they advertised (isn't that illegal?) and sometimes they have secret sales. I'm not sure if you can normally buy things even half the time; these other scenarios kept coming up! (The randomness in the game is controlled by an electronic component, so the probabilities aren't obvious.) Even when you went to the bank, you received a random amount of money somewhere between $50 and $100. (The phrase "Daddy doesn't love you as much as he loves me!" came up a bunch whenever someone received $50.)
Just to really shake things up, at any point the game could have players "warp" across the board to visit the ice cream stand or other random locations.
I'm not entirely sure what lessons this game was teaching young girls. There were certainly some sexist elements, and having to make multiple trips to the ATM in one shopping adventure may be a bit dangerous of a plan. Still, even when you try to look ahead and figure out the next two stores you should visit, you have to do a bit of calculation. Any motivation to get kids to do that is good.
So, Mall Madness, I forgive you for thinking you are a completely ridiculous game since I was a kid and agree that you do have some good qualities.
Now please don't send me to the arcade again!
Friday, April 23, 2010
Combinatorial Games... Art?
I'm more than willing to grab on to any internet sensation that has fleeting relevance to combinatorial games. This post is proof of that. :)
Roger Ebert, a famous film critic, has recently sounded off on his webpage of some non-movie related items. Lately, his post on how video games are not art has stirred up a lot of frustration. Naturally, anything on the Internet seems to get people's blood boiling, and I only happen to know of this because I'm addicted to a few webcomics. As it is, I'm not very concerned about whether video games are considered art today. I barely understand what is considered art in the current sense, but figure that someday someone will ask whether some new-fangled form of entertainment is as artistic as the "classic" art of video games. That just seems to be the pattern. I've read some cool articles refuting Ebert's column, mostly because I thought they would be entertaining (they were) but the points don't resonate with me all that well, because I have a hard time understanding "what is art"?
But, then, I thought: What about board games? What about combinatorial games? Can this realm be considered art?
I don't know, but here are a couple of thoughts.
Yes-side: some board games have very artistic components. I have some beautiful boards for games that light up my eyes every time I open them up. Dragon Strike came with four sweet boards for adventures in different locations which are very nice. Alternatively, Hero Quest has a less impressive board by itself, but the design allows for a large number of very different scenarios that Dragon Strike can't match. Perhaps there is art in this configurable simplicity? Also, I have seen chess sets of varying levels of awesome figures, created either with expensive materials or just fashioned to look like the Looney Tunes characters.
Counter-argument: Board games may have nice pieces, but that does not necessary qualify the game itself as a piece of "artwork".
Another Yes-side: There is real elegance in the rules of games. Some games can take a simple, small amount of rules and be something very complex and beautiful. Very hard to understand, yet able to draw appreciation and analysis from onlookers (players). We can appreciate a game such as Kayles, not because it is a comment on society, but because it can evoke emotions in us.
Counter-argument: similar reasoning can be made for anything. We can appreciate nearly anything, but not everything is art. I can appreciate the way you do your job, but that does not make it art.
No-side: combinatorial games are a realm of scientific study. This is art in the same way that Chemistry is art. No one actually plays toppling dominoes as an artistic experience, so it is not a piece of art. A game is also not designed so that the study of it is an emotional experience.
Counter-argument: I don't really have one. Someone help me out! :)
In the end, though, I expect that if video games are considered art, then so must board games. As for straight-up combinatorial games, I'm not sure. Where do we draw the line between the idea and the implementation as far as artwork goes?
Roger Ebert, a famous film critic, has recently sounded off on his webpage of some non-movie related items. Lately, his post on how video games are not art has stirred up a lot of frustration. Naturally, anything on the Internet seems to get people's blood boiling, and I only happen to know of this because I'm addicted to a few webcomics. As it is, I'm not very concerned about whether video games are considered art today. I barely understand what is considered art in the current sense, but figure that someday someone will ask whether some new-fangled form of entertainment is as artistic as the "classic" art of video games. That just seems to be the pattern. I've read some cool articles refuting Ebert's column, mostly because I thought they would be entertaining (they were) but the points don't resonate with me all that well, because I have a hard time understanding "what is art"?
But, then, I thought: What about board games? What about combinatorial games? Can this realm be considered art?
I don't know, but here are a couple of thoughts.
Yes-side: some board games have very artistic components. I have some beautiful boards for games that light up my eyes every time I open them up. Dragon Strike came with four sweet boards for adventures in different locations which are very nice. Alternatively, Hero Quest has a less impressive board by itself, but the design allows for a large number of very different scenarios that Dragon Strike can't match. Perhaps there is art in this configurable simplicity? Also, I have seen chess sets of varying levels of awesome figures, created either with expensive materials or just fashioned to look like the Looney Tunes characters.
Counter-argument: Board games may have nice pieces, but that does not necessary qualify the game itself as a piece of "artwork".
Another Yes-side: There is real elegance in the rules of games. Some games can take a simple, small amount of rules and be something very complex and beautiful. Very hard to understand, yet able to draw appreciation and analysis from onlookers (players). We can appreciate a game such as Kayles, not because it is a comment on society, but because it can evoke emotions in us.
Counter-argument: similar reasoning can be made for anything. We can appreciate nearly anything, but not everything is art. I can appreciate the way you do your job, but that does not make it art.
No-side: combinatorial games are a realm of scientific study. This is art in the same way that Chemistry is art. No one actually plays toppling dominoes as an artistic experience, so it is not a piece of art. A game is also not designed so that the study of it is an emotional experience.
Counter-argument: I don't really have one. Someone help me out! :)
In the end, though, I expect that if video games are considered art, then so must board games. As for straight-up combinatorial games, I'm not sure. Where do we draw the line between the idea and the implementation as far as artwork goes?
Tuesday, April 20, 2010
Candy Nim
On Friday, I mentioned Michael Albert's "Candy Nim" as a way to entertain yourself when you're losing a game of Nim.
The idea works as follows: you are in a losing Nim position (and the other player seems to know "the trick" to keep on winning). You decide to come up with a secondary goal: try to eat (take) as many of the remaining objects (pieces of candy) as possible. Michael proves that in this case, there is a way to eat at least half of the remaining objects!
Consider the case where there are two piles of objects, both with the same number (they have to be the same, otherwise you're not in a losing position). In this case, no matter how many you eat, the other player will take the same amount, and you'll eat exactly half the candy.
In some cases, there is a better "strategy". For example, if there are three piles, and one of them has size 1, then the other two must look like 2k and 2k + 1 for some k. Now, there is a way to net a 3-to-1 advantage in this situation: take 3 from the pile with 2k+1.
Then our piles go from: 1, 2k, 2k+1 to: 1, 2k, 2k-2. To counter this move, and not lose, the opposing player will take 1 from the second pile. The situation is now: 1, 2k-1, 2k-2 = 1, 2(k-1) + 1, 2(k-1). So long as k-1 isn't 0, lather, rinse, repeat! Continuing this leads to the losing player eating 3k+1 candies, while the winning player eats k+1 candies over the course of the game.
Are there any other good entertainment "games" you can play as a losing player?
The idea works as follows: you are in a losing Nim position (and the other player seems to know "the trick" to keep on winning). You decide to come up with a secondary goal: try to eat (take) as many of the remaining objects (pieces of candy) as possible. Michael proves that in this case, there is a way to eat at least half of the remaining objects!
Consider the case where there are two piles of objects, both with the same number (they have to be the same, otherwise you're not in a losing position). In this case, no matter how many you eat, the other player will take the same amount, and you'll eat exactly half the candy.
In some cases, there is a better "strategy". For example, if there are three piles, and one of them has size 1, then the other two must look like 2k and 2k + 1 for some k. Now, there is a way to net a 3-to-1 advantage in this situation: take 3 from the pile with 2k+1.
Then our piles go from: 1, 2k, 2k+1 to: 1, 2k, 2k-2. To counter this move, and not lose, the opposing player will take 1 from the second pile. The situation is now: 1, 2k-1, 2k-2 = 1, 2(k-1) + 1, 2(k-1). So long as k-1 isn't 0, lather, rinse, repeat! Continuing this leads to the losing player eating 3k+1 candies, while the winning player eats k+1 candies over the course of the game.
Are there any other good entertainment "games" you can play as a losing player?
Friday, April 16, 2010
Playing While Losing and Collecting Candy
Sometimes gamesters play games even when they are in a losing position. This means that even though we know there is no winning strategy from the current game state, they'll keep playing.
This happens for a lot of reasons. Often, this occurs because the winning strategy for the other player is not known (even though it is known that it exists). For example, the first player to move in Chomp is the winning player, though what that first move should be is unknown. Thus, if someone challenges me to a game of Chomp, but they are going first, I don't immediately quit the game. They will make their first move, and then who knows whether I'm still in a losing position?
Other times, even when a winning strategy is known, there is a chance it is not known by the player in the winning position. You might be in a losing position this turn, but if you make a sneaky enough move, perhaps they won't be able to do it again next turn...
There is the chance also that you play purposefully from a losing position, hoping your opponent will learn how to maintain their "winningness". If I am a parent someday, I bet I will do this more often!
As yet another option, it might just be that your opponent will take it badly if you quit on the game, even though it's clear who will win. You'd like to quit, but they want you to play the whole thing out. This is likely very instructive for them, so you should probably go ahead with it :)
Michael Albert found a way for the losing player to entertain themselves in (some of) these situations while playing the game Nim. The idea is to consider all the objects as pieces of candy, and by removing them from a pile, you get to eat the delicious candy! Naturally, this is not as rewarding as winning, but if you're going to lose, you might as well acquire as much of the candy as you can! He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile). This implies that the winning player will always make the best responding winning move.
I'll talk some more about "Candy Nim" next week. Have a great weekend!
This happens for a lot of reasons. Often, this occurs because the winning strategy for the other player is not known (even though it is known that it exists). For example, the first player to move in Chomp is the winning player, though what that first move should be is unknown. Thus, if someone challenges me to a game of Chomp, but they are going first, I don't immediately quit the game. They will make their first move, and then who knows whether I'm still in a losing position?
Other times, even when a winning strategy is known, there is a chance it is not known by the player in the winning position. You might be in a losing position this turn, but if you make a sneaky enough move, perhaps they won't be able to do it again next turn...
There is the chance also that you play purposefully from a losing position, hoping your opponent will learn how to maintain their "winningness". If I am a parent someday, I bet I will do this more often!
As yet another option, it might just be that your opponent will take it badly if you quit on the game, even though it's clear who will win. You'd like to quit, but they want you to play the whole thing out. This is likely very instructive for them, so you should probably go ahead with it :)
Michael Albert found a way for the losing player to entertain themselves in (some of) these situations while playing the game Nim. The idea is to consider all the objects as pieces of candy, and by removing them from a pile, you get to eat the delicious candy! Naturally, this is not as rewarding as winning, but if you're going to lose, you might as well acquire as much of the candy as you can! He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile). This implies that the winning player will always make the best responding winning move.
I'll talk some more about "Candy Nim" next week. Have a great weekend!
Tuesday, April 13, 2010
Teaching with a Game
Someday I will be asked to teach a class about logic gates. At that point, I will (want to) use bOOleO as a teaching tool.
bOOleO is a card game where two players race to be the first to complete a logic "pyramid". Each card is either an AND, OR or XOR gate and an output of 0 (False) or 1 (True). This means that a player can't use an OR-1 card on two 0-inputs.
The base row of cards are just randomly either 0 or 1, and a player has to build a triangle down from this until they have just one card at the end.
I've only played with a few students, but they already have made excellent comments I won't be able to ignore when it is my turn to teach. First, the deck comes with two "cheet sheat" cards that list all the input-output combinations for each gate. This is a useful aid for those new to boolean logic. After a couple bOOleO games, however, these reference cards are no longer necessary.
Considering strategies leads to a stronger understanding of logic gates. One facet of the game are NOT cards, which invert one of the base row of cards, switching a 0 to a 1 and vice versa. Any gate cards that then have incorrect outputs for their inputs are discarded. Some gates are more susceptible to this than others. OR-0, AND-1 and both XOR cards will always be destroyed when their input changes. For OR-0 and AND-1, this occurs because they have only one working input combination. XOR, on the other hand, changes values with a change in any input.
AND-0 and OR-1 are a bit more robust: one in four input combinations are safe! Because of this, I usually find these cards to be more valuable than the other gates. Between the two of them, I favor the OR-1 cards, since a player has more flexibility with more 1s in their circuit.
Why is that? Well, since there are no NOR or NAND cards (NOT cards are not used as gates, but as the inverters as described above) there is no way to have a gate take two 0-inputs and output a 1, though XOR-0 will do the opposite.
Most importantly, this is an involved game, but with enough randomness to prevent it from being too serious. Interacting this way with logic gates can really help to bring the point home.
If I used this in class, though, I might try to create some more complex boards for game play that more closely resembles circuitry.
What other games are great as examples for teaching "non-game" subjects?
bOOleO is a card game where two players race to be the first to complete a logic "pyramid". Each card is either an AND, OR or XOR gate and an output of 0 (False) or 1 (True). This means that a player can't use an OR-1 card on two 0-inputs.
The base row of cards are just randomly either 0 or 1, and a player has to build a triangle down from this until they have just one card at the end.
I've only played with a few students, but they already have made excellent comments I won't be able to ignore when it is my turn to teach. First, the deck comes with two "cheet sheat" cards that list all the input-output combinations for each gate. This is a useful aid for those new to boolean logic. After a couple bOOleO games, however, these reference cards are no longer necessary.
Considering strategies leads to a stronger understanding of logic gates. One facet of the game are NOT cards, which invert one of the base row of cards, switching a 0 to a 1 and vice versa. Any gate cards that then have incorrect outputs for their inputs are discarded. Some gates are more susceptible to this than others. OR-0, AND-1 and both XOR cards will always be destroyed when their input changes. For OR-0 and AND-1, this occurs because they have only one working input combination. XOR, on the other hand, changes values with a change in any input.
AND-0 and OR-1 are a bit more robust: one in four input combinations are safe! Because of this, I usually find these cards to be more valuable than the other gates. Between the two of them, I favor the OR-1 cards, since a player has more flexibility with more 1s in their circuit.
Why is that? Well, since there are no NOR or NAND cards (NOT cards are not used as gates, but as the inverters as described above) there is no way to have a gate take two 0-inputs and output a 1, though XOR-0 will do the opposite.
Most importantly, this is an involved game, but with enough randomness to prevent it from being too serious. Interacting this way with logic gates can really help to bring the point home.
If I used this in class, though, I might try to create some more complex boards for game play that more closely resembles circuitry.
What other games are great as examples for teaching "non-game" subjects?
Friday, April 9, 2010
No Post Today
I forgot to mention yesterday, but I am at a workshop all day today and won't be able to write a usual post.
Also, you are interested in me covering a topic soon, let me know and I'll do my best to talk about it!
Also, you are interested in me covering a topic soon, let me know and I'll do my best to talk about it!
Tuesday, April 6, 2010
Tsuro has dual-locality, why doesn't Geography?
I've mentioned before that I think Tsuro is a very elegant game. If I get a group of thoughtful people together to play, they will often notice some of the great properties that aren't immediately obvious. No cycles (for player tracks) and no overlapping paths make sense after some consideration, but it is still often asked as a question.
A quick synopsis of the game is that pieces move along paths printed on tiles. On your turn, you play a new tile on an untiled place on the board to move your piece further along. These tiles each have a different matching of paths connecting two sides. That place of a tile could move other pieces, also. A player loses when they either collide with another piece or follow a path off the board.
Aside from the parts mentioned up top, there are other cool aspects of Tsuro. One of these is the fact that it looks a lot like Geography.
Geography? How could that be? Geography is impartial! Tsuro is very partisan: each player has their own hand of tiles and their own piece.
Well, first of all, in order to make it more "combinatorial gamey" we have to consider removing the hands anyways to eliminate hidden information. (Perhaps instead there is just a communal pile everyone selects from.)
Now, what if instead of having two pieces, both players shared the same piece. Now you have to make sure you don't lead the piece off the board on your turn. This now looks a lot like geography, where players traverse a directed graph and must avoid crashing into an already-visited vertex.
There are plenty games that enforce a sort of locality---you have to play near the last play. Tsuro has a cool property where each player has their own sense of locality. They play not from the last play, but from their last play (unless they get moved).
What if the same were true in Geography? What if each player had their own piece moving through the directed graph, but you lose if you visit a vertex previously visited by either player? How difficult is it to play this version well?
In a very unrelated note, Molly points out this podcast, which contains a cool mention (near the end) of a board game enthusiast who uses analogical modelling to choose whether or not to buy a new board game. Ha!
A quick synopsis of the game is that pieces move along paths printed on tiles. On your turn, you play a new tile on an untiled place on the board to move your piece further along. These tiles each have a different matching of paths connecting two sides. That place of a tile could move other pieces, also. A player loses when they either collide with another piece or follow a path off the board.
Aside from the parts mentioned up top, there are other cool aspects of Tsuro. One of these is the fact that it looks a lot like Geography.
Geography? How could that be? Geography is impartial! Tsuro is very partisan: each player has their own hand of tiles and their own piece.
Well, first of all, in order to make it more "combinatorial gamey" we have to consider removing the hands anyways to eliminate hidden information. (Perhaps instead there is just a communal pile everyone selects from.)
Now, what if instead of having two pieces, both players shared the same piece. Now you have to make sure you don't lead the piece off the board on your turn. This now looks a lot like geography, where players traverse a directed graph and must avoid crashing into an already-visited vertex.
There are plenty games that enforce a sort of locality---you have to play near the last play. Tsuro has a cool property where each player has their own sense of locality. They play not from the last play, but from their last play (unless they get moved).
What if the same were true in Geography? What if each player had their own piece moving through the directed graph, but you lose if you visit a vertex previously visited by either player? How difficult is it to play this version well?
In a very unrelated note, Molly points out this podcast, which contains a cool mention (near the end) of a board game enthusiast who uses analogical modelling to choose whether or not to buy a new board game. Ha!
Friday, April 2, 2010
Game Description: Hanoi Stick-up
I have to get a set of Towers of Hanoi now!
Some of my CS professors had wooden Towers of Hanoi in their offices. These are used to demonstrate a cool process (usually described recursively) to move a stack of different-sized discs from one place to another. The stack starts off with the largest disc on the bottom, with successively smaller discs all the way up. At each step of the moving process, no discs are allowed to be placed on discs smaller than themselves. While moving the stack from one location to the next, you are only allowed to use one other place to stack, besides the start and ending places.
No matter how high the stack of discs begins, you are always able to move the discs, one at a time, to shift the stack at the destination.
Cool problems like this are often the best inspiration for new combinatorial games, and the Towers of Hanoi are no different! The result is the game Hanoi Stick-up. (Does anyone know who created this game?)
In this game, all discs start off on their own separate stack. A move consists of moving one stack on top of another; the whole thing, not just one disc. The bottom disc on the stack being moved must still be placed on top of a larger disc. Under normal play, you lose the game if you cannot move a stack on top of another.
Hanoi Stick-up is an impartial game, since both players can move whichever discs they like. This is a game with very simple rules, but it misses one of the main concepts of the Towers by allowing players to move more than one disc in a turn. However, trying to enforce doesn't lead to an interesting game; both players will just move the same disc back and forth without going anywhere. If you're going to lose the game, you can instead just undo the last move. In Hanoi Stick-up, you have to combine two stacks together each turn. Perhaps a partisan game with a coloring of the discs could lead to something more "traditional".
On a less relevant, but cool note, Andy posted about WittCon from this past weekend! Bonus!
Some of my CS professors had wooden Towers of Hanoi in their offices. These are used to demonstrate a cool process (usually described recursively) to move a stack of different-sized discs from one place to another. The stack starts off with the largest disc on the bottom, with successively smaller discs all the way up. At each step of the moving process, no discs are allowed to be placed on discs smaller than themselves. While moving the stack from one location to the next, you are only allowed to use one other place to stack, besides the start and ending places.
No matter how high the stack of discs begins, you are always able to move the discs, one at a time, to shift the stack at the destination.
Cool problems like this are often the best inspiration for new combinatorial games, and the Towers of Hanoi are no different! The result is the game Hanoi Stick-up. (Does anyone know who created this game?)
In this game, all discs start off on their own separate stack. A move consists of moving one stack on top of another; the whole thing, not just one disc. The bottom disc on the stack being moved must still be placed on top of a larger disc. Under normal play, you lose the game if you cannot move a stack on top of another.
Hanoi Stick-up is an impartial game, since both players can move whichever discs they like. This is a game with very simple rules, but it misses one of the main concepts of the Towers by allowing players to move more than one disc in a turn. However, trying to enforce doesn't lead to an interesting game; both players will just move the same disc back and forth without going anywhere. If you're going to lose the game, you can instead just undo the last move. In Hanoi Stick-up, you have to combine two stacks together each turn. Perhaps a partisan game with a coloring of the discs could lead to something more "traditional".
On a less relevant, but cool note, Andy posted about WittCon from this past weekend! Bonus!
Tuesday, March 30, 2010
Winning Player Conjectures
The game Sprouts has a very interesting conjecture associated with it:
If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.
This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.
Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.
Along these same lines, there is a conjecture for Atropos:
If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.
This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.
Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.
What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?
If the game starts off with n dots, then the first player has a winning strategy exactly when n mod 6 = 3, 4, or 5.
This seems strange. Why 6? How is this number inherent to the rules of Sprouts? Well, it's not clear that it is, because the conjecture has not been proven.
Nevertheless, supporting cases continue to be found. Somehow I am comforted by the idea that somewhere, there is a computer working to check cases for Sprouts. (Probably I feel the same way about the Collatz Conjecture. Someone is running that right now, right?) Sprouts is also studied in the misere version, with other cases being checked.
Along these same lines, there is a conjecture for Atropos:
If the game starts with n open circles along a side, then the first player has a winning strategy exactly when n mod 4 = 0 or 3.
This has a bit of intuition behind it: if the losing player can enforce that the game drags out to the last circle, then that last circle will cause the loss. Since the number of open circles at the beginning game are 1 + 2 + ... + n = n (n + 1)/2, this is even exactly when n mod 4 = 0 or 3.
Naturally, there is lots known about starting positions. Hex and Chomp both are wins for the first player, though the proof is non-constructive.
What about other games, such as Amazons? Which conjectures exist for the winning player from starting positions?
Friday, March 26, 2010
Game Description: Toppling Dominoes
I did a "tour" of classes the past few weeks, advertising my board game course next semester. While doing this, I brought my copy of "Lessons In Play" to show off. On the cover is the addition of a Konane game with a Toppling Dominoes game that equals an Amazons game.
I point out that it's pretty cool that we can express games this way. Unfortunately, I realized that I didn't really know anything about "that dominoes game". Hmmm...
It turns out the rules to this game are very simple! Here's how it works.
With a supply of dominoes, each colored green, blue or red, set some of them up in one row. Then the Blue and Red players alternate turns, each knocking one of their own colored dominoes (or any green domino) to the right or left, thus knocking down all the other dominoes on that side.
Notice that this game, just like normal Nim, is not terribly interesting alone. In just one row, any player who has a domino of their color (or green) on one of the edges of row can just topple that one, knock down all the other dominoes, and win as there are no more plays. In fact, in the case with only blue and red dominoes, if both ends are in your color, your opponent has no way to prevent you from winning.
With more than one game, however, this gets more interesting and it becomes important to find the actual value of each game to play best.
I don't know the complexity of analyzing this game, though.
I point out that it's pretty cool that we can express games this way. Unfortunately, I realized that I didn't really know anything about "that dominoes game". Hmmm...
It turns out the rules to this game are very simple! Here's how it works.
With a supply of dominoes, each colored green, blue or red, set some of them up in one row. Then the Blue and Red players alternate turns, each knocking one of their own colored dominoes (or any green domino) to the right or left, thus knocking down all the other dominoes on that side.
Notice that this game, just like normal Nim, is not terribly interesting alone. In just one row, any player who has a domino of their color (or green) on one of the edges of row can just topple that one, knock down all the other dominoes, and win as there are no more plays. In fact, in the case with only blue and red dominoes, if both ends are in your color, your opponent has no way to prevent you from winning.
With more than one game, however, this gets more interesting and it becomes important to find the actual value of each game to play best.
I don't know the complexity of analyzing this game, though.
Tuesday, March 23, 2010
Tournament Spectator Scoring
In late March in the United States, there is a college sporting event known as March Madness in which the top 64 (sort of) mens college basketball teams compete in a lose-once tournament to determine the annual champion.
I'm not a huge basketball fan---mostly because I have no sense of verifying whether a foul happened---but as with any sport, it can be tons of fun to watch. With March Madness, there is a different level of spectating that occurs. Instead of watching all the games, fans instead predict who will win each game by filling out a bracket (such as this one) before the tournament.
Fans then compete with others using their brackets. You gain or lose points by correctly or incorrectly predicting winners at each round, respectively. How does this scoring usually work?
The first time I did this with some friends in grad school, we scored by simply counting the number of incorrect guesses. The "contestant" with the least won.
Alternatively, you can assign a different number of points per incorrect guess at each round. For example, each correct guess in the first round could be worth 1 point, each in the second worth 2, then 4, then 8, 16, and the final game is worth 32 points if predicted correctly. This is apparently the preferred method (using the scientific method of web browsing).
The problem with this is that after the first few rounds, many of your teams have been eliminated. Sports are much more fun to follow if you always have a team to follow, independent of the game. If I didn't predict either of the teams to take part in a game, then I don't care who wins! Instead, whenever a team you picked loses, you cross them off everywhere in your bracket they appear (losing points at each step) and replace them with the team that beat them. This year, I picked Villanova to "go all the way" but they lost in the second round to St. Mary's College. Now, I am rooting for St. Mary's to win their next game.
This year, my competition is colleague Bill Higgins, who knows something about basketball. We agreed to score this way, with each "correction" costing 1 point. Villanova losing has already cost me 5 points, but it could cost me more if St. Mary's loses (especially if they lose soon).
One problem here is that the final game is likely not super exciting. It is only worth 1 point! Instead, each correction could cost different amounts depending on the round the correction was made. Then, using the 1, 2, 4, ... 32 sequence, I would have lost 10 points due to Villanova's loss instead of 5. In this case, everyone has a stake in the final game and it's worth 32 points. Here, however, because more than 32 points can be lost in any other round, it does not eclipse the weight of other rounds.
Perhaps that would be better to use...
Anyone familiar with other good scoring methods?
I'm not a huge basketball fan---mostly because I have no sense of verifying whether a foul happened---but as with any sport, it can be tons of fun to watch. With March Madness, there is a different level of spectating that occurs. Instead of watching all the games, fans instead predict who will win each game by filling out a bracket (such as this one) before the tournament.
Fans then compete with others using their brackets. You gain or lose points by correctly or incorrectly predicting winners at each round, respectively. How does this scoring usually work?
The first time I did this with some friends in grad school, we scored by simply counting the number of incorrect guesses. The "contestant" with the least won.
Alternatively, you can assign a different number of points per incorrect guess at each round. For example, each correct guess in the first round could be worth 1 point, each in the second worth 2, then 4, then 8, 16, and the final game is worth 32 points if predicted correctly. This is apparently the preferred method (using the scientific method of web browsing).
The problem with this is that after the first few rounds, many of your teams have been eliminated. Sports are much more fun to follow if you always have a team to follow, independent of the game. If I didn't predict either of the teams to take part in a game, then I don't care who wins! Instead, whenever a team you picked loses, you cross them off everywhere in your bracket they appear (losing points at each step) and replace them with the team that beat them. This year, I picked Villanova to "go all the way" but they lost in the second round to St. Mary's College. Now, I am rooting for St. Mary's to win their next game.
This year, my competition is colleague Bill Higgins, who knows something about basketball. We agreed to score this way, with each "correction" costing 1 point. Villanova losing has already cost me 5 points, but it could cost me more if St. Mary's loses (especially if they lose soon).
One problem here is that the final game is likely not super exciting. It is only worth 1 point! Instead, each correction could cost different amounts depending on the round the correction was made. Then, using the 1, 2, 4, ... 32 sequence, I would have lost 10 points due to Villanova's loss instead of 5. In this case, everyone has a stake in the final game and it's worth 32 points. Here, however, because more than 32 points can be lost in any other round, it does not eclipse the weight of other rounds.
Perhaps that would be better to use...
Anyone familiar with other good scoring methods?
Friday, March 19, 2010
No FUN for me. :( Other conferences?
FUN with Algorithms 2010 is taking place in Italy in early June. I submitted two papers, but neither of them made it in.
I would normally still probably try to go, but I'm getting married shortly afterwards. (Woohoo!) Without the excuse of presenting a paper, I won't attempt to squeeze these things together.
I've missed a lot of following paper deadlines, and there are others that I am either interested in or would consider submitting to. Here's a little list of what's already passed by (but might be candidates in future years):
FUN 2010
AOFA 2010
SWAT 2010
ICALP 2010
COCOON 2010
FAW 2010
Those still coming are:
GandALF 2010
FOCS 2010
SAGT 2010
COMSOC 2010
ICS 2011
INTEGERS 2010 (I don't have a site for this yet. INTEGERS 2009 had a very short submission/acceptance time.)
LAGOS 2011
(These are listed in order of (expected) submission deadline, not actual conference dates.)
I mostly catch these as they come through Theory Net. I'm likely out of touch with some more math-based feeds, though. Can anyone suggest other conference options?
Also, I've played a bunch of games of bOOleO this week already! This is an excellent card game! If I ever teach a machine organization course, I will somehow work this in as an example of logic gates!
I would normally still probably try to go, but I'm getting married shortly afterwards. (Woohoo!) Without the excuse of presenting a paper, I won't attempt to squeeze these things together.
I've missed a lot of following paper deadlines, and there are others that I am either interested in or would consider submitting to. Here's a little list of what's already passed by (but might be candidates in future years):
FUN 2010
AOFA 2010
SWAT 2010
ICALP 2010
COCOON 2010
FAW 2010
Those still coming are:
GandALF 2010
FOCS 2010
SAGT 2010
COMSOC 2010
ICS 2011
INTEGERS 2010 (I don't have a site for this yet. INTEGERS 2009 had a very short submission/acceptance time.)
LAGOS 2011
(These are listed in order of (expected) submission deadline, not actual conference dates.)
I mostly catch these as they come through Theory Net. I'm likely out of touch with some more math-based feeds, though. Can anyone suggest other conference options?
Also, I've played a bunch of games of bOOleO this week already! This is an excellent card game! If I ever teach a machine organization course, I will somehow work this in as an example of logic gates!
Tuesday, March 16, 2010
Oops and Updates!
Hmmm...
I see that I missed Friday. As soon as I noticed that, I feared that I had missed last Tuesday also, but, no, I showed up that day. Last week was spring break, but I did not intend to take as much time off from work as I did. I apologize for missing on Friday!
One of my big tasks for this past week was to make sure everything was okay to close down my web account from BU's CS department. Sad! Now the Atropos and Matchmaker applets are hosted on Wittenberg sites, and they seem to work just fine. Please let me know if you notice any problems with either of them, and I'll fix them immediately! (If you don't have Java enabled on your browser, there's not much I can do for you.)
I am expecting to get a copy of bOOLeO delivered soon! That game looks excellent! There is something very enticing about seeing game pieces in pictures and coming up with what you expect the rules to be before actually reading any.
I realize that of Atropos and Matchmaker listed above, I have only actually published (thesis not counting) about one of them. I have never submitted a paper about Matchmaker anywhere, though it might be a topic that could sneak in somewhere. Still, I am a bit loathe to do this until after I prove something concrete about the difficulty of the game. Either showing that it can be solved in polynomial time or finding a completeness result would be enough for me (I haven't worked on this game in a long time).
Is this legitimate? I've noticed that in some of my presentations, no one cares about solving the game, but are instead more interested in the origins and rules (and implementations) of the game. Perhaps it is more vital to get playable versions of games out and introduce them that way than to make sure something is known about them first.
I see that I missed Friday. As soon as I noticed that, I feared that I had missed last Tuesday also, but, no, I showed up that day. Last week was spring break, but I did not intend to take as much time off from work as I did. I apologize for missing on Friday!
One of my big tasks for this past week was to make sure everything was okay to close down my web account from BU's CS department. Sad! Now the Atropos and Matchmaker applets are hosted on Wittenberg sites, and they seem to work just fine. Please let me know if you notice any problems with either of them, and I'll fix them immediately! (If you don't have Java enabled on your browser, there's not much I can do for you.)
I am expecting to get a copy of bOOLeO delivered soon! That game looks excellent! There is something very enticing about seeing game pieces in pictures and coming up with what you expect the rules to be before actually reading any.
I realize that of Atropos and Matchmaker listed above, I have only actually published (thesis not counting) about one of them. I have never submitted a paper about Matchmaker anywhere, though it might be a topic that could sneak in somewhere. Still, I am a bit loathe to do this until after I prove something concrete about the difficulty of the game. Either showing that it can be solved in polynomial time or finding a completeness result would be enough for me (I haven't worked on this game in a long time).
Is this legitimate? I've noticed that in some of my presentations, no one cares about solving the game, but are instead more interested in the origins and rules (and implementations) of the game. Perhaps it is more vital to get playable versions of games out and introduce them that way than to make sure something is known about them first.
Tuesday, March 9, 2010
Double Games
Sometimes it's fun to try and combine multiple game boards or sets at the same time. We can always use the normal ways of adding two games together, but there are some other alternatives too...
In high school, a friend of mine mentioned he used to play "boxcar chess" with his family. This is a version of chess using two sets and four players on two teams. Two games went on at the same time, except whenever you capture an opponent's piece, your teammate gets to add that piece to their board. Thus, you had to play the opposite color of your teammate.
I don't know the details of how you add "new" pieces, but I assume you can spend a turn to place one of them in your back row.
I tried to adapt this for Stratego, since my family had two sets. I made the rules a bit too strict, however, and it wasn't all that interesting. I'd like to give it another try some day with more flexible rules.
Then, just last week, I was chatting with Brian about old war games (I really am only familiar with Risk and Diplomacy) and he mentioned enjoying "Double Risk" using two boards. The boards interact by including adjacencies between each pair of countries with the same names. Thus, if I wanted to get past Central America on board A (which has a bunch of armies on it) and I have a big force on Venezuela on board A, I could instead attack Venezuela on board B, then Central America on board B, then, say, Western United States on board B and on to Western United States on board A. I don't actually think this is a good Risk strategy, but I'm still bitter at that game for the power of cards...
In high school, a friend of mine mentioned he used to play "boxcar chess" with his family. This is a version of chess using two sets and four players on two teams. Two games went on at the same time, except whenever you capture an opponent's piece, your teammate gets to add that piece to their board. Thus, you had to play the opposite color of your teammate.
I don't know the details of how you add "new" pieces, but I assume you can spend a turn to place one of them in your back row.
I tried to adapt this for Stratego, since my family had two sets. I made the rules a bit too strict, however, and it wasn't all that interesting. I'd like to give it another try some day with more flexible rules.
Then, just last week, I was chatting with Brian about old war games (I really am only familiar with Risk and Diplomacy) and he mentioned enjoying "Double Risk" using two boards. The boards interact by including adjacencies between each pair of countries with the same names. Thus, if I wanted to get past Central America on board A (which has a bunch of armies on it) and I have a big force on Venezuela on board A, I could instead attack Venezuela on board B, then Central America on board B, then, say, Western United States on board B and on to Western United States on board A. I don't actually think this is a good Risk strategy, but I'm still bitter at that game for the power of cards...
Subscribe to:
Posts (Atom)
