I used to start writing a new chess engine with parse fen routine. It's absolutely ok in case writing it in C, but recently I've switched to NASM assembly which lead to significant grow of code size, so I came up with an idea which might have look pretty weird at a glance, but I still believe it has a potential, so the idea is to USE FEN STRING AS BOARD REPRESENTATION. I mean really for everything engine ever needs to know about the position is stored inside the fen string. The obvious problem is how to generate moves... That's the point where I've stuck... The first issue - fen is not fixed sized, but I've discovered that say start fen might have a look like this 'rnbqkbnr/00000000/00000000/.....' instead of what we used to see '.../8/8/....', so replacing the sum of empty squares by Os is just fine. So here are my questions:
1. Is it worth keep thinking this direction?
2. Did anybody ever came up with this idea or implementation before?
3. Any ideas on how to calculate offsets for move generation in non-fixed size array?
Thanks in advance.
Board representation idea
Moderators: hgm, Rebel, chrisw
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Board representation idea
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 2498
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Board representation idea
Variable length strings always have that offset problem. No matter how you do it, it will never be just adding a constant. Same reason why XML will always be slow if you use it for large amounts of data. A fixed length string would solve this, but that would basically circle back to an 8x8 concept.
Rasmus Althoff
https://www.ct800.net
https://www.ct800.net
-
- Posts: 12568
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Board representation idea
People do something very much like that, but instead of using a character string, they use an array of 64 bits to indicate where the chessmen are on the board and then a list of the chessmen at those positions (along with castle rights and e.p. status).
Now, you are correct in your assessment that the information carried in a FEN or EPD string is identical to the above formation.
There are two main differences, however.
First, the bitboard version is much more compact. For a single board, this means nothing, but for a long list of boards it can be important.
However, the important difference is the one that you have found.
It is easy to generate moves from bitboards. It is difficult to generate moves from a character string board.
But your approach will work.
I guess, in the end, you are going to end up either with bitboards or one of the array techniques, simply because they are effective.
But you will learn a lot in doing it your way.
Now, you are correct in your assessment that the information carried in a FEN or EPD string is identical to the above formation.
There are two main differences, however.
First, the bitboard version is much more compact. For a single board, this means nothing, but for a long list of boards it can be important.
However, the important difference is the one that you have found.
It is easy to generate moves from bitboards. It is difficult to generate moves from a character string board.
But your approach will work.
I guess, in the end, you are going to end up either with bitboards or one of the array techniques, simply because they are effective.
But you will learn a lot in doing it your way.
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: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Board representation idea
I'm familiar with bitboards (wrote 'plain' bitboard movegen once... ), I've just come with an idea. Being a big fan of 0x88 system (I did 3 engines using it, they are raw, but still) I wondered - 0x88 is just about indexing the board rather than using the amount of extra 8x8 squares on the right, so... what if just define some array like this:
arr { 0, 1, 2, 3, 4, 5, 6, 7
16, 17, 18 .....................
......................................
112..........................119}
and while looping over FEN string and keeping track of 8x8 piece coordinate and the corresponding square respectively just to convert that index into 0x88 index, than perform move generation and after translate 0x88 square back to 8x8 square? How about that?
arr { 0, 1, 2, 3, 4, 5, 6, 7
16, 17, 18 .....................
......................................
112..........................119}
and while looping over FEN string and keeping track of 8x8 piece coordinate and the corresponding square respectively just to convert that index into 0x88 index, than perform move generation and after translate 0x88 square back to 8x8 square? How about that?
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: Board representation idea
If you replace the numbers with a series of zeros, isn't this literally just a mailbox representation, which has been used forever?maksimKorzh wrote: ↑Thu Nov 01, 2018 6:12 pm I used to start writing a new chess engine with parse fen routine. It's absolutely ok in case writing it in C, but recently I've switched to NASM assembly which lead to significant grow of code size, so I came up with an idea which might have look pretty weird at a glance, but I still believe it has a potential, so the idea is to USE FEN STRING AS BOARD REPRESENTATION. I mean really for everything engine ever needs to know about the position is stored inside the fen string. The obvious problem is how to generate moves... That's the point where I've stuck... The first issue - fen is not fixed sized, but I've discovered that say start fen might have a look like this 'rnbqkbnr/00000000/00000000/.....' instead of what we used to see '.../8/8/....', so replacing the sum of empty squares by Os is just fine. So here are my questions:
1. Is it worth keep thinking this direction?
2. Did anybody ever came up with this idea or implementation before?
3. Any ideas on how to calculate offsets for move generation in non-fixed size array?
Thanks in advance.
-
- Posts: 771
- Joined: Sat Sep 08, 2018 5:37 pm
- Location: Ukraine
- Full name: Maksim Korzh
Re: Board representation idea
Not really for mailbox is used to prevent piece going offboard. '/' this char on the right edge of the board will prevent only sliding pieces moves, but knights would jump over that to another rank, so I believe it's not to be claimed as mailbox. Unless you meant 8x8 representation, well, probably, but that is too slow as we all know(unless using bitboards of course). The problem is not even in generating move offsets itself but to actually make move, I'll explain this in details:
say we are looping over fen, keeping track of 8x8 coordinates: if found a piece - increment file, if found a digit then file += digit(which is number of series of empty squares), if found '/' do rank-- (FEN starts with 8th rank and ends on the 1st one), this means that if we've found a pawn on file == 5 and rank == 2 then we can calculate the square using expression (7 - rank) * 8 + file, here we get the square number where pawn is sitting and can use it as an array index to look up for corresponding pre-calculated 0x88 square, then we can add an 0x88 offset 16(up/down move), and find the destnation square, then convert 0x88 dest square back to 8x8 representation. But here is another issue arising - how to actually make move to evaluate it one day? And even more interesting question is how to take it back... Changing initial FEN looks like a horrible idea, so I don't know what to do for now
say we are looping over fen, keeping track of 8x8 coordinates: if found a piece - increment file, if found a digit then file += digit(which is number of series of empty squares), if found '/' do rank-- (FEN starts with 8th rank and ends on the 1st one), this means that if we've found a pawn on file == 5 and rank == 2 then we can calculate the square using expression (7 - rank) * 8 + file, here we get the square number where pawn is sitting and can use it as an array index to look up for corresponding pre-calculated 0x88 square, then we can add an 0x88 offset 16(up/down move), and find the destnation square, then convert 0x88 dest square back to 8x8 representation. But here is another issue arising - how to actually make move to evaluate it one day? And even more interesting question is how to take it back... Changing initial FEN looks like a horrible idea, so I don't know what to do for now
Didactic chess engines:
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
https://www.chessprogramming.org/Maksim_Korzh
Chess programming YouTube channel:
https://www.youtube.com/channel/UCB9-pr ... KKqDgXhsMQ
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Board representation idea
Looping over parts of an FEN string in the way you described above only works in horizontal direction (same rank).maksimKorzh wrote: ↑Thu Nov 01, 2018 8:44 pm say we are looping over fen, keeping track of 8x8 coordinates: if found a piece - increment file, if found a digit then file += digit(which is number of series of empty squares), if found '/' do rank-- (FEN starts with 8th rank and ends on the 1st one), this means that if we've found a pawn on file == 5 and rank == 2 then we can calculate the square using expression (7 - rank) * 8 + file, here we get the square number where pawn is sitting and can use it as an array index to look up for corresponding pre-calculated 0x88 square, then we can add an 0x88 offset 16(up/down move), and find the destnation square, then convert 0x88 dest square back to 8x8 representation. But here is another issue arising - how to actually make move to evaluate it one day? And even more interesting question is how to take it back... Changing initial FEN looks like a horrible idea, so I don't know what to do for now
[d]2kr4/pp1r1p1p/2pBn1p1/4P3/P1P5/P5P1/7P/3R1RK1 w - - 0 1
How do you process that position to find all vertical moves of white rooks or all bishop moves? For kings, knights and pawns you get away with pre-calculated moves but for sliding pieces there is no "pre-calculation".
I think the idea is interesting but it will end up in something inefficient.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: Board representation idea
It's still a mailbox, though. You just aren't getting the benefits you are associating with mailboxes. Mailbox methods don't prescribe any particular shape.maksimKorzh wrote: ↑Thu Nov 01, 2018 8:44 pm Not really for mailbox is used to prevent piece going offboard. '/' this char on the right edge of the board will prevent only sliding pieces moves, but knights would jump over that to another rank, so I believe it's not to be claimed as mailbox. Unless you meant 8x8 representation, well, probably, but that is too slow as we all know(unless using bitboards of course). The problem is not even in generating move offsets itself but to actually make move, I'll explain this in details:
say we are looping over fen, keeping track of 8x8 coordinates: if found a piece - increment file, if found a digit then file += digit(which is number of series of empty squares), if found '/' do rank-- (FEN starts with 8th rank and ends on the 1st one), this means that if we've found a pawn on file == 5 and rank == 2 then we can calculate the square using expression (7 - rank) * 8 + file, here we get the square number where pawn is sitting and can use it as an array index to look up for corresponding pre-calculated 0x88 square, then we can add an 0x88 offset 16(up/down move), and find the destnation square, then convert 0x88 dest square back to 8x8 representation. But here is another issue arising - how to actually make move to evaluate it one day? And even more interesting question is how to take it back... Changing initial FEN looks like a horrible idea, so I don't know what to do for now