Talk:Combinatorial game theory

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: A-BB+ Class Mid Priority  Field: Discrete mathematics

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.

Contents

[edit] 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)

[edit] 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)

[edit] 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.

[edit] 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.

[edit] "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)

[edit] 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)

[edit] 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)

[edit] 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)