6
$\begingroup$

In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions:

(1) The game is finite; i.e. there is a constant $c$ such that all games end in $c$ moves or fewer.

(2) There are no draws; either player 1 or player 2 wins.

(3) The rules of the game draw no distinction between the players. That is, given any position, if we switch the active player then the set of legal moves is still the same, and the player who wins the game under perfect play switches.

It is often said in introductory CGT resources (here for example) that a major class of games that violate condition (3) are those in which each player has their own piece set. For example, chess violates (3) because the white player can only move the white pieces and the black player can only move the black pieces, so if we switch the active player then the set of legal moves changes.

However, it seems to me that this problem can be circumvented by the following trick. Instead of defining a "position" as the locations of the white and black pieces, we define a position as the locations of the active player's pieces and the passive player's pieces. Now the conditions in (3) are satisfied.

This trick seems too simple to be original, though, and I have read in many places about how chess is a classic example of a partisan game. So what am I missing?

Aside: To circumvent (1) and (2), we need to modify chess in some reasonable way; i.e. forbid 3x repetition of a single position and declare stalemate to be a win for the stalemating player. But that's beside the point of my question.


Years-later edit since this question has gotten some random attention lately: neither of the answers really understood the point of the question (which is probably my fault for an unclear OP). My current understanding is that there is indeed a natural isomorphism between finite drawless chess and an impartial game, but impartiality is not a property that is always preserved under isomorphism, and my misunderstanding came from the assumption that it was.

$\endgroup$
  • $\begingroup$ The only way to make Chess impartial is to allow both players to move either black or white. In that case, you could say that the last player able to move wins under "normal play" and the game would be reducible to a Nimber. $\endgroup$ – DukeZhou Aug 25 '16 at 2:45
  • $\begingroup$ If I modelled chess with a variable called 'ActivePieces' that flips between 'Black' and 'White' after every go then that would result in each player effectively 'owning' their pieces but nowhere was a set of pieces defined as belonging to either player. Doesn't this satisfy the definition of an impartial game? $\endgroup$ – Nux Oct 10 '18 at 14:51
  • $\begingroup$ If introducing an 'ActivePieces' variable that flips each turn prevents the game from being impartial then where does it end? Nim by this reasoning isn't impartial because there's an effective asymmetry between the first and second players given that the first player has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. $\endgroup$ – Nux Oct 10 '18 at 15:08
  • $\begingroup$ How can a game be said to "allow both players the same moves" if players necessarily put each other into new game-states. The only way both players would have the exact same set of moves available to them is if either player could make a move at any time and which one did has no effect on the outcome. In this case, people in this thread are right to say this is effectively a 1-player game but by the same token so are all impartial games. $\endgroup$ – Nux Oct 11 '18 at 8:33
1
$\begingroup$

Yes, I believe your changes turn chess into an impartial game. As you mention, stalemate and three-fold repetition can be dealt with by declaring loss.

Your trick decouples players (P1 and P2) from the player to move in the position (White or Black). If the two players play chess in isolation, then those two properties will be in perfect sync. The problem is that CGT allows combining games. Imagine adding chess and checkers. This means that every player on their turn picks either a chess move or a checkers move. Suppose P1 makes a chess move with White, and P2 makes a checkers move. Then P1 can make a chess move with Black! There is no longer a correspondence between the people and the colors on the board.

In a sense, your game has no fixed White and Black; we might as well say that White is always to move, and after each turn we rotate the board and swap colors. There is no real ownership of pieces. This clearly satisfies criterion (3).

I don't know the theory of partisan games, but it's clear that if you didn't remove the "partisanness" from chess, you could form a chess + checkers sum where you can move pieces with only one color.

If you identify a game by its graph of legal move histories, then your chess and normal chess are the same (modulo draws). If you think of the game as a set of rules, and consider games as "first class functions" that can be combined, then they are different.

$\endgroup$
  • $\begingroup$ Ahhh! This detail about adding games is exactly what I was looking for, and you're absolutely right that it destroys the decoupling. Thank you. $\endgroup$ – GMB Dec 11 '18 at 20:50
7
$\begingroup$

Chess violates all three conditions, so I don't really understand what there is to ask.

