Questions by Michael
Firstly hello, and many thanks for agreeing to give us this interview.
It's a pleasure Michael.
In a chess program you can improve the search algorithm or the evaluation to make your program better.
What would you improve more in Pharaon, the search or the evaluation (knowledge)?
Most chess players tend to overestimate the influence of the chess knowledge in an engine strength. I believe that what makes a strong program is first the quality of its search (hashtables and null move management, sorting of moves, pruning, etc...), not the 'quantity of chess knowledge' that it includes.
For instance, if you look at the first versions of Fruit (1.0), you'll see a program with little chess knowledge, but a good and reliable search, and it was already playing strong!
At the same time, some kind of chess knowledge is definitively needed and can not be replaced by search, for instance king safety, passed pawn evaluation...
So, in the last year I have mainly improved the search part of Pharaon, the chess knowledge being nearly the same as in Pharaon v2.62 (released +3 years ago).
What can actually be done in a search improvement?
Alpha-Beta cuts in best case n^(1/2) of the nodes in a tree without losing information about the best move, when the move ordering is perfect.
How then can you still improve the search?
Is it only the knowledge in the evaluation function (for helping the sorting of the moves) or can you actually still improve the search algorithms?
If we're looking for a true 100% 'bug free' search (meaning that we'll never accept that a sub optimal move may be returned by the search instead of the real best one), then there is little room for improvement over alpha-beta and a good move ordering.
Now, if we accept that, in some very rare cases, the search may contains some errors, we'll find plenty of ideas to speed up the search.
The most useful trick is of course the null move heuristic, it is (unfortunately:-) the only way to improve a program by +200 elo points with only a few lines change...
There are lot of other ways to prune the search tree (taking some risks), and I guess that most top playing programs benefit a lot from some 'risky' pruning techniques, by taking this 'risk under control'.
Do you think that it is a good idea to use a kind of path-algorithms inside a chess program (i.e. would you do it for Pharaon) like in the series-movers puzzles ?
This is a kind of repeated null-move, where you could place your own pieces on certain squares (neglecting at first) the other sides move?
I simply do not know this issue, and I will be very interested to see some comments about it.
What (chess) books/articles do you use when improving your program?
Chess knowledge is very important but including too much or even "contradicting" issues might make your program weaker.
Do you insert the knowledge elements one by one and test them or do you insert them all at once?
Currently, I am not using chess books to improve the engine.
My main sources of 'inspiration' are:
1. Internet forums:
there are some fascinating ideas there, like the Botvinnik-Markoff extension, the 'History' pruning (incidentally, both don't work in Pharaon...)
2. Watching engine games.
This can help finding new ideas, especially when the engine blunders.
3. Just switch off the computer and relax: some nice ideas may suddenly appear :)
I must admit that it doesn't give me plenty of new ideas to test, especially if we take into account that most ideas (+80%) are bad ideas...
The use of chess books may be of some help here.
BTW, I always test new ideas 'one by one', and discard all that do not give a clear improvement.
Have you already taken out of Pharaon, something that you implemented a long time ago which does not fit anymore with the newer concepts and if anything, what is it?
There are several things that I have removed from Pharaon lately, to name a few :
1. In previous versions of Pharaon, the engine has a 'mate in 1 move' detection algorithm, for instance in the following position:
4r1k1/1p3p1p/p5pP/8/6qn/2Q1B3/5PPP/3R2K1 w - -
.......it knows that
white can mate with Qxg7# and that black can
mate with Qxg2# .
This was supposed to make the engine stronger tactically, but I realized that it was a complex piece of code (in other terms buggy :-), and the benefit was not that obvious.
The engine plays stronger (even tactically!) without it, and there are other ways to detect mate threat faster and more accurately (for instance using the score returned by null move).
2. At a time I liked to add some very special extensions, for instance an extension for a white rook going to the 8th rank to support a passed pawn on the 7th rank.
So in the following position:
2r1k3/2P5/8/8/8/8/6K1/1R6 w - -
........the move Rb8 will trigger an extension. This extension was removed recently: no real benefit to retrieve from it.
3. Another thing I removed In Pharaon v3.x is a special draw detection code:
the engine will consider that there are some good drawing chances if a side is able to make a very long series of checks without any captures.
In the three above examples, I do not think that the ideas itself were fruitless (without word play ;-),
it can be because they contradict some other parts of the engine ('engine' specific), or also because they were not implemented correctly ('programmer' specific).
What is in your opinion the greatest achievement (technically speaking) in computer chess?
This question seems 'Deeper Blue' oriented :-)
The victory of Deeper Blue over Kasparov in 1997 came as a surprise, even if 6 games has no statistical meaning.
But the achievement of Deep Junior against Kasparov in 2003 was also impressive(a 3 - 3 tie),
especially the 5th game where Junior (with black) sacked a bishop against Kasparov.
Will you be releasing more on tournaments results or on test suites?
Also who is helping you test your program?
The thing that really matters is the engine tournament strength.
But it is only reliable after tens of tournaments (at various time control and against various opponents), which mean hundred (or even thousand) of games.
Test suites appear as a faster way to 'guess' the strength of an engine.
They are also handy to check the strengths and weaknesses of an engine (strong in endgames, weak tactically ...).
So, if we have little time to assess the strength of an engine, I think that test suite will give a better picture then few tournament games.
Thank you Franck
Questions by Frank Quisinsky
After a long time of waiting you released a new version of Pharaon.
Pharaon is a very popular engine because Pharaon is a very strong positional program.
Have you lost interest in computer chess in the last two years or is there not enough time for chess right now?
Or perhaps you are working on a secret mission with Pharaon?
I had little time for my favorite hobby because of my job, some exams to prepare, and a new professional opportunity.
I also played some chess myself and achieved my first FIDE rating last year (oct. 2004).
The Pharaon 3.x versions seem a clear improvement on the previous version 2.6.
Perhaps you have rewritten some parts of Pharaon or introduced some complete new ideas in your engine.
Could you write a little bit about the new Pharaon and the ideas you have for further improvement?
I have mainly worked on search improvement:
1. The move ordering is better
(now using Internal Iterative Deepening).
2. The Quiescence Search is more reliable
(it now includes some checks in the first plies of the QSearch).
3. The null moves are used more efficiently.
4. The hashtable replacement scheme has evolved also.
In the opposite, the chess knowledge has nearly not changed since Pharaon v2.62.
This is what I plan to improve now.
Remembering my first WB tournaments with Kai Skibbe that Prof. Dr. Djordje Vidanovic made public the results on his webpage. At that time I did not have knowledge of HTML and liked to play my tournaments with the first available Winboard engines. You were working on ZChess and we all had a lot of fun with ZChess. You were one of the first WinBoard programmers and you very quickly gave also the new UCI protocol a first look. I had at this time a very big interest to empower UCI and you helped me a lot. The big idea then was to produce a UCI CD (with 6 or 7 French engines) for a bigger French department store but the idea died with the end of Gambit-Soft. All this before we were ready with the Winboard Edition III. This was a catastrophe because Huges Magnier was working a school project with the chess tutorial you added in the new UCI Pharaon at the time. Furthermore; I had at this time a lot of problems with other people who saw in UCI as a big danger to existing protocols. The same people are today big fans of UCI.
a) Were you and Huges disappointed that the WinBoard Edition CD never came on the market!?
(PS Thank you for releasing the UCI version of Pharaon later anyway).
b) Your opinion about compatibility must be very high, I like that. It was very user friendly what you did for us all in past times and you set a mark for all other programmers. Do you have interest to make your engine compatible to Chess960 in the future?
Note: I will never forget the time with AnMon and ZChess I had the most superb computer chess time ever. An extra thank you from me for that.
a) The chess tutorial project came to life in Pharaon/ZChess 2.62.
Hugues (a strong FIDE Player) took in charge the chess specific part, and I worked on its implementation in ZChess 2.62.
The idea was to let the engine give comments and advice to its (human) opponent during games.
Even if this project was considered as a big success by Hugues Magnier school, I must admit now that those comments were very 'low level', not enough to reach Kasparov strength :-)
b) I find the Chess960 idea interesting for computer chess tournaments.
The opening book is a definitive problem in computer chess games,
where we have seen several games won (or lost) even before the program has started thinking.
If you know a GUI that supports Chess960, I would be pleased to make Pharaon, Chess 960 compatible.
I was thinking about the WMCCC in London 2000.
I wrote a mail to you before the tournament started because I needed your handy number. I had at this time a very big interest to write about the WM in the my News-Ticker on Frank's Chess Page.
My ideas were that other people would make the same in upcoming computer chess tournaments :-)
We never thought that our handy connections were the one possibility to give live reports about the results in London.
In London the PC’s did not have an internet account and with a little bit live ambiance, I had thousands of visits daily.
Chessbase and Gambit-Soft added the news that we produced directly in the own News-Ticker :-)
I believe you were very busy with me at the time with all my phone calls?
A nice time Franck! What did the other programmers in London say about our phone calls? Did they say Frank Q. is unnerving?
You never disturbed me, and I was very pleased to answer to those phone calls :)
Computer chess in France is very interesting at the moment.
One of the main points for me has been my interest in the French programmers for many years.
The French programmers built a team and this works perfectly -- A DIRECT HIT -- I think.
Perhaps a better word for the all the French programmers is "club".
The organisation of computer chess events in France is very good.
We have Massy, the French Championships and a lot of strong French programs.
Sylvain Renard is a member of the French chess federation and works a lot for these events.
You are also one of the main organisers.
There are also the BBChess programmer Bernhard Briot and AnMon programmer Christian Barreteau.
I believe the French programmers have a lot of fun in Massy!
Is Massy for you the most important computer chess event Franck?
Do you wish that programmers from other countries could participant in Massy?
It would be interesting to give 3-4 places free for programmers from other countries.
Have you discussed this with Sylvain, Christian and Bernhard?
The three persons that were the most involved are:
Bernard Brioit (BBChess), Christian Barreteau (AnMon) and Bruno Lucas (Dragon).
They have done a wonderful job in the organization of the Massy tournament (each year in May or June) and the French Computer Chess Championship (in October/November).
For the Massy tournament, we have already welcomed some guests in the past, and I am sure that, if some other competitors are interested to compete in this Massy tournament (and especially if they are not too strong :-), then they should not hesitate to send us an email.
This is an interview by Chris and Michael. Chris and Michael made/make a good work for Arena and the computer chess community.
It is nice that you support their efforts and the possibilities by adding your Pharaon in one of the Arena downloads.
But it's their interview and I will not so many questions. The last one!?
A lot of free sources from strong programs are available like the engines, Pepito, Fruit and Phalanx.
What is your opinion about free sources?
This has been after the release of Fruit, a big topic, because Fruit has a lot of playing strength and the sources are very clear.
Do you have an interest to give your sources away for free in the future?
It would be interesting if you could tell us a little about this topic.
The sharing of ideas is a very good point, and is definitively needed to improve the strength of chess engines.
The sharing of source code is on the contrary a very bad point from my point of view: there is no need to understand a source code to copy it, and to include it in some other engines.
I also felt disgusted when I see some pseudo 'computer chess authors' that, after being caught in the act, acknowledged that they were inspired by other source code, and (on top of it !) that they have no intention to hide it !!!
In the Fruit case it is very interesting, because we have a clone (Toga) that is clearly stronger then the original.
What now if the Fruit author (Fabien) includes the Toga change into Fruit ?
Who is the author of this new engine ?
Is this new engine allowed to compete in the French championship or the German championship ?
I have no definitive answer.
Even the definition of a clone is not that clear.
Thanks Franck, and sorry for all my phone calls at the time you played the WM in London :-)
Questions by Christopher Conkie
Hello Franck, thank you for taking the time to talk to us today.
You have a long standing and popular article about Bitboards on your website.
It has been a great help to those starting out by providing uncomplicated explanations where most others are heavy reading.
Do you plan anymore articles about the basics of engine programming?
Also whether or not you do create more articles, which areas do you think would be most helpful for programmers who are starting out on their first engine to pay special attention too?
There are several interesting web sites on computer chess programming technique, for instance http://www.seanet.com/~brucemo/topics/topics.htm by Bruce Moreland.
For a programmer who starts a computer chess engine, I will recommend the study of some simple chess source code, like Gerbil or TSCP.
There is really no need at that point to look at some top class chess playing programs source code (like Crafty of Fruit).
Also I will recommend the use of a programming language like C# or JAVA, and to not lose time on speed optimization technique (like lazy evaluation, hash pawns), or on the GUI (there are already superb user interface available on the net and it is very easy to plug a program to them)
A program that is correctly using Null Move, hash tables, with a decent move ordering and a simple (even piece table) evaluation, should already play at +2000 elo.
I notice that you too were the proud owner of an HP48GX.
Out of this you developed HPChess for one of the most popular programmable calculator of it’s time.
I also had one and before that a Sinclair Enterprise Programmable.
It still works with all of its 9 volt battery. Do you have any plans for Pharaon to be developed for use on modern day hand held devices?
HpChess (see http://www.fzibi.com/hp48/hpchess.htm) was a funny experiment that was released in 1994 :
this assembler chess playing program was running at the tremendous speed of 50 nodes per second ... (compared to more then 1.000.000 nps now …)
At some point I had some ideas to make a PDA version (and even a phone version) of Pharaon, but it required too many changes and I preferred to concentrate on engine improvement.
There are many testing methodologies used to determine the strength of a chess engine.
Most have anomalies that can corrupt results.
What methods do you think are the fairest and therefore most accurate in determining playing strength?
Most of the tournaments that are run are done so under a variety of configurations (books etc), leading to rather false results.
What kind of statistical analysis would you most like to see performed that would be helpful to you as an engine programmer and why?
For me, having a good testing methodology is one of the 2 pillars of computer chess programming (the other one is finding new ideas to test).
My first testing methodology (1996/1997) was to use small test set, like the Louguet Chess Test.
Unfortunately those kinds of tests give a false sense of 'improvement'.
For instance, adding more extensions (all recaptures, all king moves after a check, etc...), some new knowledge, or some odd heuristics can lead to a 100 elo point improvement in some tests ... but will weaken the engine.
It is not only because the program will be 'manicured' to solve the few positions of a test suite,
it is also because most test suites are tactical ones, meaning that in test suites a program will benefit from spending more time on sacrifices lines, exchanges sequences etc...
In the opposite, this time will be mainly useless in real games.
So in 1999/2000, I changed my testing methodology and used 'long' test matches (between 150 and 300 games) against various opponents (my favorite sparring partners were Crafty or Yace).
This new methodology has helped a lot, and ZChess/Pharaon improved clearly thanks to it.
Anyway it had several flaws:
1/ the impact of the opening book can be very high.
For instance some chess knowledge will be very useful in closed positions, and will weaken the engine in open positions.
2/ From a statistical point of view, 150 or 300 games is too small a sample.
So it will not be able to detect small changes (less the 20 elo points) in engine strength.
3/ most of those tests are done at blitz.
So it will overestimate the impact of some extensions, and will under estimate others (null move heuristic).
In 2003, I changed again my mind, and decided to set up my own test suite.
It took a long time to achieve, because I was looking for something that was both fast (at most 3/4 hours to finish), handy, ... and accurate.
I think now that it is not so 'accurate', but anyway it is handy and fast :)
It is composed of 1200 selected positions, separated in 3 categories : tactical, endgames, and 'positional'.
The output of the test looks like this:
"Compared to version 'X', Version 'Y' is on average 10 elo points stronger
(+30 in endgame, +10 in 'positional' play, -10 in tactics)."
It is the use of this test that lead to Pharaon v3.2.
This test has also several flaws:
1/ It doesn't test the engine in actual games, so things like pondering, time management will be ignored.
2/ It is difficult to calibrate it (especially for long time control games).
For instance the benefit of null move is only 100 elo points according to this test. It should be +200 elo points.
Time perhaps for a new testing methodology? ;-)
Pharaon was created using Visual C++.
If you were to start a new chess engine project from scratch,
what language would you use to create a chess engine and why?
Also what do you see as the pros and cons of the various programming languages available, with regard to their abilities and speed e.g. run time verses compile time?
My opinion on programming language changed a lot in the past few years, and I am far now from the 100% C++ fan I was 5 years ago.
When I started Pharaon in 1996/1997 (known at that time as ZChess), C++ (or even C) was an efficient choice.
The JAVA Virtual Machine from Sun was very slow (between 2 and 10 time slower then C++),
and the version of Delphi produced a code that was clearly slower (in 1996/1997) then C++ (under Watcom or VC++).
Now, if I have to start a completely new project, I will not choose C++ (even if the application requires a lot of CPU as a chess engine).
Instead, I will prefer languages like JAVA or (my preferred one :-) C#.
In term of speed, those 2 languages are perhaps 20% slower then C++ , but my belief is that they will be eventually faster then C++ !
I will try to explain my view.
There are basically 2 kinds of optimizations:
=> those done at compile time (like inlining, etc...)
=> those that can be done at run time.
Languages like C++ rely most on compile time optimization (even if some very efficient compilers, like Intel C++ and the upcoming Visual C++ 2005, can also perform some run time optimization using PGO : Profile Guided Optimization)
On the contrary, languages like Java and C# rely most on run time optimization :
the 'compiler' will do nearly no optimization, and will let the Virtual Machine do most of the job to speed up the program.
This second approach seems to boost a program speed, for instance the use of PGO in Pharaon (thanks to the beta of Visual Studio 2005) speed up the engine by 25% !
For program written in JAVA or C#, it will be even more.
What do you believe the future holds for programming chess software?
Would for example, this be helped by the creation of a dedicated language for this purpose?
I believe that there are several breakthroughs waiting to be found in computer chess,
but to find them we need some incentive.
It is clear that there is no 'money' incentive, and (contrary to Shogi),
the current state of the art algorithm are enough to compete with the very best human players.
I hope that, within the end of the 21st century (or even before !), a computer program will be able to 'solve' chess, stating whether it is a draw or a win by white.
Recently Pharaon competed with distinction at the CCT7 Tournament finishing 6th.
A pivotal moment was the 6th round and a lost game to Zappa the eventual winner of the tournament.
It appeared at first that the game might be drawn but Pharaon wandered and eventually lost.
What is your opinion on what happened to Pharaon and will you be competing with Pharaon in any other tournaments? Maybe the IPCCC again?
I was pleased with the Pharaon behavior in the CCT7 tournament: it is its best result so far.
In the Zappa vs. Pharaon game, white impressed from the beginning and was (apparently) winning but in the endgame the following position was reached:
(60th move) 8/2K5/6R1/p1p5/Pb6/7k/8/8 b - -
Black (Pharaon) played
here the horrible 60. ... c4?? and lost.
Instead 60. ... Kh4 had some good drawing chance.
I have tried this position in several engines, and most play 60. ... c4?
Before competing in tournaments like IPCCC or a WMCCC, I want first to improve the engine by at least 50/100 elo (compared to Pharaon 3.2).
So I do not have immediate plans to play in such strong international events.
Can you recommend a good red wine to us all?
Good question :-)
There is one I would recommend: it is the "Gamay", a very fruity red wine that comes from Beaujolais. (see http://www.terroir-france.com/wine/gamay.htm )
Thank you Franck for answering "20 Questions" today. We wish you continued success with Pharaon.
Thank you very much.