3 ms·
Sharing other people's amazement that such a tiny amount of code plays so well (I'm an inexperienced, infrequent player and it beat me once and drew once), I wa
by schoen 6y ago
Sharing other people's amazement that such a tiny amount of code plays so well (I'm an inexperienced, infrequent player and it beat me once and drew once), I was pondering that there's no absolute reason to think that small programs inherently must play games poorly. For many abstract strategy games, you could write an explicit game tree search in a relatively small amount of code and it would, in principle, play perfectly if you somehow gave it enough time to search the whole game tree. (That wouldn't be feasible for most abstract strategy games that human beings like to play, but would for small games like Tic-Tac-Toe, Hexapawn or Octapawn, Nine Men's Morris, maybe Hex on a small board.)
In GOFAI (https://en.wikipedia.org/wiki/Symbolic_artificial_intelligence https://en.wikipedia.org/wiki/Symbolic_artificial_intelligen...) there's a clear pattern where "intelligence" in abstract strategy games represents, in part, being able to prune game trees well without having to search them exhaustively. In some cases that means having a good evaluation function for positions, and in other cases having a cleverer search strategy in another way.
Thinking about this made me realize that it's not just impressive that this program plays decently while being tiny, but especially that it plays decently and quickly while being tiny.
- SilasX 6y ago>Thinking about this made me realize that it's not just impressive that this program plays decently while being tiny, but especially that it plays decently and quickly while being tiny. Yeah I wonder if there are subfields of chess programing that optimize for that, something like "quality of engine per unit code size".
- kuroguro 6y agoSomewhat related: I was blown away when I first heard the argument that intelligence is basically compression. http://prize.hutter1.net/hfaq.htm#compai http://prize.hutter1.net/hfaq.htm#compai Haven't done any more digging into this but it did give me something to ponder about.
- schoen 6y agoI've heard of the Kolmogorov complexity connection, but I'm not sure I've seen it spelled out as explicitly as this before. Definitely very interesting!
- Someone 6y ago“but would for small games like […] Nine Men's Morris” http://library.msri.org/books/Book29/files/gasser.pdf http://library.msri.org/books/Book29/files/gasser.pdf: “We describe the combination of two search methods used to solve Nine Men’s Morris. An improved retrograde analysis algorithm computed endgame databases comprising about 10¹⁰ states. An 18-ply alpha-beta search then used these databases to prove that the value of the initial position is a draw” So they built a database containing all all 7,673,759,269 possible positions in the endgame phase (i.e. after all stones are on the board), and then did a full-depth search for the “place stones” phase. Paper is from 1996, so one might think current hardware could do a full search, but they show (page 10/110) a position with “White to move and win. Mill closure in 187 plies.” So, I don’t think this game is small enough to search the full tree. They made it small by first creating an endgame database with 7,673,759,269 endgames, but that database requires over a gigabyte of data (“The hash function we decided to use maps the 7,673,759,269 states into a range of 9,074,932,579 indices.”)
- schoen 6y agoThanks for the information! That game is definitely bigger than I thought. (I knew it was solved, but I'd wrongly imagined it was solved by complete game tree search.)