Would someone be interested in programming....

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Fri Sep 21, 2007 9:18 am

neoliminal wrote:Unfortunately yes and no.

It does require a board configuration to test against.

I have done it by hand and did use a spreadsheet to calculate values, but again, this was tedious...and prone to error as someone pointed out to me later. (Very embarrassing)
It all sounds very vague. Why not simply post your method here, so that we all understand what it is about, and if it is something we would be interested to do?

neoliminal

Re: Would someone be interested in programming....

Post by neoliminal » Sat Sep 22, 2007 2:27 am

Here is my method... thorny warts and all:
This is a bit involved so let me say from the outset that my goal is to allow for a relatively objective value of a piece when there is no reasonable method to determine it's value.

I started with the assumption that I wanted to use a fairly standard game of chess as the basis for the analysis. I choose ECO C97 up to the 9th move:

r1bq1rk1/2p1bppp/p2p1n2/np2p3/4P3/1BP2N1P/PP1P1PP1/RNBQR1K1 b - - 0 1

I choose this position because there were no captures and both kings had castled. This resulted in 32 open spaces. I assumed the new piece was Black and placed it in each of the 32 open spaces. The following rules were applied:

A. For each piece that could be either guarded or captured by the piece, it scored points equal to that pieces normal value.

Example: A Queen on d5 could guard Pawns on b5, d6, f7, and e5 each valued at 1 point for a total of 4 points and the Rook at a8 for 5 points. It could also attack the two Pawns e4 and d2, for 2 more points and a Bishop at b3 for 3 points. In total the d5 square was worth 14 points.

B. If the piece was in danger by a piece it could not capture, it scored zero points.

Example: A Knight on d5 could be attacked by the Bishop at B3, but could not capture that piece itself. Even though the Knight could theoretically protect a Pawn, Bishop, and a Knight, it gained no points for these because it could be captured by a piece it would not capture.

C. The King was valued at 20 points.

Example: A rook on h1 would gain 20 points points for the King and 1 point for the Pawn on h3.

D. Promoted Pawns on the last rank were given half the value of a Queen.

Example: A pawn on h1 would be worth half the value of a Queen because it could promote. A Queen on h1 is worth 22, so for a pawn it was worth 11.

All the squares were then added together as divided by 37 and rounded to their nearest whole number. The results were exact matched to the standard values normally given these pieces.

Q = 9 (9.3) 344
R = 5 (4.84) 179
B = 3 (3.05) 113
N = 3 (3.27) 121
P = 1 (1.14) 42

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Sat Sep 22, 2007 9:04 am

Well, that sounds easy enough to program. In what format should the description of the fairy piece be entered?

I am wondering how well your method will do in practice, though. I note that you don't give any points at all for mobility (i.e. moves to empty squares). According to Ralph Betza's theory for piece evaluation, piece characteristics like speed, manoeuvrability and forwardness are all important for its value. E.g., in pieces that have different moves for capture and non-capture (such as FIDE Pawns), your method would be blind to the non-captures. A piece that captures as a Knight and moves as a King would obviously less valuable as a piece that capttures as a Knight and moves like a Queen. (Speed) A Knight has more speed than a King, but less manoeuvrability, so in practice a Knight is worth less then a (non-royal) King (Commoner).

neoliminal

Re: Would someone be interested in programming....

Post by neoliminal » Sat Sep 22, 2007 2:51 pm

I hadn't considered this mobility. Funny, I was trying to find a way to measure the "Pao", the chinese chess cannon piece. This is exactly the type of thing you are talking about. Perhaps I'll have to measure movement separately somehow. I guess it was being measured for normal "move/capture" pieces in the system naturally because the numbers came out to fit FIDE (after scaling).

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Sat Sep 22, 2007 4:01 pm

