multi-dimensional piece/square tables

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

multi-dimensional piece/square tables

Post by PK » Fri Jul 04, 2014 1:12 pm

hi,

I am playing with the idea of indexing piece/square tables by [piece][square][ownKingPosition][enemyKingPosition]. Of course this design choice would prevent updating them incrementally and thus would effectively prevent the usage of lazy eval (not that I am a big fan of it!), but on the other hand would enable encoding some basic pattern knowledge in a really efficient manner. Now, what information can be encoded this way? So far I can think of:

- distance to enemy king - not necessarily useful with a real king safety function (so far equal score after 500 games), but might be stylistically pleasing
- rook trapped by uncastled king
- marginal endgame pattern of a knight in a corner caught by a king
- some defensive setups (Kg8 + Bg7 or Bf8 or Nf8 etc.) that would otherwise require clumsy if/else statement
- if passed pawn scores are encoded this way, king distance is an obvious candidate
- ditto for weak pawns in the endgame

Another way would be to create such tables via data mining, but I have no exprerience in this field.

Any thoughts on this replacement of pre-processing?

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: multi-dimensional piece/square tables

Post by ZirconiumX » Fri Jul 04, 2014 1:34 pm

PK wrote:hi,

I am playing with the idea of indexing piece/square tables by [piece][square][ownKingPosition][enemyKingPosition]. Of course this design choice would prevent updating them incrementally and thus would effectively prevent the usage of lazy eval (not that I am a big fan of it!), but on the other hand would enable encoding some basic pattern knowledge in a really efficient manner. Now, what information can be encoded this way? So far I can think of:

- distance to enemy king - not necessarily useful with a real king safety function (so far equal score after 500 games), but might be stylistically pleasing
- rook trapped by uncastled king
- marginal endgame pattern of a knight in a corner caught by a king
- some defensive setups (Kg8 + Bg7 or Bf8 or Nf8 etc.) that would otherwise require clumsy if/else statement
- if passed pawn scores are encoded this way, king distance is an obvious candidate
- ditto for weak pawns in the endgame

Another way would be to create such tables via data mining, but I have no exprerience in this field.

Any thoughts on this replacement of pre-processing?
Too big. 24MiB of PSTs is way too big, and a pain to tune.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

BeyondCritics
Posts: 359
Joined: Sat May 05, 2012 12:48 pm
Location: Bergheim

Re: multi-dimensional piece/square tables

Post by BeyondCritics » Fri Jul 04, 2014 3:19 pm

Hi,

as a chess player i am very critical about it, because you can not reliably encode positional chess knowledge into this scheme. Since you cannot determine piece placement based only on the position of the kings, this is like "coffee house chess". Putting pieces into the vicinity of the enemy king is always dangerous but often antipositional. A competent chess player will refute this strategy.

Steinitz was the first to note this for chess as a general principle: In order to attack you must have some sort of advantage or precondition. You cannot always attack.

E.g.: A typical precondition is control of the center. If you decentralize your pieces to attack a king on the wing and the centre is not closed, the typical refutation is a counter attack through the centre. This is standard chess strategy.

So this scheme is disgusting for a chess player, but it may work for a chess engine, i have no idea about that, this goes without saying.

The pawns are the back bone of the position. If i would try to refine psq tables, i would consider the pawns.
Most import are the pawns in the centre, than the pawns c and f and then the pawns on the wings.

To extract reliable positional information from the position i would consider pawns c,d,e and f. Disregarding doubled pawns, that gives you (8*7/(2*1))^ 4 = 28^4 = 614656 different tables, this would be way too much.
One way to get this managable would be as follows:
Build up a database of n different important pawn positions c, d, e, and f. Attach any parameters you want to this pawn configuration, including a psq table.
Now if have you have an arbitrary pawn position, select the m positions out of the n database positions, which are the "nearest" to your given position in a sense. Then simple build the mean of the parameters attached to these m database position. So to get your psq table, build the mean of the m returned psq tables.
Since this is really slow, you would then cache the results. I was told there are only a few thousand pawn positions per search or so, so this seems doable.
What do you think of this idea?

