[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] A lot of questions
From: |
Łukasz Lew |
Subject: |
Re: [gnugo-devel] A lot of questions |
Date: |
Tue, 16 Aug 2005 12:14:22 +0200 |
On 8/15/05, Gunnar Farnebäck <address@hidden> wrote:
> Lukasz wrote:
> > 1. Why trymove(PASS) is not a legal operation?
>
> Historical reasons. This was changed in development version 3.7.1.
That is convenient.
Thanks for that.
>
> > 4. What do You think about incremental bookkeeping information about
> > legality of moves?
> > I.e. to maintain an array of bools with false meaning that move is
> > illegal.
> > This would avoid a repetitive checking of legality of illegal moves.
>
> Only interesting if it measurably speeds up GNU Go itself. I can see
> how it could be useful for certain uses of the board code, but we
> don't want the added complexity if it doesn't give sufficient benefits.
Complexity:
- additional bool array
- clearing the array in appropriate places (where? new position?)
- 8 places in the code updating the array illegal -> possibly legal
(informal proof that no more is needed)
- checking and updating the array in is_legal and trymove
Improvement in performance for my needs (MC playouts) is very large, but
for the code of Gnu go it would be much smaller.
What degree of the speed improvement would be needed?
Are there any tools in the package measuring performance?
>
> > 5. Why there is separate play_move and trymove, is only for historical
> > reasons?
> > Why wouldn't it be good to replace it by single function and
> > enhance store_board with stack handling?
>
> There are certainly historical reasons but the uses and speed/memory
> tradeoffs are fairly different. If a unified variant would work well I
> see no reason not to use it but for the time being I'm sceptical about
> the feasibility of unification.
>
I'm sceptical too, but. :)
Both functions use do_play_move:
trymove:
ASSERTS
shadow[pos]=1
legality check with definitely not allowing suicide and an
additional showboard and
dump_stack in the case of stack overflow
trymove_counter++
stack[stackp] = pos;
move_color[stackp] = color;
BEGIN_CHANGE_RECORD();
PUSH_VALUE(board_ko_pos);
memcpy(&board_hash_stack[stackp], &board_hash, sizeof(board_hash));
if (board_ko_pos != NO_MOVE) hashdata_invert_ko(&board_hash, board_ko_pos);
board_ko_pos = NO_MOVE;
stackp++;
if (pos != PASS_MOVE) {
PUSH_VALUE(black_captured);
PUSH_VALUE(white_captured);
-> do_play_move(pos, color);
}
if(sgf_dumptree) ...
if (count_variations) count_variations++;
stats.nodes++;
play_move
ASSERTS (more than try move)
move_history maintaining
maybe hash checking
if (board_ko_pos != NO_MOVE) hashdata_invert_ko(&board_hash, board_ko_pos);
board_ko_pos = NO_MOVE;
more assertions
do_play_move OR do_commit_suicide
maybe hash checking
new_position()
move_num ++
The main differences are:
- build in legality check in trymove with illegal suicide
- maintaining stack in trymove vs move_history + new_position in play_move
- some separate stats: count_variations, stats.nodes vs move_num
- some different debug information
I know that my view is very shallow, but at this point I do not see
severe problems
except perhaps the size of the modification.
I propose to have a separate is_legal and to maintaining the stack.
For the test phase of the merge implementation there could be an
additional parameter
of the call deciding which statistics update and deciding all the rest details
of the semantic differences.
> > 6. Why superko isn't implemented?
>
> It has been on the TODO list for ages. So far nobody has found it
> important enough to spend time on it.
The superko can be only checked after the move, so I propose
adding an additional function to the boardlib : is_position_repeated.
That would return a bool whether we entered into illegal cycle.
It would be implemented on a hash set and work for both trymove and play_move.
Where the data structure should be defined?
I would like to again ask how could I help to solve the problem with
MAX_STRINGS and MAXSTACK
Is the segfault a known behaviour?
Kind Regards,
Lukasz