(1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game under certain circumstances, they do not oblige the player to do so.

(2) The game has draws.

(3) As you have observed, the game definition distinguishes between the players. Your "active player" trick doesn't work because you've turned chess into a one-player game: the "active" player makes every move and the "inactive" player is a spectator.

$\endgroup$
  • $\begingroup$ I agree that (1) and (2) are violated, but my question is more about the modified version of chess from the OP that only debatably violates (3). On that point, I don't yet see how the game distinguishes between the active players in a way that Nim does not. Defining pieces by active/passive ownership just gives intuition behind the meaning of the position nodes in a game tree; it doesn't modify the transition structure of the game tree. $\endgroup$ – GMB Apr 27 '15 at 23:55
  • $\begingroup$ I think that this formulation may bend the notion of "position" beyond what is originally intended. Under this definition, both players do not see the same position at any given time. $\endgroup$ – mhum Apr 28 '15 at 1:51
  • $\begingroup$ @GMB You're right; now fixed. The actual problem is that you've turned chess into a one-player game. $\endgroup$ – David Richerby Apr 28 '15 at 8:39
  • $\begingroup$ But I haven't changed the way the game is played ... my understanding is this: an impartial game is one that can be modeled as a DAG where the players take turns walking an edge, and you lose if you are in a sink and there is no edge left to traverse. I am not trying to change the game structure; I am trying to change the real-world intuition behind the nodes ("positions") and edges ("moves") of the DAG. $\endgroup$ – GMB Apr 28 '15 at 19:35
  • 1
    $\begingroup$ You've massively changed the way the game is played. The "active" player makes every move so he doesn't care if he wins by checkmating black or white. He has a strong incentive to checkmate himself as fast as possible, which is not how normal chess works. $\endgroup$ – David Richerby Apr 28 '15 at 20:50
3
$\begingroup$

"To be impartial, a game must satisfy these three conditions".

My understanding is that what makes a game impartial or partisan is purely a function of whether or not the same plays are available to both players.

Chess is partisan because there are black and white pieces, and players can only move their own color.

The other two conditions listed are not a categorization of impartial games, but a definition of a particular game being analyzed. (This can be very confusing to those outside this still woefully obscure, but very important, field.)

In most CGT papers, the scholars begin by defining "what is a game". It is meant to apply only to the specific game being analyzed, and is never meant to be taken as a general definition of games, or combinatorial games, in general.

Fraenkel provides a very clear definition of several aspects of combinatorial games here: Infinite cyclic impartial games


Note: I think the confusion here derives from how mathematicians define games in research papers: "A game is..." or "An impartial game is..." The idea is they are defining the term in regard to the game they are analyzing, and it's not meant to be universal definition. This creates a lot of confusion for people outside the field, and, having read widely on the subject, "impartial" as a general term is not well defined. (This terminological fuzziness is irrelevant in regard to the validity of the mathematical work, and seems only to be a taxonomic issue.)

$\endgroup$
  • $\begingroup$ Thanks for your answer. I don't think that this answer or the previous one really get the point of my question (which is probably my fault for an unclear OP). My point is that chess (modified somehow to forbid draws and make the game finite) can be seen as a walk through a particular finite game tree, and there exists an impartial game whose game tree is isomorphic to the chess one. So I guess my question is: can the impartial/partisan game distinction be made solely by examining the game tree? [based on these answers, it seems no]. If not, what other formal info is needed? $\endgroup$ – GMB Aug 25 '16 at 5:16
  • $\begingroup$ @GMB Feel free to draw new attention to your question by 1) editing it to make your actual question clearer and 2) posting a bounty. Note, however, that edits that invalidate answers are frowned upon, so you may want to post a new question. If you're still interested in this. $\endgroup$ – Raphael Aug 25 '16 at 9:50
  • $\begingroup$ @GMB Sorry, I didn't realize you were defining what you meant by an impartial game in this specific context. (Possibly I should delete this answer...) Regarding the assertion that "there exists an impartial game whose game tree us isomorphic to the chess one." Is that proven? $\endgroup$ – DukeZhou Aug 25 '16 at 13:28
  • 1
    $\begingroup$ @cybermike I don't think you should delete this answer. If GMB meant to define a new term, they shouldn't have used the name "impartial", since that already has a well-defined meaning, which is even linked. The natural reading of the question is, "The definition of impartial is XYZ; by the way, you can look on Wikipedia for more information", not "I'm defining a new term impartial which, by the way, is completely different from the term impartial that Wikipedia talks about." $\endgroup$ – David Richerby Aug 25 '16 at 14:09
0
$\begingroup$

It seems you're stuck on the idea that "indirecting" by alternating who is the active player somehow gets around restriction 3. One way to see that this is unlikely to be true is that the same trick "works" to get around restriction 3 for every possible game, meaning that restriction 3 is in fact not a real restriction at all, which prompts the question: Why would someone have included it in the definition in the first place? (We may as well add some more redundant restrictions to the definition, e.g.: "(4) The name of the game has an even or an odd number of letters".)

It could alternatively be that your trick works, and nobody in the field of combinatorial game theory so far noticed that condition 3 is completely redundant.

$\endgroup$
  • $\begingroup$ Thanks for the answer -- more specifically, I think the alternation thing would only work for every possible "board game," in which the only thing preventing the game from being impartial is that each player personally owns some "pieces." I do believe that every such game is isomorphic to an impartial game, but as edited into the OP, I think I understand now that partisan-ness doesn't automatically transfer under isomorphism. I understand that CGT people are good at their jobs, I obviously don't think they overlooked anything major :) $\endgroup$ – GMB Dec 11 '18 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.