4 ms·

Pretty cool. I once wrote a C++ program to play me in chess. It was ~5000 lines of code! I can appreciation this script. I think a more interesting problem now

by jostmey 12y ago

Pretty cool. I once wrote a C++ program to play me in chess. It was ~5000 lines of code! I can appreciation this script. I think a more interesting problem now is to create computer algorithms that can be "taught" the rules of a board game --- a problem that falls squarely in the domain of supervised learning. In the studies I've found, the algorithms were provided with a lot of prior knowledge about the specific board game, so there may be a lot of room for progress.

dmichulke 12y ago
There are approaches. One is General Game Playing where the rules are given as a set of logic formulas that basically describe a state machine http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing http://www.general-game-playing.de/literature.html http://www.general-game-playing.de/literature.html GGP is then about deriving knowledge about the game and its state evaluation using a) the rules directly, b) the represented state tree or c) past matches in that very game. The other one I know of is a mechanism where you use reinforcement learning and assume one state in the beginning. With more info, you start splitting the state into several states using decision tree split criteria, such as cross entropy, and you end up obtaining a game state tree together with the knowledge to play reasonably well. Problem: I don't remember how it's called.
Yen 12y ago
You might be interested in 'General Game Playing'. The idea is that players are presented with a machine-readable description of game rules (in a prolog-like locigal language), and they then play the game. Since you can't use human-tuned heuristics for every game, you have to use more general meta-heuristics. There's also a lot of room for logically parsing the game, and trying to separate out individual components, obviously meaningless moves, etc. see http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing or https://www.coursera.org/course/ggp https://www.coursera.org/course/ggp an example game: http://ggpserver.general-game-playing.de/ggpserver/public/view_game.jsp?name=tictactoe http://ggpserver.general-game-playing.de/ggpserver/public/vi... it basically defines an initial game state, the moves each player can make and how they alter the game state, and the end-conditions and goals of the game.

by jostmey 12y ago

dmichulke 12y ago

There are approaches. One is General Game Playing where the rules are given as a set of logic formulas that basically describe a state machine http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing http://www.general-game-playing.de/literature.html http://www.general-game-playing.de/literature.html GGP is then about deriving knowledge about the game and its state evaluation using a) the rules directly, b) the represented state tree or c) past matches in that very game. The other one I know of is a mechanism where you use reinforcement learning and assume one state in the beginning. With more info, you start splitting the state into several states using decision tree split criteria, such as cross entropy, and you end up obtaining a game state tree together with the knowledge to play reasonably well. Problem: I don't remember how it's called.

Yen 12y ago

You might be interested in 'General Game Playing'. The idea is that players are presented with a machine-readable description of game rules (in a prolog-like locigal language), and they then play the game. Since you can't use human-tuned heuristics for every game, you have to use more general meta-heuristics. There's also a lot of room for logically parsing the game, and trying to separate out individual components, obviously meaningless moves, etc. see http://en.wikipedia.org/wiki/General_game_playing http://en.wikipedia.org/wiki/General_game_playing or https://www.coursera.org/course/ggp https://www.coursera.org/course/ggp an example game: http://ggpserver.general-game-playing.de/ggpserver/public/view_game.jsp?name=tictactoe http://ggpserver.general-game-playing.de/ggpserver/public/vi... it basically defines an initial game state, the moves each player can make and how they alter the game state, and the end-conditions and goals of the game.