Self-modifying expert systems?

[Robert'); DROP TABLE *;]

I'm not sure an expert system is the right term for what I want to do, but bear with me.

I'm looking to build a chess-playing AI based on logical reasoning and deduction from knowledge. Specifically, it has some conception of "This is a good/bad idea because..." as opposed to the neural net models, which AFAIK don't. However, in the grand scheme of things, I'm a rubbish chess player, so the AI has to have some method to update its knowledge base. This is the part I'm stuck with; I've absolutely no idea how the program could infer new rules about how to play chess based purely on previous results. I don't know if anyone has tried this before, how far they got, or even if it's possible at all.

I can has help, please? Does anyone have any articles or know of books about this sort of design, or know somewhere else I could go for more information?

(Thanks in advance)

[mfb]

I think that this task is extremely tricky. Imagine a program which can learn how to play (good) chess with just the rules as input: It could learn a lot of games without large modifications. And not even games: If the program is able to modify its own strategies based on learning and without any limitations given by the programmer, it could learn nearly everything. It could become a really powerful AI, not limited to board games.
And as you might guess, no such program (with reasonable CPU requirements, e.g. some years on a supercomputer) exists up to now, or it is stuck in a box.

tl;dr-version: I think you have to give the program at least some ideas how to play chess: Tell the program that losing figures is usually a bad idea (while the program might determine how bad it is for some figure within the current situation), that it is good to have a figure which can reach other figures, that a search through the list of possible next moves (and next to next moves and so on) is a good idea, ...

[WarDaft]

Well, one very basic way to define AI is to simply have a search which uses, as a heuristic, a simplified version of the same game. Implement the game as a series of tree constraints, and the game just removes one of the constraints and uses the simpler game to predict the value of the move. Over time the program could evaluate which constraints lead to better performance under which circumstances, and so develop a meta-heuristic for heuristic choosing.

But it's still not going to get any smarter than you initially programmed it to be. It's still in the category of a game AI rather than a learning AI.

[freakish777]

I'm not sure an expert system is the right term for what I want to do, but bear with me.

I'm looking to build a chess-playing AI based on logical reasoning and deduction from knowledge. Specifically, it has some conception of "This is a good/bad idea because..." as opposed to the neural net models, which AFAIK don't. However, in the grand scheme of things, I'm a rubbish chess player, so the AI has to have some method to update its knowledge base. This is the part I'm stuck with; I've absolutely no idea how the program could infer new rules about how to play chess based purely on previous results. I don't know if anyone has tried this before, how far they got, or even if it's possible at all.

I can has help, please? Does anyone have any articles or know of books about this sort of design, or know somewhere else I could go for more information?

(Thanks in advance)

Sorta, you'd very likely need to get very specific (to Chess/your problem) with how you evaluate positions (or whatever is being evaluated).

Your basic AB-Minimax (or Negascout) algorithm that determines what move to make from a given board state, at some point hands off positions (not the current one, but one 6 moves deep) to an Evaluation/Cost Heuristic (or set of formulas to determine utility).

You could then have a Genetic Algorithm update the values that your Heuristic returns after every X games it plays.

For instance, if your piece Evaluation formula is something like:

Code: Select all

//The board string represents the current board, the position string represents position, like C5, note that in real life, you want to make as efficient as possible (evaluating millions of positions that
//are 6 moves deep, so you're going to optimize this to the point of unreadability, and all your objects are going to become base types, chars, ints, strings
float PieceEval(Piece p, Board b)
{
   float baseValue = 0.0;
   float retVal = 0.0;

   switch(p.type):
      case 'Pawn': baseValue = 1; break;
      case 'Knight': baseValue = 2.75; break;
      case 'Bishop': baseValue = 3; break;
      case 'Rook': baseValue = 5; break;
      case 'Queen': baseValue = 9; break;
      case 'King: baseValue = 3.5; break;
      default:  Throw Exception.UnkwnownPieceType; break;


     retVal += baseVal + (numberOfMovesAvailableToPieceAtPosition(b, p.position) * baseValue * 0.02);
     retVal -= DistanceFromCenterOfBoard(p.position) * 0.01;
     retVal += b.NumberOfEnemyPiecesBeingAttacked(p.position) * 0.03;
     
     return retVal;
}


float BoardEval(board b, bool WhitePlayer)
{
      float retVal = 0.0
      foreach(Piece p in PieceList(board, WhitePlayer))
      {
            retVal += PieceEval(p.type, b, p.position);
      }

      retVal -= (b.NumberOfStackedPawns(WhitePlayer) * 0.5);
      retVal += (b.AreRooksBatteried(WhitePlayer) * 0.25);   //http://en.wikipedia.org/wiki/Battery_(chess)
      retVal += (b.NumberOfPiecesThreateningOpponentKing(WhitePlayer) * 0.3);
     
      <etc>

      return retVal;
}



So instead of hardcoding those values, you're instead loading them once when you first initialize your program from a config file, and your GA is updating them after X games your AI has played.


Unfortunately, the "This move is good because X, Y and Z" though would basically result in "because it puts me up by 0.457 evaluation points in comparison to my opponent" unless you made it very verbose in which case you're still left with "because my knight on C5 is worth 2.6785, and it's valued at that because it has 6 moves available to it, two of which currently attack opponent pieces. <repeat for each piece you have on the board>, there's also a positional advantage of 0.4532, which is because my Rooks are Batteried, I have no stacked pawns, 2 of my pieces Threaten my opponent's King while my king is safe, <etc>."

So, you're looking at either a very strong AI, that is capable of learning much more than just Chess to tell you why it made that move, or you're looking at your heuristic being very detailed (having an expert understanding of the problem domain to begin with) and then finding a way to tune it's verbosity to be just right ("because that move prevented my opponent from being able to fork my king and my rook next turn, and that would would have resulted in an insurmountable loss of pieces").

I do know there's some Chess Engines out there (I want to say it's Rybka) that do something similar to the "Why" part in an attempt to help professional players.

