It's unusual to have very base data model change this late in a project; any yet, here we are. Currently, I was implementing generators of all legal paths every piece can make in a ply. Since this change will disrupt development for quite some time, let me try to explain it.
The issue I'm talking about is that currently piece and tag enumerations are separated; which would be fine in almost all designs, since most of the time one data entity is indeed independent from any other, e.g. one person's year of birth is very separated from their phone number. This is not the case here, Bishop can never get "can rush" tag, nor Knight can ever castle.
Edit: Tags and pieces have very few, and very intimate relationships; usually tag can be attached to a few pieces (e.g. rush and en passant tags for privates). Technically, tag is a link between a piece and a field at which that piece is located. Once that link is broken (e.g. a Pawn has been activated and moved away), there is no more tag present (e.g. activated Pawn has lost its promotion tag) even if both a piece and its originating field are still present in a game. Most of the time the best data model is the one designed after real-life; this is why original design featured tags separated from pieces.
Another issue with separated piece and tag enumerations is that, well, they are separated. So, every function working with pieces (and in a chess game that means all of them) has to have two separate parameters. Yes, you can combine then in a neat struct, together with some other bits (e.g. a position) to bring number of parameters down; but, they both are now present in every struct you have to pass around.
Plus, they still take too much space, in fact, twice as much as needed; and that's after a change has been made quite some time ago, so that only 1 byte (char) is stored per enumeration instead of default 4 (enums are just fancy ints). You might think that we have moved past storage issues since like forever, but that is true only for local apps. For libraries, one has to consider possibility that it might serve many users at once, also it might need to do it on a restricted hardware (e.g. micro-controllers).
There is another issue with enumeration storage, and that's space it takes in a chessboard struct; again, currently it's double the amount it actually needs. Parsing user notation and applying it to a current chessboard is not an easy task; if undo is supported then one has to apply all moves performed until that point. To speed things up (and avoid doing the same job twice) position after performed move can be stored, and later retrieved. Only problem is, the largest variant has 676 fields, 190 pieces and 14 different interactions (losing tags are not counted, as they're result of interactions), which means it can last much longer than classical chess game. The longest recorded classical chess match in tournament was 269 moves, but legal match can stretch up to 5898.5 moves with 50-moves draw rule, or up to 8848.5 moves if 75-move draw rule is used instead.
For the record, move to me always means all actions performed by one player in one turn; this is different from FIDEs definition used above which define a move as white player action followed by black player action; for FIDE definition I use term cycle. Reason why I refer to move as such is because each player moves their pieces independently to each other (current chessboard position notwithstanding), there is a meaningful choice to be made; in fact, making a choice is the whole point of a game.
So, how long can chess game go in the latest and greatest variant of them all, the One? Honest answer, I don't know. I tried to guess-timate the thing, but it's probably wildly inaccurate. My guess is that tournament games won't last much longer than 18.000 moves, and technically legal games could probably go for 10.000.000+ moves; both with 50-cycle draw rule. This post is already too long, if you're interested to hear my reasoning, let me know in comments below.
As you can see, if undo is supported by storing chessboards, just having variant enumeration as an int in a chessboard struct can easily eat up to 40+ MB of space, just for that one enum. Undo chessboards could currently use 13+ GB of RAM in total; with changes proposed here implemented, that could drop down to 6.5+ GB. This is why I'll merge piece and tag enums, and also change variant enum storage to byte. Such a change will affect everything in the project; for the time, there will be development without (much) progress.
No comments:
Post a Comment