Oliver

bob
Posts: 20896
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: multi-dimensional piece/square tables

Post by bob » Fri Jul 04, 2014 4:14 pm

PK wrote:hi,

I am playing with the idea of indexing piece/square tables by [piece][square][ownKingPosition][enemyKingPosition]. Of course this design choice would prevent updating them incrementally and thus would effectively prevent the usage of lazy eval (not that I am a big fan of it!), but on the other hand would enable encoding some basic pattern knowledge in a really efficient manner. Now, what information can be encoded this way? So far I can think of:

- distance to enemy king - not necessarily useful with a real king safety function (so far equal score after 500 games), but might be stylistically pleasing
- rook trapped by uncastled king
- marginal endgame pattern of a knight in a corner caught by a king
- some defensive setups (Kg8 + Bg7 or Bf8 or Nf8 etc.) that would otherwise require clumsy if/else statement
- if passed pawn scores are encoded this way, king distance is an obvious candidate
- ditto for weak pawns in the endgame

Another way would be to create such tables via data mining, but I have no exprerience in this field.

Any thoughts on this replacement of pre-processing?
First, the precise definition of "pre-processing" is to do some computation before the search starts for a given position. PSTs are good examples. But today this is a non-functional idea, because we are seeing depths well beyond 20 plies. That means the king location at the start of the search is nowhere near where the king might be located at a terminal position. Most abandoned this years ago.

And once you abandon it, that problem goes away. But now all your PST values can represent are just "typically good or bad squares for the piece in question."

I use king location for things like passed pawn race tests. "Can this pawn promote without the enemy king being able to catch it (square of the pawn rule)?" It is natural there, but then it is also "absolute" data.

User avatar
velmarin
Posts: 1600
Joined: Mon Feb 21, 2011 8:48 am

Re: multi-dimensional piece/square tables

Post by velmarin » Fri Jul 04, 2014 4:56 pm

PK wrote:that would otherwise require clumsy if/else statement
I use HEX definitions

Code: Select all

#define SideQueen    0x0F0F0F0F0F0F0F0F   // Files= A,B,C,D
#define SideKing     0xF0F0F0F0F0F0F0F0   // Files= E,F,G,H
#define CenterBoard  0x1818181818181818   // Files= D,E
#define CenterAmplio 0x3C3C3C3C1C3C3C3C   // Files= C,D,E,F
#define WingKing     0xE0E0E0E0E0E0E0E0   // Files= F,G,H
#define WingQueen    0x0707070707070707   // Files= A,B,C
And in evaluation clumsy if, else
in pawns and all piezes, but requires much adjustment.

Code: Select all

if ((wBitboardK & SideQueen) && (bBitboardK & SideKing))
		{
			Value -= THOR_QK_B[b];
		}
		if ((wBitboardK & SideQueen) && (bBitboardK & SideQueen))
		{
			Value -= THOR_QQ_B[b];
}
ect, ect
		
With Bitboards, ect, is extremely fast, no losses.

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: multi-dimensional piece/square tables

Post by PK » Fri Jul 04, 2014 5:13 pm

I meant holding these piece/squares in memory and using exact king location. This is similar to preprocessing because of initialization process, so I consider it as a replacement of this obsolete method.

