ZirconiumX wrote:A few notes.
G++ is the 'industry standard'. If it will compille on G++ it makes porting to other compilers *much easier*.
Looking at the source code, it seems like you use an array of 'deltas' plus a few piece lists.It doesn't seem to be the fastest of board representations. Maybe this is something to improve upon?
It also appears to be fairly memory intensive. Maybe you could initialise this on startup? I could give you some example code, if you want.
I (and I think Sven would agree) think that your board representation is not very flexible. You need something that will be able to expand with your engine. I would recommend a '0x88' approach for a beginner.
Matthew:out
I agree only partially. Yes, the board representation is not very flexible. But no, I would not recommend to change the board representation of this engine
at the moment since the overall improvement would be very small, and since there are more important things to do right now in my opinion.
The following is directed @Mark of course:
The only recommendation I can give to you at this point is to try to learn how to structure a C/C++ program well. I am VERY SURE that this is the basic problem, not the choice of the right algorithms and data structures. Don't build your next chess program the same way like before.
In the following I assume a C program, things are only slightly different for C++ programs. You are free to pick what you like to do and skip what you dislike, of course. The list is also necessarily incomplete, and even if you follow every single point it will not be guaranteed that you have immediate success - you also need patience, a lot of careful step-by-step testing, and the will and ability to change or even redo things that are not as they should be.
1) Split your program into several source files (modules) where each module belongs to one logical unit of your program. Good candidates for a chess program might be: general non-chess utility code, general chess code (types + constants + utility functions), board management (incl. make/unmake move), move generation, attack management, evaluation, tree search, book management, time management, WB/UCI protocol handling. Details may be different for each program of course.
Also I suggest to define data types for concepts like "move", "move list", and maybe also for the very basic concepts like "square number", "piece type", "color". It will help a lot to avoid bugs caused by using plain integers for everything and mixing up squares and pieces.
Now don't start to take your current program and tear it apart that way. I am talking of a NEW program - I suppose it will be too difficult for you to correctly reorganize your current program accordingly, considering also the other points below!
Some people like to put everything in one file. This may be o.k. for experienced programmers but only if the program is well-structured internally and "can be read like a good book". I don't recommend it for other cases, though.
If you archive old versions and/or use a versioning software then throw out unused code frequently. Don't bother with garbage.
2) Take care to define what belongs to the "public interface" of your modules (since it is needed by other modules) and what is "internal". Then put all "public" declarations, including function prototypes of "interface" functions, into a header file "MODULE.h", and all other declarations and the implementations of a module's functions into "MODULE.c" (or "MODULE.cpp", if you like). When using this separation of interface and implementation it might happen that allegedly "internal" definitions are needed in the "interface" part to satisfy the compiler, e.g. a typedef used within a struct; in this case they are in fact part of the interface and have to appear there, unless you reorganize your definitions to avoid that.
3) Use #include "OTHERMODULE.h" where interfaces of other modules are needed. Take care to protect each header file's content from multiple inclusion with the standard include guard technique:
Code: Select all
#ifndef MODULE_H
#define MODULE_H
// now the contents of "module.h"
#endif /* MODULE_H */
4) Introduce symbolic constants instead of raw numbers where possible. That will drastically increase the readability of your program, for yourself as well as for other readers, and will reduce the number of bugs and the effort for code changes. You can use #define macros but the better style is to use either "const" variables or enums.
5) In your current stage I'd strongly advise you, as someone already mentioned, to avoid huge initializer expressions for your tables. Instead write init functions to initialize your tables at program startup. This helps to reduce your source code size and the number of "copy&paste" bugs. It is much easier to change and maintain a smaller program than a large one.
6) Write several smaller functions taking parameters, instead of one or few huge functions with thousands of lines of code. Your moveit(), wmovegen(), bmovegen(), and evaluate() functions are kind of counter-examples that way. Especially I suggest not to write huge "spaghetti" code using copy&paste and repeating very similar code pieces over and over again. There are a couple of ways to avoid that, like loops, use of pointers, or sometimes simply the use of "else" for an "if" (I did not find any single "else" in your program, btw ...).
7) I mentioned it in the previous item: become familiar with pointers. They are not "evil" if you know how to safely use them, and you are almost forced to use pointers in a C chess program for efficiency reasons and also to be able to maintain a "sane" program structure. Your current program seems to lack use of pointers completely, apart from the required "char ** argv" in main(). That's not really bad but I think that using pointers can help to improve your program structure. Not "a lot" but noticeably.
8) Take care to use a consistent and useful coding style regarding indentation, variable naming, use of brackets etc. Code like this (from ReBornMainsworthy130.cpp) is already quite hard to read (but there are even worse examples ...):
Code: Select all
if(ed ==1) {
if( !strcmp("go", cmd) ){
if((cnt != 4) & (bw==1)) {
if (stoped == 1){
if(bw==0) bw = 1;
strcpy(cmd, "");
ok = 6;
}
if (stoped == 0){
if(bw==1) bw = 0;
strcpy(cmd, "");
ok = 6;
}
}
if((cnt != 2) & (bw==0)) {
if (stoped == 1){
if(bw==0) bw = 1;
ok = 6;
}
if (stoped == 0){
if(bw==1) bw = 0;
ok = 6;
}
}
}
}
9) Make EXTENSIVE use of the standard "assert()" macro, or an own ASSERT() macro, to let your program check its own consistency at runtime in a DEBUG version. Use it to check validity of function arguments, pointers, array index ranges, important pre- and postconditions etc.
10) Don't even think of working further on evaluation and search of a chess program until the following features are implemented, well-tested and work correctly:
- the minimal WinBoard command subset that is required for tournaments,
- an FEN parser + "setboard" WB command,
- code to run "perft" tests for move generator validation,
- a "perft"-based self-test that automatically performs a couple of important tests using publicly available standard positions and proven results, and shows that your move generator has zero bugs.
I would not have mentioned that last point if I had seen such code in your program.
These were my Ten Commandments for you!
11) If you reach the point where your program basically follows my suggestions 1) through 10), or something similar, then you most probably have a good base to build upon. There are different ways how to proceed now. What you need at least before releasing your engine for tournament-level play (and testing by others) is:
- a simple and bug-free evaluation function, e.g. with material + PST + mobility,
- a simple and efficient quiescence search based on the "stand pat" principle (don't know if you have that already in your current program - it seems you haven't),
- a simple full-width alpha-beta search function,
- a working mate detection that also prefers the shorter path to mate for the winning side, and vice versa for the losing side,
- implementation of draw rules: threefold repetition, 50 moves rule, draw by insufficient material, stalemate,
- the killer move heuristic,
- move ordering based on MVV/LVA for captures and history heuristic for non-captures,
- iterative deepening,
- a way to correctly collect the PV throughout the search tree (for printing it whenever it changes at the root node, and also to use it for move ordering along the PV path in the absence of a hash table implementation),
- time control code and code to deal with interrupting your search.
What you probably also need at this stage (but usually not earlier!!) is some performance optimization. This is A LOT easier to achieve with a well-structured program, so my strong advice goes not to try this with your old-style program!
But if you start to optimize then don't think in terms of NPS (nodes per second) but instead improve algorithms, move ordering, and everything that affects the branching factor. If you find something safe that's good for a factor 10 speedup then do it. But don't mess up your program for some constant overall 5% improvement unless you are about to challenge the world's top 10 engines.
If you have all that and your program still looks good and is bug-free then it might play at ELO 1600-1800 level already. Now do the real thing: implement a hash table, null move, improve your evaluation, implement pruning techniques like futility pruning or LMR, set up an automatic testing framework, tune your parameters, ...
I hope that helps you to come a small step forward at least
Sven