Talk:Combinatorial game theory

2004-2005

Having math on the same line as text doesn't render properly. I suggest that for simple expressions, math mode shouldn't be used and more complex ones should be on a separate line. -- Arvindn 12:31, 29 Feb 2004 (UTC)

|Agree. But actually the problem with the page goes deeper - that's a severe case of dry textbook style, there.

Charles Matthews 14:09, 29 Feb 2004 (UTC)

Agree. It's a general problem with math articles (and this is a math topic). I'm not sure how one goes about solving it. You want the formalism to be there, for the people who are looking for it, and you also want a general discussion for people who are not mathematically literate -- a journalist, for example, should be able to get background here in case some mathematician makes news in CGT. How to arrange and intermix the two levels of presentation is a tricky conundrum.

There's another problem here, though, and that is that the article is very incomplete. The authors never get around to introducing the classic Berlekamp-Conway-Guy notation, and instead present the beginnings of the theory in their own notation, with the result that the beautiful heart of the theory, the mapping from games onto the real numbers, is completely missing.

I'd like to have more of a chat about this, to toss around ideas on how this material should be presented.

ACW 18:06, 11 Nov 2004 (UTC)

Well, the CGT people have a long tradition of not being able to explain themselves properly (IMHO). This page is too mathsy by half. I probably tend towards Berlekamp's attitude, and am less interested in ONAG. I have had weary discussions with Bill Spight, elsewhere, about the foundations. Charles Matthews 19:39, 11 Nov 2004 (UTC)

I think the ideal is a kind of two track description, so that the layman can read a fairly coherent explanation in plain English, while the mathematician can find the rigorous development as well. Maybe the two are interleaved, with an explanation up front that tells the lay reader than the stuff in small type (just brainstorming here) can be safely skipped. I can imagine a few ways of doing it.

Another thing that's troubling me is that the whole cluster of mathematical games articles could be better organized and more consistent ... more like they were articles from the same encyclopedia, if you get my meaning. I know the essence of True Wiki is little incremental changes without big Grand Plans, but I'm tempted to do a little Grand Planning here. You know, list the articles in the cluster, figure out what's missing, what should be moved, what are the expected reading paths, and so on. I'm too ambitious, right? ACW 02:15, 13 Nov 2004 (UTC)

Lists are good. A list of 'combinatorial games' topics would be a useful start, and a way to discriminate between CGT proper and its environs. Charles Matthews 10:06, 13 Nov 2004 (UTC)

