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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ A vague guess is that applications are more in AI than "theory" as we usually think of it... $\endgroup$– usulJul 2, 2015 at 1:07
-
9$\begingroup$ You seem to assume that computer scientists study a topic mainly because it has applications, which is false. $\endgroup$– KavehJul 2, 2015 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$– PyRulezNov 19, 2015 at 13:02
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Aug 17, 2015 at 4:53
-
1$\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$– PyRulezNov 19, 2015 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$ Oct 24, 2018 at 6:42
$\begingroup$
$\endgroup$
I was able to find an application of combinatorial game theory in cryptography. See the link here
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ Which combinatorial games have you got in mind? $\endgroup$ Aug 18, 2015 at 6:38