Why I program my chess engine.
Without going into technical details , I will try to list a few of them due to which I still continue this hobby even after nearly 2 years. This is , I think the single longest computer related hobby that I have ever had.
Most other projects would have been either completed or abandoned by now :)
1) Human opposition.
It is extremely satisfying to see your creation battle it out against an IM or GM and win against them.
When there are almost no tactical blunders from either side , the joy is infintely more - since basically , your program has outplayed the human !
Now if it is say tic-tac-toe or some game like that, where you can get till the leaves of the game , or there is not much ambiguity involved in evaluation - it would have been passe : luckily chess is unlike this !
The chess tree is way too huge to be completely traversed in the near future.
The way humans play chess is way too different from how computers play.
Lot of good chess players find it quiet difficult to grasp how computers manage to play good chess inspite of its approach !
I will try to present a basic idea here -
Given a position , how a human typically thinks is :
Find out the sub-set of "good moves" that he can make , then switch sides , find the good responses , keep minimaxing this way.
Now , in most middle games , the number of possible legal moves would be in the order of 40 - 80 moves per position.
It is trivial to see that without such an approach a human will not think deep !
The number of possible position even for a ply depth 2 will be 40 * 40 - and it keeps going exponentially for every additional ply depth you want to search !
Out of these 40 - 60 moves , just based on his "feel" and experience, a good human player is able to eliminate most of the bad or "uninteresting" moves and get a small subset of good moves to look furthur into.
This way , a human (more commonly a serious chess player) player can search relevent variation trees of quiet impressive depths.
The better the human is at playing chess , the better would be the sub-set that he chooses and so , better would be his play.
Another factor is evaluation of a position.
In lot of post-game analysis with IM's and GM's , I get something like this.
They follow a variation and then in the resulting position say "This looks better for white" or "White has more possibilities" or "Advantageous for Black" , etc.
This sort of "feel" for a position is not always based on standard positional and tactical heurestics.
Such a feel for a position - where some side has better possibilities or attacking chances is impressive most of the time -
and very tough , if ever possible , to implement in a program while still making it play competitive chess (that is , reach
sufficient depth so that it does not get killed by tactics).
Now let us come into how a program thinks :
A very basic idea is -
i) find all legal moves at current position
ii) For every legal move , find all possible responses.
iii) Continue the above process until you have reached the required depth.
iv) Evaluate the resulting position ,
v) Use minimax/alphabeta/other variants of these to arrive at the best score , best move and best variation for this depth.
vi) If you have more time , increment depth and repeat process.
This looks terribly inefficient and downright idiotic and wasteful for most humans.
Question like "Why move queen in opening when it is such a "bad" move ? Always develop minors first ?" , etc get asked.
The simple answer to all that is - any move can be good or bad depending on the position.
In all positions queen moves in opening need not be bad - even when minors are not developed - trivial example would be fool's mate !
Hence , without a search , a program cannot decide whether a move is good , bad or neutral ...
There were indeed expiriments based on how humans think , where the program tries only 3 or 4 best moves from given position after static evaluation on the "goodness" of each move and try those out... But they failed pretty badly.
The kind of pattern matching , associations and logical "jumps" that humans can do, are tough if not impossible to codify so that a program can make use of this (hmm , as usual strong ai folks can bash me on this ;) ).
Here I must point out that there have been plus points in this field by studying how humans think :
One example is "reductions" / "pruning" and "extensions"
Reductions and pruning work on principle that if the move is not good enough , or threatening enough and if it cant help the side that is to move to equalise or gain an advantage against the opponent side , then reduce the search depth for this subtree.
As can be expected , this is a very dangerous - though IF done right , potentially very lucrative area of research as it can bring down the size of the serch tree.
Some basic ideas have evolved , but I do not rely on any of these - my expiriments have concluded that they destroy the "sanctity" of my search tree too much for me incorporate them in my search.
I keep looking out , thinking and researching more on this field for potentially good ideas - but till now , have not found anything very convincing (other than NULL move based pruning - this I will discuss this some other time , or you can follow this up in some chess programming site).
Extensions are the reverse idea - IF the current move is threatening , then extend the search subtree so that you will try to find out if the opponent has any refutation for this , or if something in the search horizon is hiding anything from us ...
Typical examples for this type of threatening moves which most programs extend are checks , recaptures , passed pawn pushes to seventh rank , etc.
This has the potential to blow up your search tree and ruin your branching factor.
Hence you have to be careful while using these , but most amateurs use this with without much care ....
In earlier version of my program , I had done "selective extensions" where I extend only actually threatening moves , and not moves that may appear as threatening - but are not.
Examples : Most checks can be stupid - so extending these are a very bad idea - like sacing your bishop to give a check , etc.
I keep interacting with strong human players, try to find out how they think , why they think something is good/bad/neutral and try to incorporate that into the program.
Some of the ideas that come out of these interactions are very very interesting and revealing !
2) Incompleteness
There is nothing like "perfect search" , "perfect evaluation" , "perfect moveordering" , etc
Hence , there is always an incompleteness in any approach - due to which , there is _always_ scope for improvement !
Due to the way the tree searches like alpha beta work , the minimal tree is searched when you always search the best move first.
BUT , If you know the best move for a given position - then why search !
So what we try is , various move ordering heurestics (the more number of heurestics or more complex heurestics - the more is the associated speed penality) , so that the most likely best move gets searched first.
This is a very dodgy field , but if you get it right , the gains are exponential !
There is a delicate trade off between linear time that you "waste" in trying to "order" the moves and exponential time game that you get by a reduced tree to traverse.
A very interesting field - where I have been thinking and researching a lot !
Evaluation is another vast field - how do you make the perfect assesment of a position (well near-perfect :) ).
Since there are various factors involved - positional and tactical , and each of which interacts with the other in subtle and not so subtle ways depending on the uniqueness of a position , we can only come up with a set of heurestics based on your expiriments.
Which are the set of herestics that we pick , what weightage do we give for each , what patterns to have in the evaluation , what are the interactions between various heurestics and patterns , etc , etc - a very involved field with lots of traps , pitfalls and possible brilliancies !
One of the best evals I have seen are in Diep and HIARCS - very good programs with some pretty awesome evaluations.
3) Fellow programmers
Barring a few , most of the fellow amateur and professional chess programmers I have met are very open to new ideas and are always willing to discuss their ideas (unless it is going to directly give out what they consider vital secrets :) ).
This open atmosphere helps a newbie quickly understand and assimilate the basic concepts and rise to try out the more advanced approaches.
Without these great guys , (NOTE : I have not met/heard of any serious female chess programmer and so this is not an MCP statement ;) ) , it would not have been half as fun !
If you want to get in touch with them , follow the links on the side to CCC or the Winboard forum , where most of them hangout and post.
4) Parallel Search
This is the most recent interest in this field for me.
Making an essentially serial algorithm like alpha beta (and its variants) parallel.
The amount difficulties involved are non-trivial , which is possibly one of the reasons why there are so few of them around !
I have been quiet sucessful in this (well , my last program folded up in the end due to impossibility in maintaining a 3 + MB source tree :( ) thanks to help , suggestions and testing help from a lot of people.
But this field , still has lot of scope for improvement and is one high performance computing field which will always attract me and possibly other likeminded people time and again !
Efficient and time critical usage of multi processor systems with minimum resource contention to maximise the search efficiency is indeed a challenge !
5) Tournaments , testers and users
It would not be fair to not mention this part !
Tournaments , especially author's only tournaments , where we get to meet and interact with other fellow programmers is a veritable treat !
The amount of ideas discussed , the amount of fun that is had , has to be expierenced to be believed !
I dont think there is a such a big body of testers , amateur testers and enthusiasts who do free testing of various chess programs for the sole purpose of helping the programmer improve his creation in any other field !
These guys are great , and even though I have not yet released my program till now , the feedback that I keep reading about their analysis , comments , etc about other programs is one of the main reasons why I want to make my program available to them.
Their interest and dedication to this field is truely amazing and is , I think, one of the main reasons why this field has progressed so much.
Users , are the reason why there is so much commercial interest in this field ;)
They give valuable feedback and are constant source of motivation for the commercials to improve theor program ($$$ :) )
But jokes apart , even for amateurs chess program authors , the user comments are very valuable "non-geeky" source of ideas and inspirations.
Hope this interest continues for a much longer period - I have had lots of fun , met some wonderful people and learned a lot and I hope more people will join this challenging and interesting field.
Good night ...
Without going into technical details , I will try to list a few of them due to which I still continue this hobby even after nearly 2 years. This is , I think the single longest computer related hobby that I have ever had.
Most other projects would have been either completed or abandoned by now :)
1) Human opposition.
It is extremely satisfying to see your creation battle it out against an IM or GM and win against them.
When there are almost no tactical blunders from either side , the joy is infintely more - since basically , your program has outplayed the human !
Now if it is say tic-tac-toe or some game like that, where you can get till the leaves of the game , or there is not much ambiguity involved in evaluation - it would have been passe : luckily chess is unlike this !
The chess tree is way too huge to be completely traversed in the near future.
The way humans play chess is way too different from how computers play.
Lot of good chess players find it quiet difficult to grasp how computers manage to play good chess inspite of its approach !
I will try to present a basic idea here -
Given a position , how a human typically thinks is :
Find out the sub-set of "good moves" that he can make , then switch sides , find the good responses , keep minimaxing this way.
Now , in most middle games , the number of possible legal moves would be in the order of 40 - 80 moves per position.
It is trivial to see that without such an approach a human will not think deep !
The number of possible position even for a ply depth 2 will be 40 * 40 - and it keeps going exponentially for every additional ply depth you want to search !
Out of these 40 - 60 moves , just based on his "feel" and experience, a good human player is able to eliminate most of the bad or "uninteresting" moves and get a small subset of good moves to look furthur into.
This way , a human (more commonly a serious chess player) player can search relevent variation trees of quiet impressive depths.
The better the human is at playing chess , the better would be the sub-set that he chooses and so , better would be his play.
Another factor is evaluation of a position.
In lot of post-game analysis with IM's and GM's , I get something like this.
They follow a variation and then in the resulting position say "This looks better for white" or "White has more possibilities" or "Advantageous for Black" , etc.
This sort of "feel" for a position is not always based on standard positional and tactical heurestics.
Such a feel for a position - where some side has better possibilities or attacking chances is impressive most of the time -
and very tough , if ever possible , to implement in a program while still making it play competitive chess (that is , reach
sufficient depth so that it does not get killed by tactics).
Now let us come into how a program thinks :
A very basic idea is -
i) find all legal moves at current position
ii) For every legal move , find all possible responses.
iii) Continue the above process until you have reached the required depth.
iv) Evaluate the resulting position ,
v) Use minimax/alphabeta/other variants of these to arrive at the best score , best move and best variation for this depth.
vi) If you have more time , increment depth and repeat process.
This looks terribly inefficient and downright idiotic and wasteful for most humans.
Question like "Why move queen in opening when it is such a "bad" move ? Always develop minors first ?" , etc get asked.
The simple answer to all that is - any move can be good or bad depending on the position.
In all positions queen moves in opening need not be bad - even when minors are not developed - trivial example would be fool's mate !
Hence , without a search , a program cannot decide whether a move is good , bad or neutral ...
There were indeed expiriments based on how humans think , where the program tries only 3 or 4 best moves from given position after static evaluation on the "goodness" of each move and try those out... But they failed pretty badly.
The kind of pattern matching , associations and logical "jumps" that humans can do, are tough if not impossible to codify so that a program can make use of this (hmm , as usual strong ai folks can bash me on this ;) ).
Here I must point out that there have been plus points in this field by studying how humans think :
One example is "reductions" / "pruning" and "extensions"
Reductions and pruning work on principle that if the move is not good enough , or threatening enough and if it cant help the side that is to move to equalise or gain an advantage against the opponent side , then reduce the search depth for this subtree.
As can be expected , this is a very dangerous - though IF done right , potentially very lucrative area of research as it can bring down the size of the serch tree.
Some basic ideas have evolved , but I do not rely on any of these - my expiriments have concluded that they destroy the "sanctity" of my search tree too much for me incorporate them in my search.
I keep looking out , thinking and researching more on this field for potentially good ideas - but till now , have not found anything very convincing (other than NULL move based pruning - this I will discuss this some other time , or you can follow this up in some chess programming site).
Extensions are the reverse idea - IF the current move is threatening , then extend the search subtree so that you will try to find out if the opponent has any refutation for this , or if something in the search horizon is hiding anything from us ...
Typical examples for this type of threatening moves which most programs extend are checks , recaptures , passed pawn pushes to seventh rank , etc.
This has the potential to blow up your search tree and ruin your branching factor.
Hence you have to be careful while using these , but most amateurs use this with without much care ....
In earlier version of my program , I had done "selective extensions" where I extend only actually threatening moves , and not moves that may appear as threatening - but are not.
Examples : Most checks can be stupid - so extending these are a very bad idea - like sacing your bishop to give a check , etc.
I keep interacting with strong human players, try to find out how they think , why they think something is good/bad/neutral and try to incorporate that into the program.
Some of the ideas that come out of these interactions are very very interesting and revealing !
2) Incompleteness
There is nothing like "perfect search" , "perfect evaluation" , "perfect moveordering" , etc
Hence , there is always an incompleteness in any approach - due to which , there is _always_ scope for improvement !
Due to the way the tree searches like alpha beta work , the minimal tree is searched when you always search the best move first.
BUT , If you know the best move for a given position - then why search !
So what we try is , various move ordering heurestics (the more number of heurestics or more complex heurestics - the more is the associated speed penality) , so that the most likely best move gets searched first.
This is a very dodgy field , but if you get it right , the gains are exponential !
There is a delicate trade off between linear time that you "waste" in trying to "order" the moves and exponential time game that you get by a reduced tree to traverse.
A very interesting field - where I have been thinking and researching a lot !
Evaluation is another vast field - how do you make the perfect assesment of a position (well near-perfect :) ).
Since there are various factors involved - positional and tactical , and each of which interacts with the other in subtle and not so subtle ways depending on the uniqueness of a position , we can only come up with a set of heurestics based on your expiriments.
Which are the set of herestics that we pick , what weightage do we give for each , what patterns to have in the evaluation , what are the interactions between various heurestics and patterns , etc , etc - a very involved field with lots of traps , pitfalls and possible brilliancies !
One of the best evals I have seen are in Diep and HIARCS - very good programs with some pretty awesome evaluations.
3) Fellow programmers
Barring a few , most of the fellow amateur and professional chess programmers I have met are very open to new ideas and are always willing to discuss their ideas (unless it is going to directly give out what they consider vital secrets :) ).
This open atmosphere helps a newbie quickly understand and assimilate the basic concepts and rise to try out the more advanced approaches.
Without these great guys , (NOTE : I have not met/heard of any serious female chess programmer and so this is not an MCP statement ;) ) , it would not have been half as fun !
If you want to get in touch with them , follow the links on the side to CCC or the Winboard forum , where most of them hangout and post.
4) Parallel Search
This is the most recent interest in this field for me.
Making an essentially serial algorithm like alpha beta (and its variants) parallel.
The amount difficulties involved are non-trivial , which is possibly one of the reasons why there are so few of them around !
I have been quiet sucessful in this (well , my last program folded up in the end due to impossibility in maintaining a 3 + MB source tree :( ) thanks to help , suggestions and testing help from a lot of people.
But this field , still has lot of scope for improvement and is one high performance computing field which will always attract me and possibly other likeminded people time and again !
Efficient and time critical usage of multi processor systems with minimum resource contention to maximise the search efficiency is indeed a challenge !
5) Tournaments , testers and users
It would not be fair to not mention this part !
Tournaments , especially author's only tournaments , where we get to meet and interact with other fellow programmers is a veritable treat !
The amount of ideas discussed , the amount of fun that is had , has to be expierenced to be believed !
I dont think there is a such a big body of testers , amateur testers and enthusiasts who do free testing of various chess programs for the sole purpose of helping the programmer improve his creation in any other field !
These guys are great , and even though I have not yet released my program till now , the feedback that I keep reading about their analysis , comments , etc about other programs is one of the main reasons why I want to make my program available to them.
Their interest and dedication to this field is truely amazing and is , I think, one of the main reasons why this field has progressed so much.
Users , are the reason why there is so much commercial interest in this field ;)
They give valuable feedback and are constant source of motivation for the commercials to improve theor program ($$$ :) )
But jokes apart , even for amateurs chess program authors , the user comments are very valuable "non-geeky" source of ideas and inspirations.
Hope this interest continues for a much longer period - I have had lots of fun , met some wonderful people and learned a lot and I hope more people will join this challenging and interesting field.
Good night ...
posted by Mridul at 1:13 AM
0 comments
![[FSF Associate Member]](http://static.fsf.org/nosvn/associate/fsf-12017.png)
0 Comments:
Post a Comment
<< Home