6
$\begingroup$

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are there some applications of it? This question is similar to this one but I am asking about combinatorial games such as nim. Could someone provide me with a reference?

$\endgroup$
  • $\begingroup$ A vague guess is that applications are more in AI than "theory" as we usually think of it... $\endgroup$ – usul Jul 2 '15 at 1:07
  • 9
    $\begingroup$ You seem to assume that computer scientists study a topic mainly because it has applications, which is false. $\endgroup$ – Kaveh Jul 2 '15 at 4:03
  • 1
    $\begingroup$ Indeed, one of the first books in combinatorial game theory (Surreal Numbers by Knuth) explicitly praises its lack of applications. $\endgroup$ – PyRulez Nov 19 '15 at 13:02
10
+50
$\begingroup$

I think Kaveh's comment is the correct answer: applications? We don't need no applications.

But despite all that, combinatorial game theory does appear to have some applications in error correcting codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986.

More simply, if you are willing to think of nim-addition (bitwise exclusive or) as something that came out of combinatorial game theory, then there are plenty of applications, for instance in tabulation hashing, or as one of the components of Schieber and Vishkin's lowest common ancestors data structure, or as one of the components of some block cipher systems.

$\endgroup$
  • $\begingroup$ Nim-addition gives a nice definition of exclusive or that does not depend on binary representation. It is introduced only with a game involving natural numbers in mind, no binary required. $\endgroup$ – PyRulez Nov 19 '15 at 13:04
  • $\begingroup$ But, isn't considering biwise XOR as something that came out of CGT, a bit far fetched? Anyway, I like your answer. $\endgroup$ – Cyriac Antony Oct 24 '18 at 6:42
3
$\begingroup$

I was able to find an application of combinatorial game theory in cryptography. See the link here

$\endgroup$
1
$\begingroup$

Combinatorial game theory and topics thereof has received a lot of attention in modelling and verification of reactive systems. I would draw your attention to this nice reference for more information.

$\endgroup$
  • 2
    $\begingroup$ Which combinatorial games have you got in mind? $\endgroup$ – Martin Berger Aug 18 '15 at 6:38

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.