Simple quiet move sorting

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
AndrewGrant
Posts: 321
Joined: Tue Apr 19, 2016 4:08 am
Contact:

Simple quiet move sorting

Post by AndrewGrant » Sat Jan 13, 2018 8:55 am

So my current (not for long) method of sorting quietsis the following

Code: Select all

value =  getHistoryScore(*mp->history, move, board->turn, 512);
value += abs(PSQTMidgame[board->squares[MoveFrom(move)]][MoveTo(move)  ]);
value -= abs(PSQTMidgame[board->squares[MoveFrom(move)]][MoveFrom(move)]);
Basically just take the history score and add a little more/less based on PSQT


I've just got the following method to pass instead. It's almost like PSQT just for sorting, but much simpler.

Code: Select all

// Pawn, Knight, Bishop, Rook, Queen, King
static const int SortingTypes[KING+1] = {10, 8, 8, 4, 3, 1};

static const int SortingTable[SQUARE_NB] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    1, 2, 2, 2, 2, 2, 2, 1,
    1, 2, 4, 4, 4, 4, 2, 1,
    1, 2, 4, 6, 6, 4, 2, 1,
    1, 2, 4, 6, 6, 4, 2, 1,
    1, 2, 4, 4, 4, 4, 2, 1,
    1, 2, 2, 2, 2, 2, 2, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
};

value =  getHistoryScore(*mp->history, move, board->turn, 256);
value += SortingTypes[PieceType(board->squares[MoveFrom(move)])] * SortingTable[MoveTo(move)  ];
value -= SortingTypes[PieceType(board->squares[MoveFrom(move)])] * SortingTable[MoveFrom(move)];
Seems to beworth 7-10 elo @ 20+.02s. And I would say this is a method you could recommend to people just starting to do quiet move sorting. I'm sure this is not some new knowledge for sorting, but I have not seen this method on the forms or CPW.

Sven
Posts: 3578
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Simple quiet move sorting

Post by Sven » Sat Jan 13, 2018 9:37 am

Just one question: in both your old and new methods you combine
... MoveFrom ... MoveTo ...
... MoveFrom ... MoveFrom ...

Is this done by intent, or a copy&paste bug which should be corrected into
... MoveTo ... MoveTo ...
... MoveFrom ... MoveFrom ...
?

AndrewGrant
Posts: 321
Joined: Tue Apr 19, 2016 4:08 am
Contact:

Re: Simple quiet move sorting

Post by AndrewGrant » Sat Jan 13, 2018 10:06 am

Done by intent. first MoveFrom in each line is getting the piece type we are moving. The following MoveTo/MoveFrom is getting to to and from square, so we can see the difference in the SortingTables.

User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Re: Simple quiet move sorting

Post by Greg Strong » Sat Jan 13, 2018 9:12 pm

In the old code, I don't understand the use of absolute values. Looks like if you have any negative PST entries, you'll actually wind up doing the opposite of what you want (rewarding moving to a square with a value that is more negative.) Perhaps your new code is performing better because it doesn't have this bug?

AndrewGrant
Posts: 321
Joined: Tue Apr 19, 2016 4:08 am
Contact:

Re: Simple quiet move sorting

Post by AndrewGrant » Sat Jan 13, 2018 9:15 pm

Material values are also in the PSQT so I can update midgame/endgame eval with make/unmake move. So no, none of those numbers are negative, unless they are black. In which case, they all are. Hence the abs.

User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Re: Simple quiet move sorting

Post by Greg Strong » Sat Jan 13, 2018 11:25 pm

Got it. Makes sense.

User avatar
lucasart
Posts: 2957
Joined: Mon May 31, 2010 11:29 am
Contact:

Re: Simple quiet move sorting

Post by lucasart » Sat Jan 13, 2018 11:55 pm

AndrewGrant wrote:So my current (not for long) method of sorting quietsis the following

Code: Select all

value =  getHistoryScore(*mp->history, move, board->turn, 512);
value += abs(PSQTMidgame[board->squares[MoveFrom(move)]][MoveTo(move)  ]);
value -= abs(PSQTMidgame[board->squares[MoveFrom(move)]][MoveFrom(move)]);
Basically just take the history score and add a little more/less based on PSQT


I've just got the following method to pass instead. It's almost like PSQT just for sorting, but much simpler.

Code: Select all

// Pawn, Knight, Bishop, Rook, Queen, King
static const int SortingTypes[KING+1] = {10, 8, 8, 4, 3, 1};

static const int SortingTable[SQUARE_NB] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    1, 2, 2, 2, 2, 2, 2, 1,
    1, 2, 4, 4, 4, 4, 2, 1,
    1, 2, 4, 6, 6, 4, 2, 1,
    1, 2, 4, 6, 6, 4, 2, 1,
    1, 2, 4, 4, 4, 4, 2, 1,
    1, 2, 2, 2, 2, 2, 2, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
};

value =  getHistoryScore(*mp->history, move, board->turn, 256);
value += SortingTypes[PieceType(board->squares[MoveFrom(move)])] * SortingTable[MoveTo(move)  ];
value -= SortingTypes[PieceType(board->squares[MoveFrom(move)])] * SortingTable[MoveFrom(move)];
Seems to beworth 7-10 elo @ 20+.02s. And I would say this is a method you could recommend to people just starting to do quiet move sorting. I'm sure this is not some new knowledge for sorting, but I have not seen this method on the forms or CPW.
Interesting idea, but I wonder if this is really valuable in itself, or works like a placebo.

What if you revert this patch, and instead increase HistoryMax ?

I find it surprising that a static method like that would somehow improve on history, which is extremely strong and scalable in my experience.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Post Reply