I can imagine that it is possible to determine piece values the way you propose (perhaps weighting non-captures in, and using different weights for forward and backward moves, and giving a penalty for color-boundedness (or access to an even smaller subset of squares only), and counting how many moves you need to get to a neighbor square.

The problem is that the FIDE pieces are a very poor calibration material, as they move and capture the same, and have forward/backward symmetry. So how would you ever know if your system is any good.

I guess we really should measure the strength of some key pieces in games. E.g. play 1,000 fast games with the piece replacing a FIDE piece that we think is roughly similar in strength, for one side only, and measure how much a score advantage / disadvantage this conveys. From that we could deduce how to weigh the various aspects.

I once tried something like that to determine the value of Ferz and Wazir: reprogrammed micro-Max to have white play with Wazirs in stead of Pawn, and black with Ferzes. (This is easy in uMax, as white and black Pawns are considered different piece types.) I figured that using eight of them would ampplify any value difference (which I expected the difference to be pretty small). It seemed the Ferzes were stronger (as Ralph Betza had claimed), but the results were not very clear-cut. One problem was that without Pawns, the game became very drawish (2 Wazirs or Ferzes have no mating potential). Chess really isn't Chess without Pawns. So perhaps it would have been smarter to play with seven W and F in stead of the pieces, and leave the Pawns. Or just replace the Queen's with 3 of the fairy pieces under test. (And mirror the black initial array to prevent that the fairy pieces mainly face each other, rather than a mix of normal chess pieces.)

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Sun Sep 23, 2007 9:44 am

I thought some more about this. Problem in getting an accurate measurement is that it requires a large enough sample of independent games. Playing several games from the same initial position leads to many identical, or mostly identical games in most engines (uMax typically only varies one move in ~40, so the first 40 moves of all games are likely to be the same, and the game might bedecided by that time even if it is not finished). Usually one gets around this by chosing random lines from an opening book, but with non-standard pieces we of course have no opening theory available.

So my idea is to vary the initial setup. I want each FIDE piece type to be present, and have an array of 8 pawns with all the pieces behind it. The fairy piece of which the value should be determined should be present twice (to increase sensitivity to its value). The other 6 pieces are one K,Q,R,N, and two B. The latter I want two, to measure B-pair effects, and I want them to start on differently colored squares. The same holds for the two exo-pieces, just in case they are color-bound as wel (e.g. Camels).

As uMax only implements normal FIDE castling rules, the King needs to be in the center (on d- or e-file), and the Rook in one of the corners. This leaves 2 possible locations for the King. If the Rook is on the short side, the remaining 6 squares are divided 3-3 over colors. The Bishops can thus placed in 3x3=9 ways, and the exo-pieces then in 2x2=4 ways. The remaining two squares can accept Q+N in 2 ways. So in total 9x4x2=72 ways.

With the Rook on the long side, the remaining squares are divided 4-2 over colors. Thus 4x2=8 ways to put the Bishops, then 3x1=3 for the exo-pieces, and 2 for Q+N, total 8x3x2=48. In total 72+48=120 ways to put the pieces for a given King position, 240 possibilities for one side.

There is no need for white and black to use the same starting array, as they will have different exo-pieces anyway. So chosing them independently leavs 240x240 possible starting positions, but left-right symmetry of the board makes only 28,800 really different. But uMax does not not respect the board symmetries, though, as it scans the board in a particular direction when generating moves. So in general a mirrored position will lead to different games. A given position can be put in 8 ways on the board (forward-backward and left-right mirror images, and black-white reversals).

So there really is an enormous number of independent games we could select from. To eliminate any bias w.r.t. colors or board orientation, we would have to play each initial setup 8 times. So it should be possible to play the 2,500 independent games that are needed to determine the score percentage to 1% accuracy, and that should be enough to derive an accurate piece value from it according to Kaufman's method.

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Mon Oct 01, 2007 12:25 pm

OK, I made some progress on this.

I decided for not randomizing the initial position after all (which would be a drudge, as I would somehow have to tell the GUI about the starting positions, which would require me to generate them as a separate file of FENs, and I could not use fairy pieces in the FENs without the GUI choking on it). So what I do now is start from the regular opening position, randomizing the first 3 moves (6 ply) of the game by adding a 32 cP random to the score of every move in the root. That basically means that every move that does not immediately give away material becomes equally likely, as the random outweighs normal positional factors in uMax.

The engines are then programmed know which of the FIDE pieces to replace by the exo-piece. (In the future I will make them read this info from a file, also describing the fairy piece.) The GUI (I use Winboard_x) doesn't know about this, and displays the exo-piece as the FIDE piece that normally starts in that position. Obviously I have to switch 'test move legality' off for this to work. It is a pain to have, say, Camels show up as Knights, but I have no idea as to how to make the GUI display fairy pieces.

I patched uMax to use the piece codes for 'anti-Pawns' (white Pawns that move as black Pawns, and vice versa) for the exo-piece. I had to use this kludge, as uMax only uses 3 bits for the PieceType, and all of the 8 codes were taken, as white and black Pawns are considered different PieceType (and I need empty squares to have a unique piece type too). But this works now, so that both white and black can each have one exo-piece, and it can be a different one for black and for white.

Currently my procedure is to give only one side exo-pieces, but alternate this between black and white on odd and even games. As the GUI assumes that the same player alternately plays black and white, it adds up the game results in such a way that it becomes a match between a player having exo-pieces, and a player with the normal FIDE set. In addition the white vs black advantage is averaged out.

Early results

Camels

I had one side play with Camels in stead of Knights. When I tell both players that the Camels are worth as much as the Knights (280 cP in uMax), the Camels lose by 74%. So it seems they are not equally valuable to Knights at all. So I reduced the piece value of the Camel to 240 cP. This improved the Camel score over 185 games from 26% to 28% (and strangely enough to 31% when I did it, due to a bug, in only half of the games, so there probably was a quite unfavorable statistical fluctuation here). Now I am running a test with the Camel value set to 200 cP, to see if this makes the Camels score even better.

The Camels ((3,1) leapers) are intrinsically worth much less than Knights ((2,1) leapers), but making the program aware of this helps, as it then starts to quickly trade the Camels for more valuable material when this is still possible. (A Camel can give forks like a Knight, from even longer distance, so on a crowded board where everything is worth more than a Camel, usually opportunities can be created to make such swaps. The lower the Camel PieceValue, the more priority it gives to swapping them for other material.)

The idea is now to take the score for the Knights vs. Camels match for versions that handle the Camels best, (say 70%), and compare that to the score conveyed by the advantage of a Pawn. To determine the latter I did a Pawn-odds match, where I alternately removed f2 and f7. This seems to convey an advantage of 63% under the same cnditions as I played the exo-pieces (40/1' on a 2.4GHz Core 2 Duo). All this determined with far too few games yet, of course.

The Knights vs Camels thus gives an advantage to the Knights that is about 1.5 times as large as an extra Pawn. This suggests that the difference between N and C is 3/4 of a Pawn. A Pawn in uMax is actually worth only 80 cP, so this suggests a piece value for the Camel of 220 cP.

As it is a bit tricky to extrapolate the advantage of a Pawn to more extreme scores, I am now repeating the test where I only replace a single Knight by a Camel. This should then produce an advantage of 60% for the Knight, if the first measurement was any good.

Commoners

I also played Bishops against Commoners (non-royal Kings, also often referred to as Men). With equal piece values (320 cP in uMax, but no B-pair bonus) the Bishops win by 60%. This would suggest a 3/4-Pawn advantage (60 cP), so each Commoner might be worth 290 cP. I am currently double-checking this with the PieceValue of the Commoners set to 280 cP, to see if the difference persists if the players are aware that the Bishop is superior. Commoners are not long-range pieces, so it is difficult to force swapping them for other material if the opponent evades such swaps. So unlike the Camels, the value of the Commoner might actually go down with a more consistent evaluation. OTOH, with lower Comoner value it might swap them for Knights more easily, or at least, not fear such swaps, making the effective use of the Commoners higher.

Anyway, the initial value of a Commoner seems more like a Knight than like a Bishop. (Despite the Commoner having mate potential: KMK is generally won!) So perhaps it would make more sense to replace Knights by Commoners, rather than the Bishops. I also should be prepaired for the effect that the value of pieces in a game depend on their starting location. Especially for slow pieces like Commoners. They take three moves to go from a corner to the center, and there is a rule of thumb that equates 3 tempi to a Pawn... To test this I am going to also run a test with Commoners on c1/f1 and Bishops on b1/g1. This might be better for the Commoners than starting them at the Knight locations.

Alessandro Scotti

Re: Would someone be interested in programming....

Post by Alessandro Scotti » Mon Oct 01, 2007 1:09 pm

hgm wrote:The engines are then programmed know which of the FIDE pieces to replace by the exo-piece. (In the future I will make them read this info from a file, also describing the fairy piece.) The GUI (I use Winboard_x) doesn't know about this, and displays the exo-piece as the FIDE piece that normally starts in that position. Obviously I have to switch 'test move legality' off for this to work. It is a pain to have, say, Camels show up as Knights, but I have no idea as to how to make the GUI display fairy pieces.
If you don't have say Knights and Camels in the same game and you are using font-based pieces, you can try the /fontPieceToCharTable parameter that maps a piece to the corresponding font character. Some fonts (http://www.enpassant.dk/chess/fonteng.htm see Chess Berlin) may even have support for fairy pieces.

Edit: the Good Companion font also looks promising (http://www.enpassant.dk/chess/fontimg/gc.htm).

neoliminal

Re: Would someone be interested in programming....

Post by neoliminal » Mon Oct 01, 2007 2:14 pm

I also make piece sets. Should you figure out a way to include fairy pieces, I'd be happy to make whatever you need. Examples of my work can bee seen here:

http://wiki.schemingmind.com/SmWiki/PieceSets

(may require free registration)

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Would someone be interested in programming....

Post by hgm » Mon Oct 01, 2007 3:38 pm

Alessandro Scotti wrote:If you don't have say Knights and Camels in the same game and you are using font-based pieces, you can try the /fontPieceToCharTable parameter that maps a piece to the corresponding font character. Some fonts (http://www.enpassant.dk/chess/fonteng.htm see Chess Berlin) may even have support for fairy pieces.

Edit: the Good Companion font also looks promising (http://www.enpassant.dk/chess/fontimg/gc.htm).
Interesting. I guess this was implemented by you, so you must know a whole lot about how this works.

I guess if I would play white with Camels and black with Knights, I could simply set the white Knight of a fairy character (say an upside-down Knight), and leave the black Knight a standard Knight. I only run into trouble if white has both a Knight and a Camel.

Another problem is that alternating the Camels between black and white would not work anymore. The black Knights would continue to be displayed as ordinary black Knights in the games where black had the Camels, so that I still would not be able to see which side has the Camels without watching the game until one of them moves a Knight or Camel.

Would it be easy to expand the number of piece types in Winboard? (i.e. is this just the matter of changing a defined constant from 6 to, say, 9, or is the 6 hard-coded in many places in Winboard?)

I tried playing with the /fontPieceToCharTable option without giving a font, but then it is simply ignored. Where do the standard Winboard pieces come from? Are those stored as initialized data in the program, or are they read from bitmap files?

Post Reply