Hi.
I have 10 days off and my hobby for this period is programming AI in chess.
I chess program is only as clever as the logic in it, as such I need help with how to make it think 🙂
The crux of the program is to develop logic to make it 'think' , as such I implement a rating system for each valid move.
eg. If move = checkmate then points = 1000.
if move means opponents queen is taken, then points = 200.
The program thinks about its moves, then the possibly moves of its opponent and then its own moves again.
My chess is average and the level of intelligence is integral to the 'finer' chess details only good players possess.
Any posts appreciated.
cheers
Originally posted by pcaspianYou might want to raise checkmate to infinity, or at least something dramatically larger than any other possible combination.
Hi.
I have 10 days off and my hobby for this period is programming AI in chess.
I chess program is only as clever as the logic in it, as such I need help with how to make it think 🙂
The crux of the program is to develop logic to make it 'think' , as such I implement a rating system for each valid move.
eg. If move = checkmate then points = 100 ...[text shortened]... al to the 'finer' chess details only good players possess.
Any posts appreciated.
cheers
Things to give points to: isolating enemy pawns, creating passed points (especially on open files), making castling impossible and tactical positions in general.
I don't know much about how to do chess programming, but I did read somewhere that mate in 1 should be given a higher value than mate in 2, etc. The problem is that if all "mate in N" situtations had the same value, your program could end up never delivering mate.
Example: It sees mate in 2, and makes a move that would lead to it. Next time, it sees mate in 1, but also sees mate in 3, 4, 5, or 6, which all have equal values. It could make a move then that leads to mate in 6 rather than the one that leads to mate in 1.
Originally posted by dpressnell
I don't know much about how to do chess programming, but I did read somewhere that mate in 1 should be given a higher value than mate in 2, etc. The problem is that if all "mate in N" situtations had the same value, your program could end up never delivering mate.
Example: It sees mate in 2, and makes a move that would lead to it. Next time, it sees mate in 1, but also sees mate in 3, 4, 5, or 6, which all have equal values. It could make a move then that leads to mate in 6 rather than the one that leads to mate in 1.
Hmm, very good point also.
I've added logic to check for all valid moves (castleing included). Essentially what I require the program to do is to be able to manipulate its own scoring system. IE: prog1.1 plays against prog1.2 where 1.2 has a slightly different rating system than 1.1. The winner progresses ect.
Pawn isolation, important positions on the board ect are all good ideas tnks.
Normally you would assign some kind of positional value for each piece, in order to choose between move-sequences with equal material score--for example giving a sequence that puts a secure white knight on e5 a high score.
You want to avoid mindlessly calculating move sequences that leads nowhere, so you'll need a way to discard hopeless moves. Most programs implement some sort of alpha-beta search algorithm to weed out the crappy moves. You might also want to look into null-move heuristics.
For the learning part to be effective, you will probably have to make the program play itself an insane number of times. Will you be keeping a database or will you let it change the positional and material values?
Check out
* Crafty -- http://www.limunltd.com/crafty/
* GNU Chess -- http://www.gnu.org/software/chess/chess.html
* MSCP -- http://brick.bitpit.net/mscp/ (Very basic and easy to understand)
All open source.
Please keep us updated on your progress!
Originally posted by Svin1
Normally you would assign some kind of positional value for each piece, in order to choose between move-sequences with equal material score--for example giving a sequence that puts a secure white knight on e5 a high score.
Yes, I was thinking about that. Other than knowing the 'centre' is a good area to capture, I wouldn't really be able to tell you why 🙂
You want to avoid mindlessly calculating move sequences that leads nowhere, so you'll need a way to discard hopeless moves. Most programs implement some sort of alpha-beta search algorithm to weed out the crappy moves. You might also want to look into null-move heuristics.
Never heard of that, but will look into it thanks.
For the learning part to be effective, you will probably have to make the program play itself an insane number of times. Will you be keeping a database or will you let it change the positional and material values?
Both. I intend on keeping a database , particularly for highly successfull sequences, and the rating system (which it must be able to alter itself (AI) )
[b]
Check out
* Crafty -- http://www.limunltd.com/crafty/
* GNU Chess -- http://www.gnu.org/software/chess/chess.html
* MSCP -- http://brick.bitpit.net/mscp/ (Very basic and easy to understand)
All open source.
Please keep us updated on your progress!
Cool, thanks for the links. Have to implement the groundwork first (which I did in C++ a few years ago), but time to update.
Will let you try her out when I think she's moderately playable 🙂
cheers
Alpha-beta pruning is an algorithm that cuts the size of the search tree down to a more manageable size by eliminating irrelevant sub-trees. Null-move is a method, were you let the opponent make another move and then on basis of the result, remove parts of the search tree.
Here's some basic explanations of algorithms used in chess software
http://www.chessbrain.net/beowulf/theory.html
There's tons of in-deepth explanations on the net.
It also has some implementation suggestions--if your program doesn't use a bitboard representation for example, I suggest you take a look at that part, 'cause it will speed up things significantly.
Happy coding!
About the learning part: I'm not sure how it's accomplished by other means than a database.
I read in an AI book, that Chinook--the world champion checkers program--learned part of it's evaluation-function by playing itself. Even though checkers is very simple compared to chess (Solved for some openings already), maybe some of the ideas can be applied to chess also?
A lot of problems arise when you try to let the program learn on it's own. The program may not be able to identify the correct reason it won/lost or it could 'think' it made some real clever moves, when in reality its opponent simply blundered big time. Identifying and representing the winning pattern is a difficult task.
Originally posted by Svin1
About the learning part: I'm not sure how it's accomplished by other means than a database.
I read in an AI book, that Chinook--the world champion checkers program--learned part of it's evaluation-function by playing itself. Even though checkers is very simple compared to chess (Solved for some openings already), maybe some of the ideas can be applied to chess also?
Somewhile back I read an article by the creators of Chinook in "Communications of the ACM" (Couldn't find the issue, so this is by memory). The principle behind Chinook was as far as I remember to assign a weight (ie. probability) to each possible move. These weights were initially assigned randomly. Then Chinook was left for half a year playing itself on four p4's. During this time the program would change the weights in according to whether it won, drew or lost. For example a win was assigned 5 pts, a draw 2 pt and a loss 0, and the winning program would thus get to breed 5 copies of itself with slightly modified weights, a program that drew a game 2 copies and a loosing program none. After the time passed they had a "A world championship caliber checkers program" evolved by a "genetic-algorithm" (try googling for both terms).
I think the motivation behind doing this was that very little (or none?) theory exists in checkers, ie. you cannot assign points to an open file in checkers. Thus there really is no way of assigning points to positions other than trial and error. I'm thus not sure a genetic algorithm could be used in the same way by a chess program, though you might try mingling a bit with the values awarded for different positions.
On a side note: After the half year had passed they wanted to pit Chinook against human players. When they started off no one wanted to play it, so they decided to give the program a human form: a 19-year old female, that was quite attractive (she studied at Berkeley and enjoyed surfing). Suddenly they had plenty of opponents 🙂 And I must honestly admit that this is the first I've been attracted to a checkers program 🙂
Disclaimer: Writing this from memory, so I might be wrong on few of the details.
As chess is a much much more complex game than checkers creating a good chess engine by a genetic process will take much much longer.
You could reach a certain point by assigning point values to things such as a rook on an open file being worth 0.3 pawns and doubling an opponents pawns as 0.25 etc.
So what the program would do when given a position would be to look however many moves deep and find the position with the highest point value. Of course without pruning the move list it's hard to look far thanks to the huge number of positions. When doing the genetic process be sure to use more than just games starting from move 1. Try some challenging tactical puzzles as well and set pieces. Expect to leave a fast computer (or more than one) for weeks.