Re: [gnugo-devel] A lot of questions

[Łukasz Lew]

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