Inverse-Chess

Summary : Game of inverse chess, is the game where the game is played backward in time. It is a method of playing a game with a pre-identified start layout, a pre-identified end layout and arbitered moves chosen amongst a set of possible moves, played between two opponents on a chessboard.

Methadology : The game of chess is an old one, which has held historical significance. In the regular case (the game which we refer to as forward chess), the game is played forward in time. The opponents start with the pieces , lined up on a board , with the objective of the game being to destroy the opponent's pieces. The player that succeeds is termed the winner.

In the present ichess game, the game is played backward in time. In this case, the opponents start with all or a subset of the pieces from a pre-identified start position. This start position in inverse chess is usually an end or middle game from an already played game of forward chess, consequently rendering a small number of pieces on the board when the game begins. The game is played backward in time, with the objective of the game being constructive. The end position in inverse chess is usually the whole board at the start of a forward chess game. Alternatively, the end position in inverse chess could also be a pre-identified end position, which the players decide on by mutual agreement. The players play-chess backwards, attempting to get the pieces of their side to the starting position. For example, if the players agree to reconstruct the whole board at the end of the game, they would play with the objective of bringing back the King, Queen, Two Bishops, Two Knights and Two Rooks in the first row, with eight Pawns being placed in the second row. The pieces need not follow the same paths, in inverse chess, while proceeding towards a wining position. The process of reconstructing the pre-identified start position is achieved by either of, executing the action opposite that of destroying a piece, in forward chess (this action is referred to as spawning) or a reverse chess move. A piece can be spawned (spawned piece) if another piece vacates a position (vacating piece). In the case of forward chess, the vacating piece would have taken the place of the spawned piece but, this is reversed in inverse chess. The skill of the players is tested by how they move their pieces to the start position, how intelligently they spawn pieces possibly close to their final destinations.

Proposed Method: Previously the ichess was based on alpha – beta pruning and pvs algorithm this was not very much efficient as the time taken to make a move was more as the total number of moves left decreased because of more levels were prunned in the tree, so to improve the efficiency of the algorithm we decided to move to database approach where on the bases of pre – generated log files of previous games we were making a move i.e when opponent makes a move then the corresponding board state was matched with all the states in the log files and which ever state was matched first our player made that move despite of knowing that whether the move will result into winning or loosing the game because it might be possible that the resulting state can match with many log files, so we should make a best possible move that results in winning the game. After using this approach the efficiency improved significantly because it might be possible that the resulting state might not be there in log files then we again go to previous two algorithms but according to our observation there was improvement in the efficiency.

As mentioned there might be many matches of resulting state with many log files, so our task is to select the best possible move from log files. 1. So, we seperated the log files into three different folders where our player win, lose and third where there is no result. 2. So, when opponent makes a move then the resulting state is matched with the log files of first folder and if in that also there are multilple matches then we will select that move in which mere moves are left for player as the player will win early if it selects that move. 3. Secondly it might be possible that there is no match in first folder then we search in second folder in that also there light be multiple matches, so we select that move in which players less moves are left because the player might not loose soon. 4. It might be possible that there is no match in second folder then we move to third one and if found match then selects move from that folder. Now this approach will select the best move from the log files and it will be efficient in making move if compared to previous approach. 5. Now it might be possible that there is no match found then our player should try to learn from opponent by repeating the same procedure as mentioned above by matching the moves of wight player our task is to learn from the moves of opponent and select that move which would have resulted in win for him in less number of moves. Even if there is no move found after this then we will move to previous alpha – beta prunning algorithm and previously as we were just prunning the tree upto certain levels now at one level we should prunne the tree and again repeat the database approach again if no move is found then prune further. This approach is much more efficient then the previous approach and will result in the best possible move.

Now as we moved to the database approach now our task is to make this more efficient this might be possible only if the time to search the resulting state in the database can be made more efficient.

So, we propose two approaches to make the searching more efficient. Previously when we were searching then the log files were not structured properly and the size was too huge, so the amount of time in matching the resulting state was more, so we should structure the log files in proper format as it will be quite efficient searching and the size of the log files will be reduced and will be result into efficient searching. Previously when we searched for a resulting state then we matched each and every state from A1 to F8, so there were total 64 matches apart from this the piece which made move from which position to which position was also matched and then the number of moves were matched, so it resulted in more time in searching for the state this time can be reduced upto some extent and make our approach more efficient by properly structuring the log files. So. We propose two approaches for that.

The two approaches are as follows:

1. As previously we were matching all the locations in the log files from A1 to F8 and moves left, piece moved from and to location, so the searching time was more to reduce this we can represent all the 32 pieces in binary format this information can be stored in 1 byte as 32 pieces can be represented through 8 bits i.e 1 byte and all the other informations likes moves left and to location of piece moved can be stored through other bytes, so every time we need to match it with 1 byte for all the pieces it takes less time for matching and is much more efficient then the previous approach but here the disadvantage is that some of the pieces might not be present on the board , so it is useless to store all the location of the pieces this will result in most of the bits to 0 because those pieces might not be there on board, so it is useless to store all these pieces information. To reduce the efficienct further we can further reduce the matching time through second approach.
2. As in previous approach we were matching all the pieces location represented through 1 byte, here we will store all the board states through binary number i.e all the 64 locations can be represented using 8 bits. So here we need to store those locations only that has piece on it and those are empty doesn't need to be stored, so it will further reduce the size of log files as the number of bytes with every move will be dynamic if compared to previous approach because in previous approach we were representing all pieces with binary number and here we are representing all board states with binary number, so here we can store the location of object with binary number hence it will result in further reduction in time.

And our further task is to do create patterns then this approach of representing locations with binary number will be very helpful to create the patterns. It is the initial state of data preparation rest analysis can be done on this data.