Hi! I have thought of making some implementation of AI in chess (in the evaluation function), based on some form of artificial programming, maybe trial and error. First I thought of making one which uses Lisp, but then I thought that I should better check before if there is any better suited language, some that is more often used today than Lisp is... Do you know which language is most often used, or which is the best to use? If Lisp, which dialect should I use, CL or Scheme? And since I am new to AI and artificial programming, is there any good articles I should read about it before I give it a try? I know the basics of genetic programming, but I don't really see why I should keep more than one AI generated program at the same time when they probably will work in about the same way, at least not in this case. By the way, I read a book before sometime which contained a chapter about a computer or a computer program (don't know which) called Eurisko (you can see http://en.wikipedia.org/wiki/Eurisko). Ever heard of it? I think that used Lisp too, or at least something similar. That computer achieved some amazing things! Does anyone know how it worked? It would be really awesome if my program could do about the same thing!

LISP has historically be considered The Language For AI, because its history and the history of early Natural Language Processing are deeply linked. Don't read too much into that, though. There is very little specific to AI which is uniquely well handled by LISP. I'll let others weigh in on the LISP variant war.

You should look into minimax, alpha-beta pruning, and transposition tables. Don't be seduced by the buzzwordiness of genetic algorithms and ANNs. They are not a panacea.

Eurisko is a cool technology, but it's probably not particularly applicable to chess, since (IIRC) it has limited formal look-ahead ability. I could be wrong about this, though.... I haven't really looked at it in a while.

Not to be trite, but this is similar to asking "what is the best language for writing song lyrics?" The best programming language for AI is the one that the rest of your application speaks. If you are going to be writing the rest of your stuff in C++, why bother with LISP? If you are going to be coding in Java, why would you use VB? Exceptions to this are things that are designed to go together such as Lua plugins to C++.

General AI concepts are highly language-independent. Use whatever you are comfortable with that is capable of supporting what you need to do. (e.g. if you need recursion or flexible container classes, then the language must support those)

Thanks. I know about alpha-beta pruning, and also about transposition tables. I am going to use these too. Well, I look at this project more as an attempt to create something that is creative, that can come up with ideas about what a good position should look like. If it is possible to do it at all with artificial programming.

I have an idea of how this can be done:

I start by creating a very basic evaluation function of course (which will make the program able to play a somewhat reasonable game that is not totally random). Then a number of random but common game positions (maybe from past games or the previously played one) is taken. All of these positions will have their own values, given by the estimation function.

However, these values are just estimations of the current state of the game (which player has the advantage and how big), and we want them to be better. And that is achieved by looking several moves ahead, although looking only a few moves ahead will also improve the estimations. So, every position is given a new value, taken from looking one or two moves ahead (depending on if it necessary that it is the same players turn again, or not), using min-max or alpha-beta pruning (these values can act as "true values", for example if a neural network and backpropagation would have been used instead). It is probably also possible (it should be in some way) to try to make small modifications of the evaluation function, to better match the new values. If such a modification is found, it is applied to the evaluation function. This is however only a method for improving the evaluation method, then it is used as normal when a real game is played.

Does this make sense at all?

Otherwise, it could just try modifying the code a little bit and play one or a few games against the old code, to see if it improved.

The reason I asked about what language to use is that I want to find an easy language to implement it in. With Lisp for example requires quite little (I guess) to write the interpreter (and also the code generator) in comparison to if other, more complex languages like C, or worse, C++, are used. The generated program still has to be able to perform well though.

If you have no idea where to start, Python. If you want to get into industry, C++. :-)

This is potentially an interesting project. The best attempt at this kind of thing I've seen was some paper in the early 90s where they converted positions into graphs (where a link represents a piece attacking a square) and then trying to automatically generate a database of useful patterns with associated values. The evaluation function would then consist of identifying the patterns that might be present and adding their values up.

Another, more limited approach was KnightCap, which used TD learning to auto-tune parameters in its evaluation function.

The tough part about this is what algorithm to use, not what language to express it in. I would do it in C++ because that's what I am more used to, but you can use anything else.

I have never heard about C++ script before. Is it common to use it? I have heard that C++ is a very difficult language to parse, if you compare it to for example C. That is if you are going to use classes, templates and polymorphism of course, but what good is it without all that?

C seems complex enough to make a script language of. Is it sure it isn't easier making it in Lisp, I mean, you basically just got a loot of parenthesis in Lisp, and you don't have to bother about precedence or associativity of the operators. Lisp only allows one operation, or "function", at each depth in an expression.

Then of course, you are the game programmers, so you probably know better! I guess many of you have been coding in some project which used scripting. Which language did you script in; is it possible to script in C++? Did you use your own parser (script interpreter) or did you use an external one? Is there any good parsers out there that you can use?

Just exploring!

-Kristofer

Isn't the whole point with using a script language to avoid developing everything in C++ because of all it's drawbacks, so I see no good reason to have a pure C++ script language?

I recommend for example Lua (used in many good games, for example ai in supreme commander)
http://lua-users.org/wiki/LuaUses

Why do you think you need scripting for this?

Quote: Original post by alvaro
Why do you think you need scripting for this?

Because it's supposed to be research, not game making in first hand.