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?
Asked
Active
Viewed 1,846 times
7
-
A vague guess is that applications are more in AI than "theory" as we usually think of it... – usul Jul 02 '15 at 01:07
-
9You seem to assume that computer scientists study a topic mainly because it has applications, which is false. – Kaveh Jul 02 '15 at 04:03
-
1Indeed, one of the first books in combinatorial game theory (Surreal Numbers by Knuth) explicitly praises its lack of applications. – Christopher King Nov 19 '15 at 13:02
3 Answers
11
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.
David Eppstein
- 50,990
- 3
- 170
- 278
-
1Nim-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. – Christopher King Nov 19 '15 at 13:04
-
But, isn't considering biwise XOR as something that came out of CGT, a bit far fetched? Anyway, I like your answer. – Cyriac Antony Oct 24 '18 at 06:42
