PSA that with the Ryzen 5000 series, AMD apparently fixed PDEP/PEXT
https://www.anandtech.com/show/16214/am ... x-tested/6
FEN compression
Moderators: hgm, Rebel, chrisw
-
- Posts: 96
- Joined: Fri Jul 06, 2018 1:09 am
- Location: Chicago, IL
- Full name: Josh Odom
-
- Posts: 12566
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: FEN compression
Specifically:
Code: Select all
Instruction Zen2 Zen3
PDEP/PEXT 300 cycle latency 250 cycles per clock 3 cycle latency 1 per clock
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: FEN compression
Definitely my next CPU when I finish frying my Intel i7.Dann Corbit wrote: ↑Thu Mar 18, 2021 2:54 am Specifically:Code: Select all
Instruction Zen2 Zen3 PDEP/PEXT 300 cycle latency 250 cycles per clock 3 cycle latency 1 per clock
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 12566
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: FEN compression
I am going to wait one (or possibly 2) more generations. Of course, I already have a 3970x and it has some life in it yet.lucasart wrote: ↑Thu Mar 18, 2021 4:31 amDefinitely my next CPU when I finish frying my Intel i7.Dann Corbit wrote: ↑Thu Mar 18, 2021 2:54 am Specifically:Code: Select all
Instruction Zen2 Zen3 PDEP/PEXT 300 cycle latency 250 cycles per clock 3 cycle latency 1 per clock
But I figure there will be a big shrink in either one more, or two more generations.
That might double the cores again and also boost the speed a lot at the same time.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: FEN compression
Update: removed useless ep bit.
I think this algorithm is provably optimal, at least when the metric is the worst case. The proof is basically obvious by just following each step of the algorithm.
Nitpick: if you assume that positions are legal, then you can reduce the cnt(candidates), in cases where you can infer that the double push would have been illegal. You can also infer turn when there is a check on the board. All this complicates code for negligible benefit in reducing avg(bits), so probably not worth it.
Code: Select all
itemname | bits | definition
--------------------------------------------|-----------
occupied | 64 |
pext(white,occupied) | cnt(occupied) |
black = occupied & ~white | 0 |
pext(pawns, occupied) | cnt(occupied) |
pext(knights, remaining) | cnt(remaining) | remaining = occupied & ~pawns
pext(bishops, remaining) | cnt(remaining) | remaining &= ~bishops
pext(rooks, remaining) | cnt(remaining) | remaining &= ~rooks
pext(queens, remaining) | cnt(remaining) | remaining &= ~queens
kings = remaining | 0 |
turn | 1 |
pext(epSquare, candidates) | cnt(candidates)| candidates = turn == black ? ((white & pawns & rank4) >> 8) : ((black & pawns & rank6) << 8)
pext(castleRooks, rooks) | cnt(rooks) | castleRooks = rooks with associated castling rights (any color)
rule50 | 7 |
fullMove | 10 | useless: conveys no position information
Nitpick: if you assume that positions are legal, then you can reduce the cnt(candidates), in cases where you can infer that the double push would have been illegal. You can also infer turn when there is a check on the board. All this complicates code for negligible benefit in reducing avg(bits), so probably not worth it.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 300
- Joined: Mon Apr 30, 2018 11:51 pm
Re: FEN compression
I don't think the proof is obvious by any means; you need to prove that your bit technique is more effective than any run-length or arithmetic coding option (it obviously wouldn't be if the board were bigger or the number of pieces were fewer). Also, you need to prove that the extra information from legality (e.g. side to move cannot be in check) cannot be used in any better way, e.g. by encoding the king's position earlier in the sequence and using that to reduce the number of bits you need to encode for other pieces.lucasart wrote: ↑Thu Mar 18, 2021 5:36 am Nitpick: if you assume that positions are legal, then you can reduce the cnt(candidates), in cases where you can infer that the double push would have been illegal. You can also infer turn when there is a check on the board. All this complicates code for negligible benefit in reducing avg(bits), so probably not worth it.
-
- Posts: 31
- Joined: Tue Feb 27, 2018 11:29 am
Re: FEN compression
I use this one, which (if I understand his code correctly) is quite similar to Andrew's:
The maximum of 26 bytes could be pushed down to 24 by having the white and black kings be separate piece types and by having rooks that can castle be a separate piece type, but I think the increased ugliness just isn't worth it for just two bytes.
Code: Select all
"""
compress(b::Board)
Compresses a board into a byte array of maximum 26 bytes.
Use the inverse function `decompress` to recover a compressed board.
"""
function compress(b::Board)::Vector{UInt8}
io = IOBuffer(UInt8[], read = true, write = true, maxsize = 26)
# Write occupied squares (8 bytes):
write(io, occupiedsquares(b).val)
# Write square contents, one nibble per occupied square:
nibble = 0
for s ∈ occupiedsquares(b)
# HACK: Encode a pawn that can be captured en passant differently
if pieceon(b, s) == PIECE_WP && s == epsquare(b) + DELTA_N
x = UInt8(7)
elseif pieceon(b, s) == PIECE_BP && s == epsquare(b) + DELTA_S
x = UInt8(15)
else
x = UInt8(pieceon(b, s).val)
end
if nibble == 0
nibble = x
else
write(io, UInt8((nibble << 4) | x))
nibble = 0
end
end
if nibble ≠ 0
write(io, UInt8(nibble << 4))
end
# Pack side to move and castle rights into one byte:
write(io, UInt8((b.side - 1) | (b.castlerights << 1)))
# Write castle files (for Chess960):
write(io, UInt8(b.castlefiles[1] | (b.castlefiles[2] << 4)))
take!(io)
end
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: FEN compression
So you train on eval not game result ? I've implemented both models in Demolito, for tuning the HCE (hand crafted eval):AndrewGrant wrote: ↑Wed Mar 17, 2021 2:39 am Not nearly as good as yours, although trivial to decompress and matches my internal use during training. Load times are pretty fast, to the point where speeding it up is a non-factor for me, but I imagine your scheme would be faster, trading off disk reads for decompression.
Code: Select all
Occupancy : 8-bytes Evaluation : 2-bytes Turn : 1-bytes White King Sq : 1-bytes Black King Sq : 1-bytes Piece Count : 1-bytes Packed Pieces : 1-bytes per two pieces (16 max, 12 average) = Average of 26-bytes, max of 30-bytes.
- eval + tempo = alpha + beta * deepEval + error
- result = 1 / (1 + exp(-(eval + tempo))) + error
Neither gave me anything, because Demolito's HCE is already tuned to death, using reinforced learning with Joona Kiiski's SPSA script https://github.com/zamar/spsa. But experimenting clearly showed that the logistic regression on game result was better.
Are you using this for tuning an HCE (Ethereal) or NN eval (Halogen) ?
Btw, I think you can save 24-bits, without complicating code or using PEXT/PDEP:
Code: Select all
Occupancy : 8-bytes
Evaluation : 2-bytes
Turn : 1-bytes
Packed Pieces : 1-bytes per two pieces (16 max, 12 average)
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 35
- Joined: Sun May 02, 2021 10:23 pm
- Full name: John Tromp
Re: FEN compression
I'm working on a FEN compressor that maps any FEN describing a reachable position into a non-negative number under N=8726713169886222032347729969256422370854716254 (~8.7E45), which amounts to ~19.1 bytes.
Position information includes side to move, en-passant status, castling rights, but no 50-move rule or evaluation information.
Position information includes side to move, en-passant status, castling rights, but no 50-move rule or evaluation information.
-
- Posts: 1789
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: FEN compression
This would be of interest. Keep us posted if you can.tromp wrote: ↑Tue Jun 22, 2021 1:30 pm I'm working on a FEN compressor that maps any FEN describing a reachable position into a non-negative number under N=8726713169886222032347729969256422370854716254 (~8.7E45), which amounts to ~19.1 bytes.
Position information includes side to move, en-passant status, castling rights, but no 50-move rule or evaluation information.
#WeAreAllDraude #JusticeForDraude #RememberDraude #LeptirBigUltra
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )
"Those who can't do, clone instead" - Eduard ( A real life friend, not this forum's Eduard )