I've just made some changes: (1) Most importantly, I've found and corrected what I think was an error (the author originally stated that C_fin is the smallest collection of games such that for every pair of H,K of elements there's a game G with L(G) = {H}, R(G) = {K}).

(2) I've explained what it means to 'play' these strange games.

(3) Using (2), I've added 'intuitive descriptions' of addition and negation of games.

(4) The author hadn't explained how to construct the set "P", so I worked out such a construction myself.

(Note that my only background in this theory came from actually reading the original page!)

---

I've modified your text a bit to speak of well-founded games, rather than finite non-loopy games. The distinction is a bit fine. For instance, consider the game G for which L(G)=R(G)=N, where N is the set of all nim-heaps. G is not finite, but it is well-founded. Conway calls these games "Enders".--Dan Hoey(because the signature feature seems to be malfunctioning)68.239.81.167 01:57, 24 October 2005 (UTC)

I see that what happened is I got logged out. Anyway, I've modified the definition of C_fin so that it covers all the well-founded collections of games. --Dan Hoey 02:18, 24 October 2005 (UTC)

I've fixed some problems with the definitions of well-founded games and C_fin. But what really needs to be done is to make this page more consistent with the Surreal numbers page. I've made a start by introducing the G = { L(G) | R(G) } notation. But the part about taking the quotient needs to be continued to talk about which games are numbers. Also something about the quotient being the greatest refinement that preserves outcomes of disjunctive sums. --Dan Hoey 15:22, 24 October 2005 (UTC)

---

This page lack of definiton of Combinatorial game theory (CGT). It is stated that is part of game theory, but not what is. In the formal definion it is not clear what a game is. Apart from mathemaical abstract aspect is not clear at all the correlation to real (normal) game AnyFile 13:31, 24 Jan 2005 (UTC)

---

Added a paragraph to the introduction to illustrate the purpose of CGT, and added a couple of good reference books. — Preceding unsigned comment added by 195.92.70.130 (talk) 11:52, 3 June 2005 (UTC)

History

The history section used the term disjoint sum which I corrected to disjunctive sum (ONAG, p. 74). This should be described more completely, since it is the fundamental insight that makes CGT an advance over the diffuse theory that preceded it.

I must say that I am quite uncertain about the History section. The mathematics of CGT were presented in ONAG six years earlier than WW, and the latter extended the theory in fairly minor ways. I don't imagine that Conway cares to argue priority; in fact, he acknowledges Berlekamp and Guy as his sources for much of the material in ONAG. But saying that WW "pioneered" CGT and was preceded by ONAG with some of its content seems an odd sort of horsecart. --Dan Hoey 23:34, 23 October 2005 (UTC)

I have discussed this with Elwyn Berlekamp, and I know how Conway works (he used to be a colleague). The lags in writing-up are true enough to the historical record. Charles Matthews 15:39, 24 October 2005 (UTC)

Yes, the history is not so simple. Although I was not yet alive at the time much of this was going on, I have met all authors of WW and have some familiarity with their opinions on the subject. You must remember that Winning Ways was in production for more than a decade, whereas ONAG was written (by Conway's own admission) in a week sometime in the middle of this period. Conway notes in the preface to the second edition that Berlekamp threatened legal action in response to the book, and that he failed to acknowledge Richard Guy's contributions of diagrams and tables for the first edition. I believe there is unanimity, however, that it was Conway who was responsible for the {L|R} notation and for the discovery of "surreal numbers". He dislikes that name, by the way; these were not named by him but by Donald Knuth, who somehow managed to beat them all to general publication! Only a University of Calgary research paper preceded Knuth in print, appearing under Conway's name, but written (apparently) largely by Guy. Knuth stole some of Guy's jokes in this paper.

So, the whole thing is a bit of a mess. The point is, it is not right to say that Conway invented CGT. One can say he invented the modern notation and first understood the concept of numbers, both of which are invaluable contributions to the subject, to be sure. The partizan theory in general, however, is due largely to WW and its authors (which includes Conway) even if it was published later. Of course, bits and pieces of this were floating about before then, and we can't overlook the importance of the impartial (Sprague-Grundy) theory, which was already well understood at this time.

I hope this helps future editors of this article. Someone should really do proper interviews of all these people while they are still alive to clear things up even further. -- 68.146.220.249 (talk) 00:31, 4 May 2008 (UTC)

---

Confused about point that WW required "complete information" yet more modern notion seems to require "perfect information." Why the switch? what are the implications Um297zoa (talk) 07:37, 5 June 2014 (UTC)

Simple English

Please take a look at the Simple English version of this page. Despite some errors, it is much better than this one. Rcaetano 15:23, 28 May 2005 (UTC)

I highly agree. Now that I've seen a "simple english" version of what this is, I've finally been able to figure out what the complex math notation is saying. I used the simple english version as a guide to add a "Simpler Definitions" section under formal definitions, which I hope will help people out. Needs some explanatory images of the tic-tac-toe boards I reference though... I'll see if I have the time to whip some up. Fieari 10:21, July 24, 2005 (UTC)

The Simple English page is wonderful! You might consider adding a link to it to this page, as it's a great introduction to this one. It gives a quick, easy overview, and this page adds more technical definitions and examples. Chocolatechipmuffin (talk) 15:51, 13 January 2008 (UTC)

There are a number of ways in which this article could be improved. The article could be organized and the topics introduced in a way similar to the article on surreal numbers. Some game other than tic-tac-toe ought to be used for an example, since tic-tac-toe is not played according to the normal rule, and does not break into independent components, like most games studied in Combinatorial Game Theory. Some other game, like nim or domineering might be a better example.

The example ought to introduce some of the common operations and definitions in Combinatorial Game Theory, such as the sum operator, inverse operator, bracket notation, and comparisons, and equivalent games. Sums and inverses could be demonstrated much better with some game other than tic tac toe. Contrary to what the current article seems to imply, these concepts can be given intuitive definitions that the layman can understand.

Additionally, the formal definitions below don't seem to correspond to any standard approach to combinatorial game theory, and the notation seems very obscure. The surreal numbers article has better definitions than this one, and it would make sense to copy these definitions into this article.

This article also has a lot of room for expansion. Information on further Combinatorial Game Theory topics could be introduced, such as canonical normal forms, numbers, nimbers, stopping values, thermography, infinitesimal games, all-small games, ordinal sums, norton products, and atomic weights (as well as a lot of other stuff that I don't know about). Most of this stuff is in On Numbers and Games, and there is probably a lot more stuff in Winning Ways. —The preceding unsigned comment was added by 152.157.79.253 (talk • contribs) .

Would you be able to suggest a textbook to reference? I haven't taken a class in this, I'm simply interested on a personal, almost hobby-like level, and to be honest, I can barely understand the current "Formal Definitions" at all. I simply took the "Simple English" version of this page and added it in... which was the only way I really understood what was going on. Fieari 18:15, 17 May 2006 (UTC)

Choice of Example Game

Using Tic-Tac-Toe as an example seems like a poor choice. This is not a typical sort of game that is analyzed in CGT, and it does not fit into the framework of the theory very well. For example, tic-tac-toe games can end in draws, although nonloopy games in CGT always end in one player winning. Also, it does not make much sense to add tic-tac-toe positions together, so the operation of addition cannot easily be demonstrated.

A better choice would be a game such as hackenbush, domineering, or nim, which are actually played under the Normal Rule. Positions in these games could be used to demonstrate some of the basic operations in CGT, such as addition and negation, in terms that the layman could understand. — Preceding unsigned comment added by 12.72.242.202 (talk) 19:55, 3 September 2006 (UTC)

Mathematical Presentation

The formal mathematical description in this article is vary confusing, even to someone who knows a lot about CGT, since it is completely unorthodox. The article on Surreal Numbers has a much better approach, that could be the model for this article, as the construction of Surreal Numbers is almost the same as the construction of the class of games. In general, this article should probably adopt the same notation and conventions as On Numbers and Games, or Winning Ways. Someone who has read these books should rewrite most of this article in a more orthodox notation. — Preceding unsigned comment added by 12.72.242.202 (talk) 20:01, 3 September 2006 (UTC)

Errors

In the tic-tac-toe example, the "star" scenario is described as

XUL_OUR_XCC_OCR_XLC_OLL_XCL_OUC = {{ | } | { | }}

I believe this is incorrect and that the correct game states are actually

XUL_OUR_XCC_OCR_XLC_OLL_XCL_OUC = {XLR | OLR}

XUL_OUR_XCC_OCR_XLC_OLL_XCL_OUC_XLR = {{ | } | { | }}

This seems more logical to me. 83.226.180.17 (talk) 13:46, 2 November 2010 (UTC)

"Formal Definitions", etc.: Suggestions

I've been watching this article for some time, hoping that it would be improved.

Of the books cited as sources, I own Winning Ways and ONAG. Not even ONAG features the formalism of this article. Therefore, I conclude that said formalism is pulled out of the air, i.e. original research. As has been pointed out above, it uses extremely unorthodox notation, which makes it very hard to understand. You will not see the notation <C,L,R> in ONAG, nor will you see the "0 element" defined to be unique. In fact, ONAG and WW make reference to "zero games," which are just those in which the second player wins with best play. In WW, the position {-2|2} is considered a zero game, whereas in the article it is not connected with the number zero in any way. This is unfortunate. Furthermore, the set P defined in the article is just the set of all zero games. Another problem with the formal portion of the article is that it provides little or no explanations of any of the steps taken.

Equally disconcerting is what is not mentioned in the article. There is no mention of "thermography," for example -- an important topic. The game * is mentioned briefly, but only in the informal section. The ideas of fuzzy, positive, negative, and zero games are not mentioned. The games {0|*} and {*|0} (up and down) are not included; nor is the idea of atomic weight of a game. Finally, the treatement of nimbers is far too brief.

I would try to be bold and fix this myself, but I am certain I would do a poor job. Although I am familiar with CGT, I do not have an intimate knowledge of it. Also, I don't have enough time to do this well.

--N Shar 05:33, 30 December 2006 (UTC)

I am eliminating the "Formal Definitions" section. As it stands, the formalism is entirely inappropriate to this page...it is introduced in a way appropriate to a Bourbaki volume, not an encyclopedia. If we are to include mathematical formalism in this page, we need to introduce it purposefully and with discussion that makes the relevance of the definitions apparent to the reader. Currently, even to a reader with a fair amount of mathematical background and some patience, the material is close to useless. Cazort (talk) 03:36, 24 November 2008 (UTC)

The current state of the article makes no sense whatsoever. A sum is defined, but this definition is quite hard to find from the place where + is used for the first time. Since sum is defined, one could guess what multiplication by a natural number would mean; however, most of discussion is in terms of notions =, < and > which are in no way defined. As a result, 2/3 of the article may be safely replaced by one sentence: “Trust me, one can do a lot of interesting things with these thingies.” --76.218.120.86 (talk) 08:02, 4 March 2012 (UTC)ilyaz

Changes in progress

I'm about to start working on rewriting this article. If you disagree with some change I make, please don't just revert -- also comment here. I'd really appreciate the input. Anyone else is welcome to join in, of course. --N Shar 02:11, 8 February 2007 (UTC)

Adversarial search

Artificial intelligence research (from the 1950s onward) developed a number of strategies (such as minimax, alpha-beta pruning, etc.) for winning two person games, referred to in AI textbooks as adversarial search. Should this article include a section on these algorithms? Should the articles that refer to these algorithms be included in the category Category:Combinatorial game theory? Is this the same field of study? ---- CharlesGillingham (talk) 11:01, 21 November 2007 (UTC)

• It seems like a related field to me. AI research tends to deal in heuristic methods for winning games. By contrast, combinatorial game theorists seek to understand the entire structure of a game in detail. I would tend to say that heuristic methods deserve a mention in the article, as they are an important technique used to study two-player games, but probably they shouldn't take over the article, as they are more engineering than mathematics. --N Shar (talk · contribs) 05:47, 18 December 2007 (UTC)

• I think Category:Game artificial intelligence, where these articles already are categorized, is a better place. There are connections between game search algorithms and combinatorial game theory, but they're really not the same thing. The game AI category should probably be included as a subcategory of one of the game theory categories, and I'll go do that, but since it includes games such as poker that are not really combinatorial in nature, I think the main game theory category would be a better place for that. —David Eppstein (talk) 05:52, 18 December 2007 (UTC)

• Do you have an opinion on whether they should be mentioned or described in the article? I wasn't sure what to say about this. I kind of think they should be mentioned (at least very briefly), but nevertheless I have an uncomfortable worry, somewhere in the back of my mind, that it would be "polluting" the mathematics. --N Shar (talk · contribs) 06:12, 18 December 2007 (UTC)

• Techniques like alpha-beta search and CGT don't mix very well. In alpha-beta search, one generally only searches partway to the end of a game, using numerical scores that have some heuristic intention but no precise mathematical definition beyond the scoring function they are computed by. In computer game programming, when one can search all the way to the end of the game, the scores that are used are instead simple win-loss-draw values, no longer susceptible to more complicated alpha-beta cutoffs. In CGT, on the other hand, the value of a position is well-defined mathematically, generally requires searching out to the end of the game to compute, and can't generally be handled by alpha-beta because not all values are comparable with each other. So while there's some connection, I think it's too tenuous (and would likely require too much original research) to say much about it. —David Eppstein (talk) 06:53, 18 December 2007 (UTC)

• Okay, it sounds like this is a different subject and should be left alone. Thanks, everyone. (The real problem I was having is that the lead article in Category:Game artificial intelligence (game artificial intelligence) does not connect at all with the articles in the category. It's about non-player characters in role-playing games. I now think the solution is to write a survey article about games and AI, and to retitle the existing article.) ---- CharlesGillingham (talk) 04:06, 20 December 2007 (UTC)

Checkers solved

Not long ago, checkers was solved [1]. I don't know enough about CGT to decide exactly how this should fit in the article, but at least it alters the bit about checkers not being solved.Cretog8 (talk) 13:07, 16 April 2008 (UTC)

Contributions?

Ok, so what exactly are the contributions of this field to the study of games, other than having come up with a name for itself? Neither extensive-form games/backward induction nor alpha-beta pruning (and similar algorithms) are mentioned here, and they obviously apply to the very same type of games. Tijfo098 (talk) 12:21, 21 March 2011 (UTC)

It is about defining algebraic values in generalized number systems that mathematically represent the possible outcomes of a game position. It is especially relevant to games such as nim or go or amazons in which the position tends to get split into several independent pieces and at each move a player can choose to move in only one of those pieces — then the mathematical value of the overall game can be calculated as a sum of the values of the separate pieces. —David Eppstein (talk) 13:55, 21 March 2011 (UTC)

I take it you haven't improved the lead because of COI or something (I saw the EL at the bottom). I see now that the contributions are in the unique analysis methods of the game tree. What is less clear to me is if constraint logic and the game complexity results are considered part of this or not. I'll do my best to summarize the stuff in the lead after I grok it at least "from the helicopter". Tijfo098 (talk) 23:42, 21 March 2011 (UTC)

Scoring Play Combinatorial Game Theory

Should we include a separate section on Fraser Stewart's new theory for Scoring Play Combinatorial Games? [2] This is new theory that was done in a PhD thesis and his papers are currently under review for Games of No Chance 5, but the thesis has been examined and has passed so is it ok to write a section about that now? — Preceding unsigned comment added by 92.2.128.176 (talk) 11:59, 30 March 2012 (UTC)

This sort of material is prohibited by Wikipedia policy for a number of good reasons. You will notice a conspicuous absence of millions of other dissertations like this one. Of course, WP can make exceptions for dissertations which have become famous over time, but this is not such a case. Rschwieb (talk) 02:16, 10 April 2012 (UTC)

Probably because the vast number of PhD theses consist of pointless drivel that's why. If there are "millions of other" theses like that one then I'd like to know where all these great mathematicians are. Care to show me all the other PhD theses that introduce their own brand new mathematical theory? Thought not, they don't exist. — Preceding unsigned comment added by 92.2.119.2 (talk) 20:12, 21 April 2012 (UTC)

Well it's good that you see that we can't admit a thesis automatically, and if you'd just apply that objective conclusion to this situation, you will understand why it's not a good idea to admit that thesis here. Time will tell if this thesis is drivel. It is not a WP editor's place (and even more certainly not the place of someone close to the author of the thesis!) to decide how important or reliable a certain thesis is. A thesis that is introducing a brand new theory is especially suspect as a resource, because there is so little material on the subject matter. Please help keep Wikipedia encyclopedic! Rschwieb (talk) 13:41, 23 April 2012 (UTC)

Big improvements; congratulations to all editors

I haven't been looking at this article for about six years; in the intervening time it has improved enormously. The idiosyncratic notation is all gone, replaced by the much more standard Berlekamp/Conway/Guy notation. This is outstanding work, and the current structure makes it possible to see ways to improve it still more. I'm going to thing about it for a while and then make a stab at it, but I just wanted to give credit where it's due. Wikipedia at its best, my friends.ACW (talk) 01:20, 22 April 2012 (UTC)

n-player CGT ?

Is formal CGT really limited to two players? There has to be a theory or category that includes combinatorial n-player games as well, at least as a theoretical possibility even if there is no active research in that direction. It is strange if one has to resort to general (non-perfect information) game theory in order to have more than two players. I think the possibility of more than two players needs to be commented in the article.

Chinese checkers is an example of a perfect-information strategy game for up to 6 players.

Anders Hallström 85.230.254.123 (talk) 13:01, 6 January 2013 (UTC)

Zero-sum?

It is not clearly stated whether combinatorial games are by definition zero-sum. All the examples are zero-sum games. What is the answer? References? In "Introducing Game Theory and its Applications By Elliott Mendelson" it is part of the definition (p.9 item 5). I'm not sure if this is the standard definition. Experts? sattath (talk) 18:58, 4 January 2014 (UTC)

Combinatorial games have a winner and a loser. They do not have a utility value. They are not part of the classical game theory in which zero-sum games are defined. Additionally, in the classical game theory, players both move simultaneously, and randomization is important, while in combinatorial game theory one player moves at a time and the optimal strategies are deterministic. So your question is meaningless. —David Eppstein (talk) 19:18, 4 January 2014 (UTC)

emphasis

The body of this article (though not the introduction) currently deals only with the Berlekamp-Conway-Guy style of combinatorial games (focusing on games where the winner is determined by who moves last, for example). Ideally the article should be reworked so that positional games can be discussed on the same level. Currently the introduction gives the general (in my view, correct) view of a combinatorial game (a game of complete information) but then, in the body, the presentation is based entirely on the Berkekamp-Conway-Guy style.

Otherwise, in its current form, I would suggest the article be renamed to something like "Additive theory of Combinatorial Games" or something like that.

Thoughts? Wpegden (talk) 18:39, 9 January 2015 (UTC)

Note that the title of the article is already Combinatorial game THEORY, not combinatorial games more broadly. So I think the emphasis on the theory of this sort of games, rather than positional games as a whole, is appropriate. —David Eppstein (talk) 21:14, 9 January 2015 (UTC)

Right, but the emphasis is currently only on the BCG-style THEORY of combinatorial games (tending to have an additive structure) and ignores the THEORY of positional games... this is what I think should be corrected. Wpegden (talk) 17:01, 12 January 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Combinatorial game theory/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

With some enhancement to the referencing, this is ready for GA nomination. Geometry guy 20:42, 9 June 2007 (UTC) The formal definitions and well-founded collections sections are currently very notation-heavy and consequently difficult to read; I think some improvement is possible there, and should be undertaken before GA nom. —David Eppstein 20:21, 10 June 2007 (UTC)

Last edited at 20:21, 10 June 2007 (UTC). Substituted at 01:54, 5 May 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Combinatorial game theory. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://www.webcitation.org/5oFLE7Mgx?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf to http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 04:17, 11 August 2017 (UTC)

Emphasis of Summing Games

From what I understand by reading various articles on the subject, what makes combinatorial game theory special is it's emphasis on combining games using the disjoint sum. Without understanding this many of the choices used in the theory to describe games seem very odd. The concept is mentioned and stated as being important, but it's not explained why it is important, and the subject itself is not linked to. I suggest this article be revised to better emphasize the rule of the disjoint sum. — Preceding unsigned comment added by 128.187.83.26 (talk) 05:58, 13 February 2020 (UTC)

You did see the part in the History section of the article (the first section after the lead) where it says

One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure.

John Conway states in ONAG that the inspiration for the theory of partisan games was based on his observation of the play in go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

Right? In what way do the parts about rich structure and play in go endgames not explain why this is important? —David Eppstein (talk) 07:30, 13 February 2020 (UTC)