Robert'); DROP TABLE *; wrote: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;
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;
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);
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.