Improve my chess engine (mainly nps and branching factor)

[jdart]

I think C++ std::map is not even a hash table as you might expect, but a tree, so search is relatively expensive. Definitely look at a more efficient method. There are plenty of open-source examples of hash implementations for chess.

--Jon

[vittyvirus]

This was a section from a book that discusses the basics of techniques used to improve chess engines.
'Gimme Your Best Shot!' -
the Null-Move
At the beginning of the 1 990s a new
and very effective way of pruning the
search tree came up. Given that a large
percentage of the moves that computers
search through are junk, programmers
have been working on how to get
nd of the lines that make no sense The
most absurd sacnfices can take a lot of
time to go through. For the computer,
any sacnfice could prove valuable at a
later time, while humans often have an
intuitive feeling about a sacrifice that
the computer does not possess. Take a
look at the diagram overleaf.
Imagine that we have a program
with no opening book analysing this
well-known position in the Ruy Lopez.
The computer takes a look at the sacnfice
4 ..Itxa6 and analyses the move 8
plies deep
Even a beginner will see that this
move leads to nothing but the loss of a
bishop for a pawn The computer program,
however, has to go down 8 plies
of this line with around 25-35 ramifications
at each ply to find out that the
move is a bad one, and essentially losing.
This is a serious time-waster, and
analysing these 'junk lines' will keep
the computer from lookmg at more
relevant lines For this reason the nullmove
was invented. Null-move actually
means 'not moving' or 'pass' - something
that is not normally possible in
chess. Basically, it can be compared to
a very confident boxer allowing his
opponent to take an extra shot or two
Imagine that a computer program is
analysing the first three plies 4 i.xa6
bxa6 5 lDc3 (or another fifth move)
and then makes an evaluation A program
based on material evaluation
alone will give the value - 200 - a twopawn
plus for Black Now it is time for
the null-move The program, playing
Black, believes that Black's position is
so supenor that it 'passes' and gives
White another shot. White seems to
have nothing special here The best
move􀁑 are probably 0-0 or d4 Despite
the fact that White gets an extra move,
Black will still have his two-pawn plus
Now the computer concludes that
White cannot do anything special even
with an extra move, and therefore all
lines containing 4 i.xa6 are not analysed
any further. In the diagram position
White could play a lot of other
moves (such as, for instance, 4 0-0)
that leave the bishop en prise, but most
of these lines will be cut off quickly by
a null-move procedure
Programmers are still experimenting
and testing if there are positions
where one side needs to make two or
more null-moves to find the hidden
dangers in the position. No matter
what, the result is a dramatic reduction
of the branching factor of the search
tree, and this can lead to an improvement
in search depth.
Naturally, this kind of pruning also
has its dangers. First of all, by cutting
off a lot of useless junk, it also becomes
less likely that the program will
find the good sacnficial lines, as some
of those will be pruned off. The speed
of modern computers compensates
for this to a certain degree However,
when analysing with a computer - or
playing against a computer - the human
player should be alert about this
weakness of the programs When performing
computer-assisted analysis it
is very important always to execute the
actual sacnfice and perhaps a few more
moves, especially if they are nearly
forced Taking the computer a little
INSIDE THE MACHINE 2 7
way down a sacrificial line will help it
a lot.
When playing against a computer, a
long-term positional pawn sacrifice
or an unclear piece sacnfice that leads
to an attack are strong weapons However,
when it comes to short-term tactics
and sacrifices, the programs are
second to none. They never make
short-term mistakes.
Let us look at an example from the
match between Vladimir Kramnik and
Deep Fritz in October 2002, in which
Kramnik made an unclear knight sacrifice
which I have already mentioned
in chapter one.
V. Kramnik - Deep Fritz
Match (6), Bahrain 2002
In tills position from game 6, we have
nearly reached the cntical moment.
Deep Fntz is analysing 1 8 . . . dxc4, and
at this point it has to analyse 46 different
answers to this move, one of them
is the sacnfice 1 9 li:Jxf7. I would like
to use this example to illustrate some
of the points that I have discussed so
far, so we shall imagine, for a moment,
that we are a computer program
trying to analyse this position. First of
all, we shall look at the main line as
played in the game, counting plies and
extending when there are checks or
captures. Let us assume that our program
only extends the search when
there is a 'healthy capture' , a capture
of equal matenal or a capture winning
material
18 ... dxc4
Ply 1 .
1 9 li:Jxf7
Ply 2. This is not a straight exchange,
so the search is not extended.
19 ... 􀀖xf7
Ply 3
20 .i.dS+
Ply 3 . The line is extended one ply
because of the check
20 ... 􀀖g6
Ply 4.
21 'iWg4+
Ply 4. The line is extended another
ply because of the check
21.. . .i.gS
Ply 5.
22 .i.e4+
Ply 5 . The line is extended another
ply because of the check.
22 .. Jhe4
Ply 6. This is not a straight exchange,
so the search is not extended.
23 'iWxe4+
Ply 6. The line is extended because
of check
23 ... 􀀖h6
Ply 7
24 h4 (D)
Ply 8.
This is the first time since the knight
sacnfice on move 1 9 that the black
kmg has not been in check. Most programs
should get to this point fairly
quickly. Normally we would have
reached 1 2 plies here, but because of
all the checks it is only counted as 8
plies. Consequently, the program will
go deeper in this line than in quieter
lines without checks and captures.
Counting material, Black is the
equivalent of two pawns up, i.e. he has
a knight, a bishop and a pawn for a
rook. At this point the program throws
in a null-move, as if it is saying: 'My
position is supenor when it comes to
matenal. Would White have anything
if it were his tum to move')' If he does
not, then the program (playing Black),
will throw away the whole line
However, the computer soon di􀁑covers
that White can use his extra
move to take the bishop with 25 hxg5+,
so the line cannot be thrown out yet In
the continuation, White keeps checking,
and this extends the search.
24 .•. .Xi.f6
Ply 9
25 .id2+
Ply 9, search extended
25 ... g5
Ply 1 0.
26 hxg5+
Ply 1 0, search extended.
26 .•. .Xi.xg5
Ply 1 0, search extended, as this is
an exchange of equal material In the
game, Vladimir Kramnik now played
27 􀂪h4+, but let us continue a while
down the line which is en tical for the
assessment of the sacrifice on move
1 9
27 􀀲e6+
Ply 1 0, search extended.
27 ... tZ:lf6
Ply I I .
28 f4
Ply 1 2
28 ... .ih4!
Ply 1 3
2 9 gxh4
Ply 1 4.
29 ... 􀀲g8+
Ply 1 4, search extended
30 􀀲xg8
Ply 1 5.
30 ... Mxg8+
Ply 1 5 , search extended.
31 Wh2
Ply 1 6.
31. .. tZ:lg4+
Ply 1 6, search extended
INSIDE THE MACHINE 29
32 􀀻g3
Ply 1 7 .
32 ... tZJe3+
Ply 1 7 , search extended.
33 􀀻f3
Ply 1 8
33 ... tZJxfl
Ply 1 9.
34 1'hfl
Ply 20
34 ... c3
Ply 2 1
The program would have to reach
approximately this point to make a
correct assessment of the refutation
move 28 . .lth4 ' , which appears to be
the only saving resource. At move 34
the position is not even stable yet, as
White will lose further matenal because
both the rook and the bishop are
threatened, and the pawns on c3 and
d4 are a dangerous force Anyway, at
move 34 the material evaluation will
be that Black is a pawn up, and this
essentially refutes White' s sacrifice
This line is only one of the main lines
in the analysis of the sacrifice, but giving
a thorough analysis is not the point
here.
I have included this example to show
how the engine analyses a complicated
position In the game the machine wa􀀰
searching 2.5 million pO'litions per
second, and it is of course not possible
to reproduce the program's 'thoughts'
However, the example shows how extensions
and null-moves operate. At
move 24 the program tned to throw
out the whole line with a null-move
procedure, but it had to continue the
search, since White' s threats were too
strong (unlike the example with the 4
i.xa6 sacnfice in the Ruy Lopez)
The analysis above show that computers
are capable of going quite deep
into the cntical lines, but it also tells us
that some sacrifices may be beyond
the computer's honzon I set up the
initial position (before Black's 1 8th
move) on an AMD 850 MHz processor
with 432 Mb set for hash tables
With Fntz 8 it took the machine 5 1h
hours to reach ply 1 8 in the main line,
extending the search up to 56 plies in
some lines (yet we do not know if
these are relevant positions). To go 1
ply deeper, the program usually needs
3 times more time, so it would probably
need about 1 7 hours to reach ply
1 9, and approximately 5 1 hours to get
to ply 20 Obviously, the mUlti-processor
machine that played this game
was much faster, so it i s not easy to say
how much of the refutation of the sacrifice
Deep Fntz actually saw. However,
the example above should give
some idea about it.
Unfortunately for the programs,
there are positions where the null-move
does not work. In the endgame in particular,
the null move is of little use, as
it leads to trouble in zugzwang positions
Here is one simple example of
this (see diagram overleaf):
White does not actually have a
threat here. He is waiting for Black to
make the move . 􀀻g7, so he can play
􀀻e7 and queen his pawn. For obvious
reasons, a null-move does not work in
these situations, as makmg a pass in
this case will result in Black drawing
the game, instead of losing it. Thus,
the null-move algorithm is normally
not used in endgames.
Razoring
Programmers have found other methods
to refine the search and make it
more selective. Another method of
pruning the search tree is called razoring,
and it works by cutting off more
lines when the search is getting closer
to the maximum depth analysed. Let
us imagine that we have a program
analysing 1 5 plies deep in the middlegame.
With the razonng procedure the
program evaluates all positions three
plies before the end, in this case before
ply 12, and if the evaluation function
shows that the computer is a
queen or more down, it will immediately
throw out the whole line The
reason is that it is unlikely that the 3
last plies in the search will change
anything significantly - although of
course this does happen ! However, the
most i mportant thing is that the program
will get rid of some junk lines,
which will save time for focusing on
more important vanations
Like the null-move procedure, this
is of course a risky method. However,
in practice it seems to work well, and
according to the programmers of the
program Dark Thought this method
shnnks the search tree by 5- 1 5 % on
average when the search depth is more
than 1 0 plies.
The Evaluation Function
So far, we have only been speakmg
about matenal evaluation when discussing
the evaluation function. Most
chess computer users will know, however,
that chess programs do not merely
count the material and nothing else
How, for instance, do we tell a computer
program that a knight is often
better placed in the centre than on the
nm, or in the comer of the board?
-10 -5 0 0 0 0 -5 -10
-5 5 10 10 10 10 5 -5
-5 5 1 5 1 5 1 5 1 5 5 -5
-5 5 1 5 1 5 1 5 1 5 5 -5
-5 0 1 0 10 10 10 5 -5
-5 0 5 1 0 1 0 5 0 -5
-10 0 0 0 0 0 0 -10
-20 -5 -5 -5 -5 -5 -5 -20
INSIDE THE MA CHINE 31
The above diagram shows a possible
piece-placement table for a white
knight.
By assigning a number to each of
the 64 cells, i.e. the 64 squares of the
board, the computer will get a bonus
for centralizing the knight. The distnbution
of points in the diagram can, of
course, be discussed.
Following this table the program
will be encouraged to develop a knight
from g 1 to f3 for instance, gaining 1 0
points, as the value goes from - 5 to
+5. Note that these values are not necessarily
strictly comparable to our matenal
evaluation earlier in this chapter,
as programmers assign different values
for putting a knight on d5 for example.
In our example it would be
worth ' 1 5 points' , but the actual value
will differ from program to program.
Each piece has a table like this, and the
positive thing about the tables are that
they do not 'cost' much for the program
in time. When Fritz won the World
Computer Chess Championship and
beat Deep Blue in Hong Kong in 1 995,
the program had nothing but this kind
of piece-placement tables and a welltuned
search function This tells us
that the piece-placement tables are effective,
but of course modem programs
have many more factors included in
their evaluation
Many factors are important when
analysing where the pieces will be
well placed One of them is where the
opponent's kmg is placed To get an
aggressive and attaclang program you
can give a bonus for putting the pieces
close to the opponent' s lang This is
done by counting the number of king
moves from the square to the opponent's
lang The piece placement is illustrated
in the following example.
V. Korchnoi - O. Romanishin
Leonid Stein memorial, Lvov 2000
Black has castled kingside, and
White has a knight on f3 that he would
like to transfer to f5 via h4. From the
f3-square there are 5 king moves to g8
(e.g f3-f4-f5-f6-f7-g8) , but on f5 the
knight is only 3 king moves from the
opponent's king (f5-f6-f7-g8), and this
gives a bonus. Moreover, the knight
will get a + 1 0 bonus for making this
manoeuvre according to our pieceplacement
table, and for this reason it
is possible that White will try this -
provided that there is no tactical drawback
and that nothing else returns a
higher score
The next step is to expand the positional
evaluation by looking at the
pawn-structure. The program will
award a further bonus if no pawn can
threaten it on f5 (i.e. the e- and g-pawns
have been exchanged or are too far advanced),
or if the knight is covered by
one of its own pawns In this situation
the knight is covered by e4, but it can
actually be threatened later by the gpawn,
although this is unlikely to happen
in the following moves, as the
black h-pawn hangs
Computer programs contain vanous
kinds of positional evaluations. One of
these is a rook on an open file Some
programs may want to play 1 2 dxe5 in
this position to underline the white
rook's position on an open file, even
though its position would probably
soon be challenged by a black rook.
Anyway, this move seems to be no
worse than 1 2 'Dh4 and perhaps the
two plans can be combined
To mention all the values that a
modem program considers is the same
as giving a list of most of the rules of
thumb that human chess-players use
Some of these would be. pluses for the
bishop-pair, knight outposts, a rook
on an open or semi-open file, passed
pawns, connected passed pawns, good
king safety; and minuses for doubled
pawns, isolated pawns, doubled isolated
pawns, backward pawns, a bad
bishop, etc All of the computer's positional
evaluation is, of course, borrowed
from human knowledge of chess
positions, and this is the reason why
they can sometimes play very reasonable
and almost human-like chess.
Essentially, when your chess program
displays, e g., ' l .09' this evaluation
consists of hundreds of pluses and minmes
calculated by the computer.
In a few cases it seems that programmers
have actually expanded the
existing theory a bit One example is
that many programs work with as many
as ten phases of the game, instead of
the three well-known ones (i.e. opening,
middlegame and endgame). Perceiving
the game as three phases is too
simplistic to understand what is going
on in many games. These ten phases
probably do not have fixed names, but
they correspond to different phases
of the opening, middlegame and endgame,
such as 'early middlegame',
'late middlegame' , 'early endgame' ,
'late endgame' and so on. These phases
are essential for understanding the
value of a bishop vs knight, the centralization
of the lang, and so on. In
the 'late endgame' , such as a pawn
endgame, king activity and opposition
are important factors, while other values
may be more i mportant in an
'early endgame' . To determine which
phase the game is in, the computer
will count the number of pieces and
work out which pieces have been exchanged.
The queens are especially
important in determining the phase of
the game.
The values of positional pluses and
minuses are quite easy to explain in
computer language 'If Black has a set
of doubled pawns, then -30' , for example
However, most chess-players
INSIDE THE MA CHINE 33
may imagine some of the problems
ansing with the evaluation function
Sometimes a rook has nothing to do on
an open file, sometimes the knightpair
is stronger than the bishop-pair,
sometimes doubled pawns can be good
because they result in the opening of a
file which can be used for attacking
purposes, and so on How can we 'tell'
the program about these issues?
When 'teaching' a program to play
better positionally, we have to set everything
up as simple rules. One example
of a rule could be that the bishop is
bad if there are two or more pawns on
the c-, d-, e-, and f-files that are on the
same colour as the bishop These rules
may seem somewhat simplistic to humans,
and they can often lead to wrong
evaluations. For a chess programmer,
however, there is no other way The
programmer has a difficult task He
has to invent the rules that can be explained
to a program and give them
the right values All of these have to be
weighted against each other and the
result is the evaluation displayed on the
screen The problem is that in chess
there are numerous exceptions for any
rule you may create. This is one of the
reasons why chess is so fascinating
and difficult Most chess-players will
probably say that you cannot expres􀁑
chess as a formula, but this is essentially
what the programmers have to
do. Arguably, chess programs are the
most dogmatic of all players '
Much will depend on the chess insight
of the programmer." which may
vary Actually, there are many examples
of progrdms having, for instance,
no code for a bad bishop or oppositecoloured
bishop endgame􀪓 All of thi.,
leads me to the conclusion that you
should not trust the computer evaluation
blindly, even though the strongest
of today' s programs have well-tuned
evaluation functions. Take a good look
at the position yourself, and your own
intuition may surpri􀄧e you '
One last point to consider is the mobility
of the pieces. The simple way
of measuring mobility is to count the
number of legal moves for Black and
White, and then calculate the difference
between the two numbers In the
diagram on page 3 1 , White has 36 legal
moves, while Black has 3 1 This gives
White a lead in mobility of 5 - a number
which can then be multiplied by a
factor chosen by the programmer to
fit into the evaluation function. If we
choose to multiply it by 1 0, we will
give White a mobility advantage worth
50 points, or liz pawn Some programs
work with a more sophisticated mobility
evaluation, which gives a better
picture of the actual scope of the vanous
pieces. Let us imagine we have a
position with a knight trapped on h8 It
has the possibility of going to f7 or g6,
but it will be captured immediately if
it does so. A simple mobility evaluation
will tell us that the knight ha<; a
mobility of 2, while the more sophisticated
mobility evaluation will give a
score of 0 The advanced evaluation is
more 'expensive' in time, and thus it is
not included in many programs One
would expect the programs that analyse
the fewest positions per second
to have elaborate functions like this,
and these probably include Hiarcs and
Gandalf.
The Engine Output
During the analysis of a position, the
engine displays information about the
lines that it is currently analysing Let
us take a look at the output of one of
the strongest positional engines, starting
from the diagram position.
12 tbh4 exd4 13 tbf5 l:te8 14 l:txd4
tbc5 1 5 tbd5 i.d8 16 f3 ± (0.75)
Depth: 9/20 00:00:06 526kN
Hiarcs 8 suggests the move 1 2 tbh4,
played by Korchnoi, quite quickly It
gives this move as the best in less than
one second. After this it displays a
main line with the moves it currently
considers best for White and Black to
a depth of 9 plies. On the screen the
program will also give information
about which move it is currently analysing.
Furthermore, it shows how
many positions it is analysing per second
In this example it was analysing
85 kN/s, which means approximately
85,000 positions a second
The evaluation of the position is
given in brackets. At this point it is
0 75 , which means a '0.75 pawn plus
for White ' . This evaluation refers not
only to the current position, but also of
the potential in the position In reality,
it is an evaluation of the position arising
if the moves in the main line were
played out. In the main line the program
displays the line which it considers
the best - it assumes that both
Black and White make the best moves
on each tum. Obviously, the program' s
evaluation o f the position 9 plies later
can change if the program is set to analyse
at that point.
In the variation window Hiarc&#1048987;
gives a main line of 9 plies. It displays
Depth = 9120, in which the first number
corresponds to the number of plies
in the main line displayed by the program,
and the second refers to the
deepest line it has found, which is 20
plies long This line includes extensions
and 'healthy captures' at the end
of the search. '526 kN' means that after
six seconds the program has examined
approximately 526,000 positions
in total. This may sound like a lot, but
actually Hiarcs is a slow-searcher compared
to other modem programs However,
it has a lot of knowledge built in
to compensate for this Some other
programs could search half a million
positions per second starting from this
position (with the same hardware), but
this does not mean that these fastsearching
programs are necessarily
stronger. Actually, it is difficult to say
exactly how the user can use the information
that a program is searching x
kN/s. The only thing you can say for
sure is that if this value if relatively
low, you are dealing with a more
' knowledgeable' program, which may
INSIDE THE MACHINE 35
know more rules about positional play
and the endgame With all this knowledge
of chess rules and of positional
play, some may ask why the computer
programs still have problems with positional
chess, and we will get back to
this in Chapter 3, when discussing the
weaknesses of the computer.
Information about which programs
are more knowledge-based can be of
help when choosing a program to analyse
with The ' slow' programs are
not necessanly the one!> that do worst
when calculating tactical strokes, as
we shall see in the following example.
The main line here is the spectacular
sequence 1 iLxh6 ! gxh6 2 g7 j"e7 3
Mxe5 ! dxe5 4 &#1048746;b3+ 'It>h7 5 &#1048746;f7, mating.
I tested some programs, and the
results for finding the first move of the
solution were
Nimzo 8 2 sec (625 kN/s)
Shredder 7. 4 sec. ( l43.kN/!»
Gandalf 5 beta· 5 sec ( 1 1 2 kN/s)
Chessmaster 9000 5 sec ( 1 1 9 kN/s)
Hiarcs 8 37 sec. (73 kN/s)
Junior 7 37 sec (700 kN/s)
Crafty 1 9.03 58 sec (355 kN/s)
Fritz 8· 1 09 sec (396 kN/s)
Chess Tiger 1 5 : 342 sec (209 kN/s)
Gambit Tiger 2 726 sec. (238 kN/s)
This result shows that programs
such as Shredder, Gandalf and Chessmaster
find this combination quite
quickly despite the fact that they calculate
fewer nodes (or positions) per
second than, for example, Junior or
Fntz. Both Hiarcs and Junior find the
solution after 37 seconds, even though
the latter calculates 1 0 times more
nodes per second' Thus, vanations in
the way of searching and knowledge
have a great impact on the output
Note, however, that the best time of all
is achieved by a fast-searcher, and another
fast-searcher, Goliath, also finds
the solution extremely quickly.

[Richard Allbert]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

[adityapande]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

I think arrays are not good enough because of variable number of each piece type.

[ZirconiumX]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

I think arrays are not good enough because of variable number of each piece type.

While the waste of space is a valid point, I think it's worth it for the direct speed gain of using an array.

Matthew:out

[Richard Allbert]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

I think arrays are not good enough because of variable number of each piece type.

Just make space for the maximum - 10. It's not much space, and the performance difference is huge.

Anyway, not my problem.

[lucasart]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

In fact, I suggest you weed out C++ STL completely from your engine. You will waste less time writing STL crap, building an object model that depends on it, only to find out later that the whole think sucks and has to be rewritten, but now that everything depends on it, you have to do a complete rewrite of large parts of code etc.

Now Rein will answer and lecture us about the benefits of STL. Just don't listen allright?

[Henk]

This is why data encapsulation/data hiding was introduced. To prevent rewriting large pieces of code.

Problem is that it conflicts with efficiency(speed).

[mar]

Well... how do you expect to perform with stuff like this:

Code: Select all

Move *tmp = new Move(*move);

storing UCI move string in Move structure (ok only a static array but still),
indexing out of bounds (debug mode vector should catch it for you)
and who knows what else. Your engine is obviously original so thumbs up.

My suggestion is to fix bugs, simplify move and board structure, use negamax to get rid of separate min/max code,
generate moves on stack (you use depth-first search anyway, I see no point in holding the whole tree in a dynamic structure, you even dynamically allocate each move!)
maximum number of moves per position should be no more than 256 (there is an exact number that you can google, it's less than that, 218 IIRC).
Just be careful to avoid excessive stack usage (typically apps can use 1 meg/512 kb).

[Rein Halbersma]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.

Following on from this, I noticed in your Position class you are using std::vector<int> for your pieces - I did this in my first ever program and it slowed it down a lot. May be better just to use an int array[].

In fact, I suggest you weed out C++ STL completely from your engine. You will waste less time writing STL crap, building an object model that depends on it, only to find out later that the whole think sucks and has to be rewritten, but now that everything depends on it, you have to do a complete rewrite of large parts of code etc.

Now Rein will answer and lecture us about the benefits of STL. Just don't listen allright?

Ah Lucas, haters gonna hate