11
$\begingroup$

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they do not form a set but a class).

See for instance this pdf or Wikipedia for an introduction.

They can be even more generalized to so-called "games", which are originally introduced to study combinatorial games. The original motivation of Conway was to analyze the game of Go, in particular the endgame is especially suited to be modeled with "surreal games".

My question is: do you know if anybody has implemented this approach in an AI (i.e. computer player) to improve its level at a game? I am especially interested in the case of Go, but others as well. If not, is there an obstacle or a reason why it would not be a good idea?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ According to the book "Mathematical Go", it seems there used to be a companion program by Raymond Chen for solving the endgame problems in the book, but I do not know where it can be found. I also have a vague memory of Berlekamp referencing "Go explorer", which might be mentioned in the paper "Smart game board and go explorer: a study in software and knowledge engineering". I do not think combinatorial game theory is really used in the top Go playing programs at this time, though. $\endgroup$
    – Mark S.
    Nov 22, 2015 at 21:17
  • 3
    $\begingroup$ If I recall correctly (maybe not as it was a long time ago), according to David Wolfe (co-author of Mathematical Go), one can concoct Go end-game positions where top professional players tend to play non-optimally by as much as a point, whereas the Conway/Berlekamp/Wolfe game-theory approach allows one to compute the optimum relatively easily. However, such positions are contrived. This phenomenon is rare in games that arise in real play. $\endgroup$
    – Neal Young
    Jul 6, 2018 at 21:00

3 Answers 3

Reset to default
8
$\begingroup$

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here). It includes an implementation of various standard operations on Conway games in canonical form, as well as a scripting language for describing new games.

Improve this answer
$\endgroup$
3
+50
$\begingroup$

on some search there do not seem to be much published general implementations of surreal numbers. heres an implementation of surreal numbers in coq.

  • Surreal numbers in coq / Mamane, TYPES'04 Proceedings of the 2004 international conference on Types for Proofs and Programs

    Surreal Numbers form a totally ordered (commutative) Field, containing copies of the reals and (all) the ordinals. I have encoded most of the Ring structure of surreal numbers in Coq. This encoding relies on Aczel's encoding of set theory in type theory.

    This paper discusses in particular the definitional or proving points where I had to diverge from Conway's or the most natural way, like separation of simultaneous induction-recursion into two inductions, transforming the definition of the order into a mutually inductive definition of “at most” and “at least” and fitting the rather complicated induction/recursion schemes into the type theory of Coq.

there are some part-implementations of surreal arithmetic for a game called hackenbush (Davis) popularized by Conway, Berlekamp, and Guy of which there are a few references.

Go is indeed one of the leading edge areas of game AI research (considered significantly harder than chess which occupied AI for decades) but it appears there is little research specifically into using surreal numbers to model/ play it. Go is considered a frontier for machine learning/AI algorithms because it also has a relatively unique status/ distinction in that the best software based algorithms ("still/ currently") do not outperform champion human players.

see this ref The Mystery of Go, the Ancient Game That Computers Still Can’t Win (Wired mag) for a decent rough survey of current Go AI techniques/ researchers/ leads.

Improve this answer
$\endgroup$
2
$\begingroup$

Here is an implementation of Surreal Numbers in a relatively new language, Julia. https://github.com/mroughan/SurrealNumbers.jl

Described at https://www.sciencedirect.com/science/article/pii/S2352711018302152

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.