[Jplus]

I recommend reading a good introductory book on (technical) artificial intelligence in general. It will inspire you and help you to find further information on this type of problem and many others. You could, for example, take Artificial Intelligence: A Modern Approach by Russell & Norvig.

[freakish777]

After digesting AIMA (as Jplus suggested), I would further recommend:

Neuro-Fuzzy And Soft Computing and Applying Case-Based Reasoning

[Robert'); DROP TABLE *;]

Unfortunately, the "This move is good because X, Y and Z" though would basically result in "because it puts me up by 0.457 evaluation points in comparison to my opponent" unless you made it very verbose in which case you're still left with "because my knight on C5 is worth 2.6785, and it's valued at that because it has 6 moves available to it, two of which currently attack opponent pieces. <repeat for each piece you have on the board>, there's also a positional advantage of 0.4532, which is because my Rooks are Batteried, I have no stacked pawns, 2 of my pieces Threaten my opponent's King while my king is safe, <etc>."

So, you're looking at either a very strong AI, that is capable of learning much more than just Chess to tell you why it made that move, or you're looking at your heuristic being very detailed (having an expert understanding of the problem domain to begin with) and then finding a way to tune it's verbosity to be just right ("because that move prevented my opponent from being able to fork my king and my rook next turn, and that would would have resulted in an insurmountable loss of pieces").

Oops, I hadn't thought of that. What I was looking for was a way to avoid the magic numbers involved in neural net evolution, since evolving ANNs basically gives you the same meaningless-but-working result that RL evolution does. I forgot that the "meaning" it assigns will be in terms of an evaluation function that's not going to be meaningful to me. There isn't really a cheap way around that, is there?

Well, one very basic way to define AI is to simply have a search which uses, as a heuristic, a simplified version of the same game. Implement the game as a series of tree constraints, and the game just removes one of the constraints and uses the simpler game to predict the value of the move. Over time the program could evaluate which constraints lead to better performance under which circumstances, and so develop a meta-heuristic for heuristic choosing.

But it's still not going to get any smarter than you initially programmed it to be. It's still in the category of a game AI rather than a learning AI.

Could you expand on this? It sounds like what I'm going for, but I'm not entirely sure how removing constraints, rather than adding them, makes the game simpler to evaluate. (And also, a learning AI is really what I'm looking for. Why wouldn't this model get better as it played?)

[WarDaft]

The easiest example I can think of is actually copy and pasted from the Stanford AI course.

You know the X by Y grid of sliding tiles with one missing to asking you to solve a picture puzzle? The constraints are to move a tile to an empty square, and move tiles to adjacent squares. If you satisfy both, then you only have the vertical/horizontal movement of tiles to empty squares typical of the puzzle. If you satisfy only one or the other, you lead to a problem which tends to be (but is certainly not always, hence the idea of meta-heuristics) as much as a constant factor smaller in the number of moves required, which results in an enormous reduction in the overall size of the search space. If you can swap any two tiles at any point, then a 4x4 puzzle can have no more than 15 possible moves. Otherwise, you could have a search space of up to 4^80 (the maximum length of a 4x4 puzzle is 80 moves) which is intractable to exhaustively explore.

It is also not necessarily tractable to be able to identify which of the constraints are valuable to discard, and which are not, statistically. You would need many degrees of approximation for any practical attempts.

The model would get better as it played, but still only because it is iterating on a series of probabilities. These probabilities are much easier to tie directly to actual properties, but still, it is not developing any new methods of reasoning that were not initially presented. The initial identification of the problem specifies all of the strategies the AI might choose to enact, the AI only (potentially) develops a method of determining which set of strategies lead to the highest wins/calculations of the ones specified.

[freakish777]

Oops, I hadn't thought of that. What I was looking for was a way to avoid the magic numbers involved in neural net evolution, since evolving ANNs basically gives you the same meaningless-but-working result that RL evolution does. I forgot that the "meaning" it assigns will be in terms of an evaluation function that's not going to be meaningful to me. There isn't really a cheap way around that, is there?

After thinking about it for a little bit, I think what you'd want to do is keep a list of the top X (let's say 3?) moves considered.

Then when you're giving a reason, you could compare the differences (as opposed to the similarities) between the moves (so Knight on C5 worth 2.75 and Knight on C5 worth 2.75 doesn't get anything said about it, where positional advantage of the board with King on C1 after a queen side castles worth 3.45 vs positional advantage of the board with King on E1 worth 2.45 gives "I moved here to increase the number of moves available to my rook and to move my king away from my opponent's pieces").

Another thing to keep in mind, a move might have a worse evaluation in the here and now, but a better evaluation 6 moves deep (or more likely, the reason is 6 moves deep). This makes giving a reason more complicated. You probably want to display the line of play being considered. You probably want to avoid giving the reason that's X moves deep unless absolutely necessary (as it isn't exactly helpful for most people, most people don't do minimax in their heads and think of the game as "what features of the current position make it a good one or a bad one for me to be in?").