Board representation idea

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.
Post Reply
maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Board representation idea

Post by maksimKorzh » Thu Nov 01, 2018 5: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.

Ras
Posts: 1393
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Board representation idea

Post by Ras » Thu Nov 01, 2018 6:30 pm

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

Dann Corbit
Posts: 11135
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Board representation idea

Post by Dann Corbit » Thu Nov 01, 2018 6:30 pm

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.
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.

maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Board representation idea

Post by maksimKorzh » Thu Nov 01, 2018 6:48 pm

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?

Robert Pope
Posts: 519
Joined: Sat Mar 25, 2006 7:27 pm

Re: Board representation idea

Post by Robert Pope » Thu Nov 01, 2018 7:21 pm

maksimKorzh wrote:
Thu Nov 01, 2018 5: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.
If you replace the numbers with a series of zeros, isn't this literally just a mailbox representation, which has been used forever?

maksimKorzh
Posts: 81
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Board representation idea

Post by maksimKorzh » Thu Nov 01, 2018 7: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 :(

Sven
Posts: 3851
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Board representation idea

Post by Sven » Thu Nov 01, 2018 9:16 pm

maksimKorzh wrote:
Thu Nov 01, 2018 7: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 :(
Looping over parts of an FEN string in the way you described above only works in horizontal direction (same rank).


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)

Robert Pope
Posts: 519
Joined: Sat Mar 25, 2006 7:27 pm

Re: Board representation idea

Post by Robert Pope » Fri Nov 02, 2018 1:28 pm

maksimKorzh wrote:
Thu Nov 01, 2018 7: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 :(
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.

Post Reply