I’ve only just become interested in this domain, so sorry if I’m not using the correct terminologies.
What I want is the following: Say I have a set of rules (or constraints), I want to derive some implications of those rules.
For example, in Conway’s Game of Life, there are 4 basic rules. From these rules, we can see a few patterns emerge. I want a system in which I can input the rules (in some formal language), and it would output at least some of these patterns. Also, if I make a change in any rule, or add a new rule, it should show me the implication of this change (or I should be able to derive it myself from comparing the two outputs).
This should ideally apply to any game that has a set of rules. For example in chess, it should say that the knight can move two squares in front of it by performing two L moves. In checkers it could be that having a piece behind another prevents the other playing from taking that piece.
Has anything like this ever be made? Is it even feasible? Can you recommend any courses or books where I could start my (re)search?
All I’ve found so far are Automated Theorem Provers, but from what I can tell so far, they are way too generic and mathematically oriented (they aim to solve any theory in maths, which has a lot of rules, I just want it for simple games with a small number of rules).
6
Consider General Game Playing. The idea is to write a program that performs well playing any game that can be formally described. So you don’t create a tic-tac-toe program or checkers program or Reversi program. You create a program/agent that can play all of these games with the best general performance.
The steps of a GGP session are:
- The game server delivers a formal description of the game. This includes number of players, initial state, and valid rules.
- Each player has some time to process the rules.
- The game starts. The game server calls for a move from each player in proper turn order.
- As players submit moves, the game server validates that the moves are legal and either accepts or rejects them.
- Play continues until a player wins.
Obviously, this doesn’t all apply directly to the problem you describe, but the underlying principles are the same. Given some set of rules and an initial state, decide the valid transitions from state to state to state. Michael Genesereth and Michael Thielscher go into detail in their General Game Playing online book.
Your Conway’s Game of Life example could be described as a single player game that has no winning state. It runs forever. You’d have to decide when to stop “playing”. Chess fits very well in the GGP model, though it’s obviously a game with a fairly large state space. Take a look at Tiltyard’s game list to get an idea of the variety of games being played by the GGP community.
There’s also a very fun General Game Playing Stanford course and an online community that includes starter kits for developing players and a free General Game Playing server.
4
To me it sounds like you have a state of a system (a chess board, a game of life board), set of state transformations (given state A, state B is an output). Then you have a state (starting chess board) and want to get all following states for each state transformation, possibly for multiple steps.
Bruteforcing this is primitive. But the amount of states that you get as output gets overwhelming really fast, so I fail to see any useful application.
AI for those games is usually about searching the state space.
2