search

Infinite-Chess / infinitechess.org

Infinite Chess Web Server
https://www.infinitechess.org
GNU Affero General Public License v3.0
172 stars 40 forks source link

"Truly infinite move distance" #25

Open optim-ally opened 1 month ago

optim-ally commented 1 month ago

This is listed as the first of the "crucial features" still to be implemented.

Moves are currently stored as strings (e.g. "62,22>120,82=N"). These can theoretically represent moves of arbitrary distance. Once loaded into the browser, however, they get converted to Number types for manipulation: https://github.com/Infinite-Chess/infinitechess.org/blob/52fb1674a87dd2eb0aaf9dc9e6814ce91dba7258/game/formatconverter1.js#L807-L814

This bounds useable move distance to Number.MAX_SAFE_INTEGER which is 253 - 1. Coordinates larger than this may not be compared correctly, for example when checking if a destination square is on the same file.

There are already some BigInt helpers in the codebase - I don't know how close these are to being used. Using BigInt for coordinate calculations and comparisons would allow arbitrarily large and safe move distances but it may not be worth it. There could be a considerable impact on speed just to be able to say that "infinite move distance" is supported. Perhaps users can choose a "truly infinite" setting to enable BigInt calculations? Some benchmarking is needed before switching over.

If we decide that BigInt is worth the slowdown then the bottleneck may once again become the game storage. The string representation is only "infinite" if the database supports arbitrary string lengths.

this-is-not-available commented 1 month ago

There is a discussion about this here https://discord.com/channels/1114425729569017918/1260305383302631484 (I think)

Naviary2 commented 1 month ago

Discussion here Basically, a bit ago I started on a library supporting fast arbitrary-precision decimal and integer arithmetic, using BigInts paired with fixed-point arithmetic. A dedicated portion of the BigInts least-significant bits are dedicated towards the decimal portion of the number.

But this library isn't required to store the coordinates of the pieces, those are integers and BigInts can be used. But if we want to make this "truly infinite", we also need arbitrary decimal precision to store the player's position, and zoom level.

I don't think we'll have to worry about BigInts, yes they are slower than doubles, but they are the fastest thing we have when it comes to arbitrary integer arithmetic. The mesh of the pieces only needs to be calculated once, and in games with 32 pieces, that's pretty much instantaneous even if you are at extreme distances.

But, to not hurt already-high-performance, I suggest games are stored in their current format, until someone makes a move that is beyond Number.MAX_SAFE_INTEGER. At that point the gamefile gets converted into BigInts, and you get a slight performance decrease, likely only noticable in games with over 10,000 pieces.

Probably we should have the player position and zoom level always stored as a BigDecimal though (the name of the library being written), for simplicity's sake, even if they haven't moved past Number.MAX_SAFE_INTEGER. 2 arbitrarily large numbers is nothing to calculate once per frame.

That BigInt helper in the codebase is outdated, it will be replaced by this custom library.

Speed is also a huge priority of mine so I want to make sure this is optimized as possible as very much playable before we switch.