As for the ugliness - they are no more ugly than generalized tables, the only ugly thing about them is the amount of space they take. King distance certainly would not be a dominant factor (something like [-7...+6] range when knight pst uses the range [-40..+25]

As for using some general cathegorization of pawn structure instead, I'm afraid one has to be very careful then, much more careful than with king placement. Let's imagine reasonably static Carlsbad structure: White pawns on d4 and e3, half-open c file, black pawns on b7, c6 and d5, half-open e file. I've seen all the possible castling arrangements there, but generally speaking white has three basic ways to handle this pawn structure: good old minority attack with short castle, kingside pawn storm with long castle and play in the center with f3 and e4. Not much in common between these schemes, except perhaps that Ne2 is probably as good as Nf3. But the real problem starts after adding a little bonus for Ne2 in this structure - if it is meaningful enough, one would have to phase it out (decrease, but not delete) in a couple of pawn structures that Carlsbad can transform into. King distance might be clumsy, but at least reasonably continous.

User avatar
velmarin
Posts: 1600
Joined: Mon Feb 21, 2011 8:48 am

Re: multi-dimensional piece/square tables

Post by velmarin » Fri Jul 04, 2014 6:12 pm

bob wrote:But today this is a non-functional idea, because we are seeing depths well beyond 20 plies. That means the king location at the start of the search is nowhere near where the king might be located at a terminal position. Most abandoned this years ago.
It is a good explanation.

Yuri osipov says by "Strelka 6" including the PST directly eval,
This may be an idea made ​​in "Houdini 4".

You can earn some proof.

Tony P.
Posts: 99
Joined: Sun Jan 22, 2017 7:30 pm
Location: Russia

Re: multi-dimensional piece/square tables

Post by Tony P. » Tue Jan 28, 2020 4:32 am

Sorry for necromancy - I want to credit Pawel for considering PSTs involving more than 1 piece location.

I've stumbled upon a 2018 preprint 'Comparison Training for Computer Chinese Chess' (the final version of the article was published in IEEE Transactions on Games in January 2019) by Wen-Jie Tseng, Jr-Chang Chen, I-Chen Wu, and Ting-Han Wei, who claimed that their modifications of a xiangqi engine Chimo that included eval features that they denoted as LOC2 - features that indicated pairwise interactions of pieces, could be indexed by [piece1color][piece1type][piece1square][piece2color][piece2type][piece2square], for many or even all the pairs of pieces - performed clearly better at very fast TC (0.4 sec/move on Intel Core i5-4690) than the modifications that didn't include such features, despite the former modifications (denoted as EVAL10-13) having >120K eval parameters that were hard to train (and whose training probably hadn't even converged) while the latter (EVAL0-9) had <=730 params.

Seeing how much success A0 and lc0 have had despite having to train millions of weights, I guess that adding and tuning pairwise PSTs with <300K values in total (out of which, at most a few hundred would be used per position) could strengthen an A/B engine, which I certainly wouldn't have imagined before the A0 papers. Is anyone brave enough to spend plenty of effort on this idea? :mrgreen: Or is Western chess too different from xiangqi for it to ever work?

The approach can be extended to certain triples of pieces, like a certain piece plus both kings as Pawel initially suggested -
PK wrote:
Fri Jul 04, 2014 1:12 pm
I am playing with the idea of indexing piece/square tables by [piece][square][ownKingPosition][enemyKingPosition].
- but that would add even more params, so caution is needed. I've simply brought up an extra data point (the preprint) in support of the general idea of multi-piece PSTs.

Tony P.
Posts: 99
Joined: Sun Jan 22, 2017 7:30 pm
Location: Russia

Re: multi-dimensional piece/square tables

Post by Tony P. » Tue Jan 28, 2020 4:57 am

Also, while we're at it, let me necro HGM's rotated nibbleboard idea from the WB forum as well :wink:

I'm still not sure if it's best to store 2, 3 or 4 bits of info per square.

The problem with 4 bits/sq (hence 32 bits per ray) is that the LUT would be too large to fit into RAM, but unlike in 2006, it would be small enough to fit onto an SSD, and it could probably be hashable in RAM, as only a small part of it would be needed in the search from a certain position.

PK
Posts: 861
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: multi-dimensional piece/square tables

Post by PK » Tue Jan 28, 2020 12:16 pm

Perhaps I will revisit this idea at some point. Additional incentive is what I've done in Rodent IV. It calculates two different, competing piece/square table scores for the entire board, and then does weighted average of them, pulling result towards better of the scores (more so if score difference is bigger). This is of course not as robust as a full-blown neural network, but still a neat way to add some form of second-order non-linear scoring.

Post Reply