How about profiling.Richard Allbert wrote: Which means there is a bug somewhere, but I'm getting very frustrated in wondering where to look.
Any ideas?
Thanks
Richard
PS It's tough at the bottom
Move ordering help
Moderators: hgm, Rebel, chrisw
-
Ferdy
- Posts: 4834
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Move ordering help
-
jwes
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Move ordering help
I would try at small fixed depths until you find a significant difference in nodes, and then dump the tree.
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering help
I'd propose that you let us also have a look at your move ordering and your qsearch, if you don't mind. At least in the part of your alphabeta() function you have posted I have not found any severe problem up to now, apart from code formatting issues 
What is your approximate branching factor?
What about your ordering at the root between iterations, do you really ensure to always search the best move from previous iteration first, and in which order do you process the remaining root moves?
Are you working with aspiration window, and if so, how do you handle a fail low?
Just some ideas, as you requested ...
Sven
What is your approximate branching factor?
What about your ordering at the root between iterations, do you really ensure to always search the best move from previous iteration first, and in which order do you process the remaining root moves?
Are you working with aspiration window, and if so, how do you handle a fail low?
Just some ideas, as you requested ...
Sven
-
Spacious_Mind
- Posts: 317
- Joined: Mon Nov 02, 2009 12:05 am
- Location: Alabama
Re: Move ordering help
Hi Sven,Sven Schüle wrote:I'd propose that you let us also have a look at your move ordering and your qsearch, if you don't mind. At least in the part of your alphabeta() function you have posted I have not found any severe problem up to now, apart from code formatting issues
What is your approximate branching factor?
What about your ordering at the root between iterations, do you really ensure to always search the best move from previous iteration first, and in which order do you process the remaining root moves?
Are you working with aspiration window, and if so, how do you handle a fail low?
Just some ideas, as you requested ...
Sven
Quick side topic. Do you still have your chess program available for Atari ST ? If so I wouldn't mind checking it out.
Best regards
Nick
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering help
Very good question!Spacious_Mind wrote:Quick side topic. Do you still have your chess program available for Atari ST ? If so I wouldn't mind checking it out.
1. All what I wrote for Atari ST was very weak, buggy, and did not conform to any standard protocol like WB (I didn't even know about WB at that time). There was no way for automatic engine-engine play implemented, only a "proprietary" console interface.
2. I'm afraid I don't have access to these old programs anymore. They are probably on the HD of my old Atari ST which does still exist but only in a packing case from where it did not escape during the last, say, 15 years
And very likely the bad news is that the HD might have died in the meantime, I simply don't know - R.I.P.3. The last things I did on my Atari were early versions of "Surprise". It is possible that I have a copy of some old version of it on some floppy disk but even if that copy were still intact, I don't know where I have it ... There are "a lot" of floppies in some packing cases
If I happen to find any of these buggy dinos by accident some day then maybe I'll remember your request ...
Sven
-
Roman Hartmann
- Posts: 295
- Joined: Wed Mar 08, 2006 8:29 pm
Re: Move ordering help
Sorry, I just noted that I calculated my fail-high percentage wrong. My fail-high rate at the first move is not 48% but rather 92%. So my move ordering is quite good actually.Richard Allbert wrote:Hi Roman,
Thanks for the reply.
How are you describing "fail high on first move" ? Do you update a counter for every position searched, or only in the case of a fail high?
...
Btw, do you order your moves at the root?
Roman
-
hgm
- Posts: 27837
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering help
I was already wondering what move ordering you could have that only managed 48%. 
Simply playing the MVV/LVA capture first should already do much better than that.
Just to make sure: all these reported numbers do not consider null-move prunings as a first-move cutoff, right? If you say 92% it is 92% of the real moves tried first that gae the cutoff.
From my statistics, at d=2 I have 446k first-move cutoffs (of which 263k by hash move), out of 563k cutoffs by a real move. But I have 2.9M null-move prunings.
Note that at d=1 I hardly have any hash-move cutoffs. I guess at d=1 there ususally is no hash move.
Simply playing the MVV/LVA capture first should already do much better than that.Just to make sure: all these reported numbers do not consider null-move prunings as a first-move cutoff, right? If you say 92% it is 92% of the real moves tried first that gae the cutoff.
From my statistics, at d=2 I have 446k first-move cutoffs (of which 263k by hash move), out of 563k cutoffs by a real move. But I have 2.9M null-move prunings.
Note that at d=1 I hardly have any hash-move cutoffs. I guess at d=1 there ususally is no hash move.
-
Spacious_Mind
- Posts: 317
- Joined: Mon Nov 02, 2009 12:05 am
- Location: Alabama
Re: Move ordering help
Thanks Sven,Sven Schüle wrote:Very good question!Spacious_Mind wrote:Quick side topic. Do you still have your chess program available for Atari ST ? If so I wouldn't mind checking it out.
1. All what I wrote for Atari ST was very weak, buggy, and did not conform to any standard protocol like WB (I didn't even know about WB at that time). There was no way for automatic engine-engine play implemented, only a "proprietary" console interface.
2. I'm afraid I don't have access to these old programs anymore. They are probably on the HD of my old Atari ST which does still exist but only in a packing case from where it did not escape during the last, say, 15 years
3. The last things I did on my Atari were early versions of "Surprise". It is possible that I have a copy of some old version of it on some floppy disk but even if that copy were still intact, I don't know where I have it ... There are "a lot" of floppies in some packing cases
If I happen to find any of these buggy dinos by accident some day then maybe I'll remember your request ...
Sven
Best regards
Nick
-
Richard Allbert
- Posts: 792
- Joined: Wed Jul 19, 2006 9:58 am
Re: Move ordering help
Hi Sven,
It'll be rather long.... because I do this in the movelist class... (which is used by the move generator).
That's all a mess isn't it?
@ HG - Thanks for the tip about those stats. I thought I was printing detailed enough info... obviously not!
@Roman - this is without root sorting. Your 92% seems a little better!!
Also, if I add PVS
Then the node count increases, rather than an expected decrease.
I don't have time tonight, but I will look at this tomorrow evening after work, starting with some stats by depth as in the table above.
Thanks for the replies...
Although, one thing I did notice. I left the other engines with PVS on. When I turned this off, they weren't much different than Jabba.
So the problem could well be the PVS implementation... sorry.
It'll be rather long.... because I do this in the movelist class... (which is used by the move generator).
Code: Select all
const uint HISMAX = 50000;
#define HASH 2600000
#define M_KILLER 2500000
#define WIN_CAPT 2400000
#define Q_PROM_CAPT 2300000
#define Q_PROM 2200000
#define GCAP_QQ 2100000
#define GCAP_RR 2000000
#define GCAP_NN 1900000
#define GCAP_BB 1800000
#define GCAP_PP 1700000
#define SEECAP 1600000
#define KILLER1 1500000
#define KILLER1_PLY 1400000
#define KILLER2 1300000
#define KILLER2_PLY 1200000
#define OO 1100000
#define OOO 1000000
#define MINORPROM 900000
static const int equalcap[13] =
{0,GCAP_PP,GCAP_PP,GCAP_NN,GCAP_NN,
GCAP_BB,GCAP_BB,GCAP_RR,GCAP_RR,
GCAP_QQ,GCAP_QQ,0,0};
/*moveorderingpsqt*/
static const int orderpawn[64] = {
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
10 , 10 , 10 , 10 , 10 , 10 , 10 , 10 ,
20 , 20 , 20 , 20 , 20 , 20 , 20 , 20 ,
30 , 30 , 30 , 30 , 30 , 30 , 30 , 30 ,
40 , 40 , 40 , 40 , 40 , 40 , 40 , 40 ,
60 , 60 , 60 , 60 , 60 , 60 , 60 , 60 ,
80 , 80 , 80 , 80 , 80 , 80 , 80 , 80 ,
100 , 100 , 100 , 100 , 100 , 100 , 100 , 100
};
static const int orderknight[64] = {
0 , 10 , 10 , 10 , 10 , 10 , 10 , 0 ,
10 , 15 , 30 , 30 , 30 , 30 , 15 , 10 ,
10 , 20 , 50 , 50 , 50 , 50 , 20 , 10 ,
10 , 20 , 50 , 80 , 80 , 50 , 20 , 10 ,
10 , 20 , 50 , 80 , 80 , 50 , 20 , 10 ,
10 , 20 , 50 , 50 , 50 , 50 , 20 , 10 ,
10 , 15 , 30 , 30 , 30 , 30 , 15 , 10 ,
0 , 10 , 10 , 10 , 10 , 10 , 10 , 0
};
static const int orderbishop[64] = {
80 , 60 , 50 , 30 , 30 , 50 , 60 , 80 ,
60 , 80 , 60 , 50 , 50 , 60 , 80 , 60 ,
50 , 60 , 80 , 60 , 60 , 80 , 60 , 50 ,
30 , 50 , 60 , 80 , 80 , 60 , 50 , 30 ,
30 , 50 , 60 , 80 , 80 , 60 , 50 , 30 ,
50 , 60 , 80 , 60 , 60 , 80 , 60 , 50 ,
60 , 80 , 60 , 50 , 50 , 60 , 80 , 60 ,
80 , 60 , 50 , 30 , 30 , 50 , 60 , 80
};
static const int orderkingmid[64] = {
80 , 80 , 80 , 40 , 40 , 70 , 80 , 40 ,
20 , 20 , 20 , 10 , 10 , 20 , 20 , 20 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0
};
static const int orderkingend[64] = {
0 , 10 , 20 , 40 , 40 , 20 , 10 , 0 ,
10 , 20 , 30 , 50 , 50 , 30 , 20 , 10 ,
20 , 30 , 40 , 60 , 60 , 40 , 30 , 20 ,
40 , 50 , 60 , 80 , 80 , 60 , 50 , 40 ,
40 , 50 , 60 , 80 , 80 , 60 , 50 , 40 ,
20 , 30 , 40 , 60 , 60 , 40 , 30 , 20 ,
10 , 20 , 30 , 50 , 50 , 30 , 20 , 10 ,
0 , 10 , 20 , 40 , 40 , 20 , 10 , 0
};
static const int orderrook[64] = {
10 , 10 , 10 , 20 , 20 , 10 , 10 , 10 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
20 , 20 , 20 , 20 , 20 , 20 , 20 , 20 ,
80 , 80 , 80 , 80 , 80 , 80 , 80 , 80 ,
40 , 40 , 40 , 40 , 40 , 40 , 40 , 40
};
static const int *midordertab[] = {
0,
orderpawn, orderpawn,
orderknight, orderknight,
orderbishop, orderbishop,
orderrook, orderrook,
orderrook, orderrook,
orderkingmid, orderkingmid
};
static const int *endordertab[] = {
0,
orderpawn, orderpawn,
orderknight, orderknight,
orderbishop, orderbishop,
orderrook, orderrook,
orderrook, orderrook,
orderkingend, orderkingend
};
void cMovelist::init_opt()
{
opt->histab = true;
opt->mvvlva = true;
opt->killer = true;
opt->hashmove = true;
opt->matekiller = true;
}
void cMovelist::resethistab()
{
uint pce,sq;
for(pce = pE; pce <= pbK; ++pce)
{
for(sq = 0; sq < BRDSQ; ++sq)
histab.value[pce][sq] = 1;
}
histab.max = 1;
}
void cMovelist::resetstats()
{
stats.killer1=stats.killer2=stats.matekiller=0;
stats.histab=stats.capture=stats.badcapture=stats.hashmove=0;
stats.qprom=stats.minorprom=0;
stats.epcapture=stats.castle=0;
}
void cMovelist::resetkillers()
{
for(uint i = 0; i < maxply; ++i)
{
killers.k1[i]=killers.k2[i]=killers.mk[i]=NULLMOVE;
}
}
void cMovelist::scoremove(uint move, uint depth, uint pce)
{
uint to = TO(move);
//histab.value[pce][to] += depth*depth;
histab.value[pce][to] += depth;
if(histab.value[pce][to] > histab.max)
histab.max = histab.value[pce][to];
}
void cMovelist::failowmove(uint move, uint depth, uint pce)
{
uint to = TO(move);
if(histab.value[pce][to]>depth*depth)
{
histab.value[pce][to] -= depth*depth;
if(histab.value[pce][to] < 1)
histab.value[pce][to] = 1;
}
}
void cMovelist::score_killer(uint move, int score, uint ply)
{
if(score > matescore-200)
{
killers.mk[ply] = move;
return;
}
if( !(FlagCAPEP&move) )
{
if(move != killers.k1[ply])
{
killers.k2[ply] = killers.k1[ply];
killers.k1[ply] = move;
}
else
{
killers.k2[ply] = move;
}
}
}
cMovelist::cMovelist()
{
uint pce,sq;
for(pce = pE; pce <= pbK; ++pce)
{
for(sq = 0; sq < BRDSQ; ++sq)
histab.value[pce][sq] = 1;
}
histab.max = 1;
init_opt();
}
int cMovelist::ordercapture(uint move, cBoard &pboard, cMaterial &material)
{
int from,to,val;
from = FROM(move);
to = TO(move);
uint side;
uint pcefrom = pboard.p2board()[from];
uint pceto = pboard.p2board()[to];
if(PROM(move))//promotion
{
if(PROM(move)==pbQ||PROM(move)==pwQ)//queen
{
stats.capture++;
return Q_PROM_CAPT;
}
else
{
stats.badcapture++;
return MINORPROM;
}
}
else//not a prom
{
val = piecevals[pceto] - piecevals[pcefrom];
if(val>0)
{
stats.capture++;
return WIN_CAPT+val;
}
else if(val == 0)
{
stats.capture++;
return equalcap[pcefrom];
}
else
{
side = pboard.getside();
if(isattack(pboard, material, side^1, to))
{
stats.badcapture++;
return 1;
}
else
{
stats.capture++;
return SEECAP;
}
}
}
}
void cMovelist::ordermove(uint move, uint &cap, const uint &flag, const uint &prom, uint &ply, uint pce, cBoard &pboard, int *score, cMaterial &material)
{
*score = -200;
if(move==pvmove && opt->hashmove)
{
*score = HASH;
stats.hashmove++;
}
else if(opt->matekiller && move==killers.mk[ply])
{
*score = M_KILLER;
stats.matekiller++;
}
else if( cap && opt->mvvlva )
{
*score = ordercapture(move, pboard, material);
}
else if(move & FlagEP)
{
*score = GCAP_PP;
stats.epcapture++;
}
else if(prom!=pE)
{
if(prom==pwQ||prom==pbQ)
{
*score=Q_PROM;
stats.qprom++;
}
else
{
*score=MINORPROM;
stats.minorprom++;
}
}
else if(move==killers.k1[ply] && opt->killer)
{
*score = KILLER1;
stats.killer1++;
}
else if(move==killers.k2[ply] && opt->killer)
{
*score = KILLER2;
stats.killer2++;
}
else if (move & FlagCA)
{
stats.castle++;
if(files[TO(move)]==FILEC)
{
*score = OOO;
}
else
{
*score = OO;
}
}
else
{
if((material.getmaterial(cW) + material.getmaterial(cB)) > ENDMAT)
{
tab = midordertab[pce];
}
else
{
tab = endordertab[pce];
}
*score=tab[sqto64(TO(move))]-tab[sqto64(FROM(move))];
stats.histab++;
}
}
void cMovelist::addpawnmove(uint &from, uint &to, uint &cap, uint side, uint &ply, uint pce, cBoard &pboard, cMaterial &material)
{
if(side==cW)
{
if(ranks[from]==RANK7)
{
this->addmove(from,to,cap,FlagE,pwQ,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pwN,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pwR,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pwB,ply,pce,pboard,material);
}
else
{
this->addmove(from,to,cap,FlagE,FlagE,ply,pce,pboard,material);
}
}
else
{
if(ranks[from]==RANK2)
{
ASS(ranks[to]==RANK1);
this->addmove(from,to,cap,FlagE,pbQ,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pbN,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pbR,ply,pce,pboard,material);
this->addmove(from,to,cap,FlagE,pbB,ply,pce,pboard,material);
}
else
{
this->addmove(from,to,cap,FlagE,FlagE,ply,pce,pboard,material);
}
}
}
void cMovelist::addmove(uint &from, uint &to, uint &cap, const uint &flag, const uint &prom, uint &ply, uint pce, cBoard &pboard, cMaterial &material)
{
uint count = movecount[ply];
uint move = (from | (to<<7) | (cap<<16) | (prom<<20) | flag);
movelist[ply][count] = move;
movescores[ply][count] = -200;
ordermove(move, cap, flag, prom, ply, pce, pboard, &movescores[ply][count], material);
movecount[ply]++;
}
and for completeness...
class cMovelist {
private:
uint movelist[maxply][maxmoves];
uint movecount[maxply];
int movescores[maxply][maxmoves];
sHistab histab;
sKillers killers;
uint pvmove;
sOrderstats stats;
const int *tab;
cMovelist( const cMovelist & );
cMovelist &operator = ( const cMovelist & cMovelist);
void cMovelist::ordermove(uint move, uint &cap, const uint &flag, const uint &prom, uint &ply, uint pce, cBoard &pboard, int *score, cMaterial &material);
int ordercapture(uint move, cBoard &pboard, cMaterial &material);
public:
cMovelist();
sScoreOpt opt[1];
void init_opt();
uint *p2list(uint &ply) {return movelist[ply];}
int *p2scores(uint &ply) {return movescores[ply];}
uint &getcount(uint &ply) { return movecount[ply]; }//shows for current ply
uint &getpvmove() { return pvmove; }
void setpvmove (uint pvm) { pvmove = pvm; }
void printmovelist(uint &ply);//prints movelist for the current ply
void printatplymovelist(uint ply);//prints movelist for the given ply
void resetcount(uint &ply) { movecount[ply]=0;}
void incrmovecount(uint &ply) { this->movecount[ply]++; }
void addmove(uint &from, uint &to, uint &cap, const uint &flag, const uint &prom, uint &ply, uint pce, cBoard &pboard, cMaterial &material);
void addpawnmove(uint &from, uint &to, uint &cap, uint side, uint &ply, uint pce, cBoard &pboard, cMaterial &material);
void scoremove(uint move, uint depth, uint pce);
void failowmove(uint move, uint depth, uint pce);
void score_killer(uint move, int score, uint ply);
void resethistab();
void resetkillers();
void resetstats();
void says_stats();
};
@ HG - Thanks for the tip about those stats. I thought I was printing detailed enough info... obviously not!
@Roman - this is without root sorting. Your 92% seems a little better!!
Also, if I add PVS
Code: Select all
int played=0;
for(uint i = 0; i < mlist.getcount(game.getply()); ++i)
{
picknext(i,mlist);
if (makemove(game,mat,his,list[i]))
{
takemove(game,mat,his);
continue;
}
check = incheck(game,mat,game.getside());
ext = 0;
if(check) { stats->checkext++; ext = 1; }
if (played==0 && opt->pvs)
{
stats->pvssearch++;
val = -alphabeta(-alpha-1, -alpha, depth-1+ext, true, check);
if ((val > alpha) && (val < beta))
{
stats->pvsresearch++;
val = -alphabeta( -beta, -alpha, depth-1+ext, true, check);
}
}
takemove(game,mat,his);
if(status->stopped == STOPPED) { return 0;}
played++;
from = FROM(list[i]);
if (val > alpha)
{
..etc
I don't have time tonight, but I will look at this tomorrow evening after work, starting with some stats by depth as in the table above.
Thanks for the replies...
Although, one thing I did notice. I left the other engines with PVS on. When I turned this off, they weren't much different than Jabba.
So the problem could well be the PVS implementation... sorry.
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering help
No problem, I can read and understand most of your code quite well!Richard Allbert wrote:It'll be rather long.... because I do this in the movelist class... (which is used by the move generator).
Not quite. But there some issues.Richard Allbert wrote:That's all a mess isn't it?Code: Select all
// snipped (EDIT: and improved indentation) int cMovelist::ordercapture(uint move, cBoard &pboard, cMaterial &material) { // ... if(PROM(move))//promotion { // ... } else//not a prom { val = piecevals[pceto] - piecevals[pcefrom]; if(val>0) { stats.capture++; return WIN_CAPT+val; } else if(val == 0) { stats.capture++; return equalcap[pcefrom]; } else { side = pboard.getside(); if(isattack(pboard, material, side^1, to)) { stats.badcapture++; return 1; } else { stats.capture++; return SEECAP; } } } }
1) You don't really do MVV/LVA for the winning and equal captures. Instead you score winning captures by the difference of piece values, and you score all equal captures lower than winning captures. This results in a different order compared to original MVV/LVA for some cases. It may turn out that your method is sufficient, though, but many people do it differently. For instance, usually QxQ is always tried before PxN since QxQ removes a queen from the board which reduces the tree quite well.
2) For potentially losing captures (capturing a minor piece), you make the score depend on whether the captured piece is defended, by calling isattack(). If it is defended then you regard the move as bad capture, otherwise you assign a constant score SEECAP which is lower than all scores for equal captures. Both is not quite what I would do.
a) "Defended": Consider captures like NxP, RxP, QxP. Even if the pawn is defended it is not clear whether you have a bad capture since it will depend on the value of the "least defender", and maybe as well on the presence of more attackers and defenders. As long as you do not take that into account you cannot conclude having a bad capture. Doing so may wrongly put many captures to the end of the move list. Knowing that the least defender is a pawn would already be better, although this would restrict the set of bad captures you can recognize.
b) "Not defended": Here you have more information than you are using, in fact you have identified a winning capture, so why not scoring it accordingly? IMO it is better to score QxR (undefended) higher than PxN, for instance, although there may be other opinions. Also capturing an undefended queen should go before capturing an undefended pawn, for instance, but you assign the same score for both.
I think that using SEE for potentially losing captures is much better than your method of calling isAttack(), and I also believe that isAttack() is too expensive when considering the very small amount of information you get returned and can use in your case. If you don't want to implement SEE right now then you will have to fix your "compromise" solution at least, or fully stick with plain MVV/LVA instead without even trying to detect bad captures.
I'm currently having the same problem with my new engine: I do not have a fully satisfying SEE implementation yet but I wish to detect at least some subset of bad captures. So what I currently do is to find out, for potentially losing captures, whether the least defender is a pawn or, in some cases, a minor piece. It is a compromise that seems to work, but of course I want to replace this by SEE asap.
Sven