5 ms·

A Python AI for two-player board games

57 points by rubinelli 13y ago

dangoldin 13y ago
Oh nice. Reminds me of a hackathon I did a while back where I tried to implement a connect 4 AI bot using a genetic programming approach. Here's the code: https://github.com/dangoldin/connect4bot https://github.com/dangoldin/connect4bot And here's a writeup: http://dangoldin.com/2013/11/30/genetic-programming-connect-4/ http://dangoldin.com/2013/11/30/genetic-programming-connect-...
Ihmahr 13y ago
Why didn't you go for monte carlo tree search? Wouldn't that have been more robust to handle different games?
- gamegoblin 13y ago
  Negamax is very good for a wide variety of relatively simple games. It will utterly fail for Go, but I've written negamax AIs that dominate any casual player at chess, connect 4, reversi, gomoku, etc. They become yet stronger if you add a quiescence search.
mattr555 13y ago
Finally, we can play WarGames in Python http://zulko.github.io/easyAI/examples/games.html http://zulko.github.io/easyAI/examples/games.html
jpoulter 13y ago
This looks like a really tidy framework for this class of general games (http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing). There's actually an annual competition for this type of thing. In this competition game rules are described using a language called GDL (http://en.wikipedia.org/wiki/Game_Description_Language http://en.wikipedia.org/wiki/Game_Description_Language). Broadly there are two approaches. Super fast Monte-Carlo tree searches and algos which, from rules, infer game-state heuristics which are used in more traditional depth-limited search.
- mrcactu5 13y ago
  there was a Coursera course on GGP this fall: General Game Playing: https://www.coursera.org/course/ggp https://www.coursera.org/course/ggp they were using java/javascript for their players. And there were other issues making their framework a little bulky
sehugg 13y ago
Very nice, the examples are very clear and terse. I started on a similar project in C which is unique in that the game logic is written more-or-less procedurally and the library takes care of backtracking the game state to iterate through the tree nodes: https://github.com/sehugg/Starthinker https://github.com/sehugg/Starthinker

57 points by rubinelli 13y ago

Oh nice. Reminds me of a hackathon I did a while back where I tried to implement a connect 4 AI bot using a genetic programming approach. Here's the code: https://github.com/dangoldin/connect4bot https://github.com/dangoldin/connect4bot And here's a writeup: http://dangoldin.com/2013/11/30/genetic-programming-connect-4/ http://dangoldin.com/2013/11/30/genetic-programming-connect-...

Ihmahr 13y ago

Why didn't you go for monte carlo tree search? Wouldn't that have been more robust to handle different games?

gamegoblin 13y ago
Negamax is very good for a wide variety of relatively simple games. It will utterly fail for Go, but I've written negamax AIs that dominate any casual player at chess, connect 4, reversi, gomoku, etc. They become yet stronger if you add a quiescence search.

mattr555 13y ago

Finally, we can play WarGames in Python http://zulko.github.io/easyAI/examples/games.html http://zulko.github.io/easyAI/examples/games.html

jpoulter 13y ago

This looks like a really tidy framework for this class of general games (http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing). There's actually an annual competition for this type of thing. In this competition game rules are described using a language called GDL (http://en.wikipedia.org/wiki/Game_Description_Language http://en.wikipedia.org/wiki/Game_Description_Language). Broadly there are two approaches. Super fast Monte-Carlo tree searches and algos which, from rules, infer game-state heuristics which are used in more traditional depth-limited search.

mrcactu5 13y ago
there was a Coursera course on GGP this fall: General Game Playing: https://www.coursera.org/course/ggp https://www.coursera.org/course/ggp they were using java/javascript for their players. And there were other issues making their framework a little bulky

sehugg 13y ago

Very nice, the examples are very clear and terse. I started on a similar project in C which is unique in that the game logic is written more-or-less procedurally and the library takes care of backtracking the game state to iterate through the tree nodes: https://github.com/sehugg/Starthinker https://github.com/sehugg/Starthinker