Anastomochess

De Lillois Fractale Wiki
Aller à la navigation Aller à la recherche

Introduction

This article describes a project related to the chess game.

The purpose of the project is not a chess playing engine; it is a chess database and a front-end program to explore it (with a dedicated web site).

Other articles on chess from the same author are available in this wiki.

Building the database

The building of the database should include the loading of MANY games (~106 and more if possible).

The loaded games should include (besides the sequence of moves), the result and the name and elo rating of the players.

Each game will be processed so that the 20 (or more...) first positions generated by the moves are stored in the database.

Anastomosis

In a tree (in computing science and in life science), the anastomosis is the reconnection of two streams that previously branched out.

In chess, which is tree game, anastomosis is highly present, but most of the time poorly handled.

Anastomosis brings complexity, because it eliminates several convenient properties of tree management. But it also provides wide benefits.

Indexing positions

In order to manage a large number of positions, a good indexing scheme is required. An original and performing scheme is documented here, and provides a way to index any position on a compact bit set.

The number of bits fully defining a position is between 78 and 113, depending on the complexity of the position, but this is optimal in terms of compacity (would be hard to have it more compact).

The position indexing scheme is used to build huge HashSets of positions.

Database content

For each position in the database, the following fields at least should be present:

  • the number of paths leading to that position (anastomosis factor)
  • the various last moves leading to that position (and links to the corresponding previous positions)
  • the various next moves played from that position, and for each of them
    • the number of time they were played
    • the average Elo rating of the players who chose them
    • the results of the games (white/draw/black)
  • an uncertainty measure for this position, using an entropic measure
  • a global white/black balance measure
  • a global dynamic measure (measure of likelihood of a draw game)
  • (the indexing key)

The size of the information stored by position should be around 200 bytes (including linked objects)

An efficient use of storage would then allow to manage up to 5x106 anastomo-positions per terabyte.

Specific data structures

The specific data structures involved in the project include

  • back moves (5 bytes + 1 key per object)
  • forward moves (20 bytes + 1 key per object)
  • anastomo-positions (~80 bytes + 1 key per object)

[ a key is at most 15 bytes ]

User interface

The user interface should

  • display all the information present in the database (listed above)
  • allow backward links to previous positions for all last moves
  • allow forward links to next positions for all next moves

Obviously the user interface should be fast, user friendly, visually attractive.

The relationship between the data server and the front-end is probably complex and should inlcude an aefficient usage of caching tools.

It is beyond the perimeter of this article.

Development

Suggested technology

Java / JavaFX / Collections.

The Matscape java libraries would provide fast development path.

Estimated workload

Between 1 and 3 year men.