Handling of game history as tree-like structure

[sphaso]

We've decided to transform our game history datastructure from a list to a tree. What this entails is:

• make_move could be used inside a branch. The move you're pushing could not be the latest of the game but rather the lastest of the variation you're in
• is_legal could be used inside a branch. It should check the legality of a move against the current board position, not the latest from the trunk (also consider Ko check)
• make_variation could be used inside a branch. There should be a way to know at what move AND depth we should branch out (put a list inside another list)

This is complicated by the fact that every helper method (e.g. is_neighbour) is considering self.goban. Maybe the goban representation should become a parameter and its datastructures (groups, captures etc.) should be calculated from scratch against the current position as well (in editing mode I can jump from a branch to another, we cannot assume linear time).

[tylerjw]

I think if we handled the game tree within game and left board alone we should be able to accomplish this without modifying all of those methods. The methods inside Board deal only with the board at hand while the game handles history and the game tree.

[sphaso]

It sounds very promising. Let's see if I understand. Into Game, "board_history" stores a history of the full boards after each move, while "move_history" stores a history of the moves (pos) made? Do we need both? I think we might want to calculate the board based on the move we're looking at and thus only updating move_history. If not, we need to make both structures tree-like.

[tylerjw]

I don't really know the point of the move_history list as it doesn't seem to be used. Board history is used in the undo method. I'm hoping I can get the SGF format library working and build the game record history around it. Allowing games to easily be saved and recreated.

[tylerjw]

As of right now I don't know how we would handle the issue of undo and ko without board_history. board_history seems to be a waste of system memory in that it saves the object state of every "board" in the game. On the other hand, system memory is in abundance and complicated algorithms cut down on the responsiveness of the game. Something I don't think we should do. However I don't believe the solution of board_history is elegant.

On ko testing: To prevent a ko (repetition of a board position) we really only need to save a few board if we are only preventing simple ko (immediate repetition) and not banning all repetition.

On undoing moves: The main problem in undoing moves without a board history lies in the capture of stones. If somehow the capture of stones was annotated in the tree history (it probably is, need to read more on SGF) then this is a mute point.

On move_history, I think it is completely useless and should be removed. Note my latest commit.

[sphaso]

Ko testing: we can recreate two boards (the old one and the prospect one) whenever a move has the same position of the one two steps behind (this can be in different branches as well), we recreate the boards and compare them for equality, if they are the same we're in front of a Ko and refuse the move

Undoing moves: at each undo we remake the moves, this time we can avoid testing for legality (but we need to update groups in case of captures)

However, I agree we should probably trade memory for performance and store a board_history. From where I stand it seems that game_tree is the new and better move_history. I wonder if we really need to transform board_history into a tree as well, maybe a dictionary will do? key could be an hash of the moves so far (complete with variations, e.g. B3A4VA3C4) and the value the actual board, could it be easier\faster to traverse? not sure.

[tylerjw]

I think you are onto something with board_history being hash-able. Since we aren't using it to "undo" and we are just testing for a previous position we should make Board a hashable object (python supports this) and just store the hash. That would solve both the memory and performance. Creating and comparing hashes is fast, and storing them takes almost no space. Awesome idea!

On Sun, Jul 14, 2013 at 6:38 PM, sphaso notifications@github.com wrote:

Ko testing: we can recreate two boards (the old one and the prospect one) whenever a move has the same position of the one two steps behind (this can be in different branches as well), we recreate the boards and compare them for equality, if they are the same we're in front of a Ko and refuse the move

Undoing moves: at each undo we remake the moves, this time we can avoid testing for legality (but we need to update groups in case of captures)

However, I agree we should probably trade memory for performance and store a board_history. From where I stand it seems that game_tree is the new and better move_history. I wonder if we really need to transform board_history into a tree as well, maybe a dictionary will do? key could be an hash of the moves so far (complete with variations, e.g. B3A4VA3C4) and the value the actual board, could it be easier\faster to traverse? not sure.

— Reply to this email directly or view it on GitHubhttps://github.com/tylerjw/badukpy/issues/6#issuecomment-20936902 .

V/R Tyler Weaver Cell - (303) 903-5681 email - tylerjw@gmail.com

"Things may come to those who wait, but only the things left by those who hustle."

• Abraham Lincoln

[sphaso]

sure, we can make Board hashable and we can still use board_history to undo if the key is a reference to the move history (not move_history). I would guess it's faster than remaking all the moves and we don't need a special "make move without checking legality" method, we just need a way to link the moves to a position.

[tylerjw]

I'm not sure I understand what you are saying. The primary concern I see with undo actions is when you are undoing a move that caused a capture. It's then not as simple as taking the last piece off, you have to know how to undo the capturing of the other side's stones.

[sphaso]

Certainly, my idea was for board_history to be a dictionary where the key would be a representation of the move in the tree and value the hashed board. In this case when you undo you look for the previous move in the dictionary and retrieve the board. The main challenge of course is how to reference that exact move across the program. What do you think? were you considering another solution?

[tylerjw]

Checkout the latest commit, I think it is a move in the right direction. I didn't create hashes of game_history. My understanding of "game_history" is that it is only necessary for testing for ko and for undoing.

For undoing if we can find a way to notate that stones were captured on a move we wouldn't need game_history for that.

For ko testing it'd be real simple. We just need to hash the board on each move and save the hashes to a list. If we are just preventing simple ko (moves that return the board to the immediate previous position) we only need to store the last couple hashes. If we are preventing ko in all cases (board ever returns to a previous state, i believe this is the way it works now) we just add the board hash to a list every time a move is made and then test to make sure that hash doesn't exist in list.

I don't think we need to link moves to hashes, but maybe I don't understand.

[sphaso]

Undoing: I like the idea of adding a captured_stone field to the move class, if this allows us to trash another object we're currently using (game_history?) or increase our speed with minimum memory loss

Ko: these are complex matters where confusion and edge cases easily spring up. My worry is that the user woulnd't traverse the game tree linearly. I look at a variation, then click away 50 moves ahead, edit there, go back, edit there etc. Go GUIs allow this by giving a visual representation of the game tree. In this case I'm not sure if we can simply store a couple of boards, because we wouldn't know when did that position arise. Yet, even if we force the user to traverse each variation linearly, we cannot just store boards in a list because the same position can arise in different variations and be perfectly legal. Plus, we have the case of multiple Kos on the board which might repeat the position multiple times (if my knowledge of this case is correct, which I wouldn't be so sure about).

[tylerjw]

I'm sorry I didn't understand at first but I think I'm starting to grasp the issue. Maybe we could store a hash of the board at each of the "Node" objects, then the ko test could be done internal to the make_move inside the gametree sgf objects. Does that sound good?

I take that at some point we are going to need a gui representation of the game tree(s) that allows the player to skip through them in a non linear way? That way you could try different moves several deep from a given position.

[sphaso]

Nothing to be sorry about, we're here to share ideas and find solutions together. I think your suggestion is sound and it will allow us to only have a game_tree object with a board in each node, since we're at it we might want (or rather, need?) to add the captures as well (or does the Board we're putting there takes care of that already?). Great stuff! The only issue might arise for move substitutions in the middle of a variation, for that we'd need to recalculate everything down the line. I don't recall any GUI that allows this (I think some chess GUIs do, but they don't have half the problems we're addressing) nor I think we should allow this to happen. A new move in the middle of a variation is child branch. Yes, we'll need a gui representation of the game tree, it looks difficult, but I'm sure we'll manage :)