2

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).

| improve this question | |
  • recommended reading: Where to start? – gnat Jan 5 '16 at 9:52
  • 2
    "...I can input the rules (in some formal language), and it would output at least some of these patterns." So... a normal rules engine, then? – Kilian Foth Jan 5 '16 at 9:55
  • 2
    The problem here is not the the implementation of rules, this can be done either by implementing them conventionally, or by utilizing some kind of rules engine (see martinfowler.com/bliki/RulesEngine.html). The problem is it is totally unclear what "output some of these patterns" or "derive implications" means. For example, take the rules for "chess" or "checkers" - what patterns or implications do you expect to be found from them? The task is not even clear when trying to do this manually, so how do you expect a computer program to do this? (Voting to close as "too broad"). – Doc Brown Jan 5 '16 at 10:16
  • "take the rules for "chess" or "checkers" - what patterns or implications do you expect to be found from them? " one example I could think of is that, for example in chess, 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. How do you suggest I make those terms more clear? – Nini Michaels Jan 5 '16 at 10:26
  • This is a massive area so I think this may be closed due to its breadth. But you might want to look at heuristics and Fermi calculations – Robbie Dee Jan 5 '16 at 10:50
7

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:

  1. The game server delivers a formal description of the game. This includes number of players, initial state, and valid rules.
  2. Each player has some time to process the rules.
  3. The game starts. The game server calls for a move from each player in proper turn order.
  4. As players submit moves, the game server validates that the moves are legal and either accepts or rejects them.
  5. 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.

| improve this answer | |
  • I miss to see how this can help the OP to answer his question "I want a system [...which] would output at least some of these patterns.". As I wrote in my comment, what makes this question unanswerable is not the part about the rules (the input to the system), it is the (unclear) part about the output. – Doc Brown Jan 5 '16 at 13:42
  • 2
    @DocBrown I'm focusing more on the word "implication". If I had to guess, the OP is still honing in on what exactly they're after. This question has a 100% chance of being closed. I just figured I'd offer an introduction to a very interesting and relevant practice before it's closed. Conceptually, GGP does exactly what the OP describes minus the output. Given that we're talking about highly dynamic systems, the "output" is not going to be what the OP expects. GGP is a fun and interactive way to explore and discover how these systems work. It will allow the OP to adjust their expectations. – Scant Roger Jan 5 '16 at 14:09
  • Ok, I guess that might be the best possible way to give an answer to an otherwise unanswerable question ;-) You get my upvote. – Doc Brown Jan 5 '16 at 14:22
  • You gave me a starting point, thank you for that. I will begin my research here and will possibly come back when I have a clearer picture of what I want. – Nini Michaels Jan 5 '16 at 21:01
2

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.

| improve this answer | |
  • From the "game of life" example, it is IMHO clear that is not what the OP is after. He seems to be interested in a program which can imitate the "pattern finding capabilities" of the human brain. – Doc Brown Jan 5 '16 at 11:57
  • 1
    @DocBrown But then, he writes "(or I should be able to derive it myself from comparing the two outputs)". So he may be fine with just seeing possible outputs. Maybe? – Euphoric Jan 5 '16 at 11:58

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