search

maxpumperla / deep_learning_and_the_game_of_go

Code and other material for the book "Deep Learning and the Game of Go"
https://www.manning.com/books/deep-learning-and-the-game-of-go
953 stars 387 forks source link

Why does_move_violate_ko looks into an unlimited depth? #35

Closed fredthedead closed 5 years ago

fredthedead commented 5 years ago

In the following code section it seems like the ko detection/search is traversing all past moves: https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/61328b8f0c0e54870bd95d6ace7f9641acf1247b/code/dlgo/goboard_slow.py#L216

Isn't ko limited only to the previous move? (so the while should be replaced by if?)

roryheim commented 5 years ago

In the following code section it seems like the ko detection/search is traversing all past moves:

https://github.com/maxpumperla/deep_learning_and_the_game_of_go/blob/61328b8f0c0e54870bd95d6ace7f9641acf1247b/code/dlgo/goboard_slow.py#L216

Isn't ko limited only to the previous move? (so the while should be replaced by if?)

Hi fredthedead, checkout my PR from about 18 days ago. My fix fixes this issue you observed. I don't note that in my PR, however due to the original comparison bug, if you only use an 'if', there's still a bigger bug in that a ko violation will never be found. I verified via unit tests that my fix only looks back one board and if ko violation occurs it will be detected. Once the author transitioned to the hashing method, his original code then works fine. https://github.com/maxpumperla/deep_learning_and_the_game_of_go/pull/34/commits/5d0fde79b5f1b52d458a5f63463c4737e9e18bb1

fredthedead commented 5 years ago

Hi @roryheim, thanks for replying! I've looked at your PR, with that change - would it still look back at more than a single state? If so, is that needed? I thought ko is only defined on two consecutive states

maxpumperla commented 5 years ago

@fredthedead technically ko can be defined by disallowing the exact same board position twice, i.e. the board you reach with the current move can't be the same as any of the previous board states. In practice, it's usually enough to look at your last move, but I'm sure you can cook up an artificial example in which black and white take a bunch of stones from each other to end up where they were 40 moves ago. that would be ko.

looking up hash values in a hashmap is cheap, so we do that in the Zobrist implementation of GoBoard.