Update readme.txt for new position format
[bonanza.git] / thread.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <assert.h>
5 #include <stdarg.h>
6 #if defined(_WIN32)
7 #  include <process.h>
8 #else
9 #  include <arpa/inet.h>
10 #  include <sys/types.h>
11 #  include <unistd.h>
12 #  include <sched.h>
13 #endif
14 #include "shogi.h"
15
16
17 #if defined(TLP) || defined(DFPN_CLIENT)
18 int CONV
19 lock_init( lock_t *plock )
20 {
21 #  if defined(_MSC_VER)
22   *plock = 0;
23 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
24   *plock = 0;
25 #  else
26   if ( pthread_mutex_init( plock, 0 ) )
27     {
28       str_error = "pthread_mutex_init() failed.";
29       return -1;
30     }
31 #  endif
32   return 1;
33 }
34
35
36 int CONV
37 lock_free( lock_t *plock )
38 {
39 #  if defined(_MSC_VER)
40   *plock = 0;
41 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
42   *plock = 0;
43 #  else
44   if ( pthread_mutex_destroy( plock ) )
45     {
46       str_error = "pthread_mutex_destroy() failed.";
47       return -1;
48     }
49 #  endif
50   return 1;
51 }
52
53
54 void CONV
55 unlock( lock_t *plock )
56 {
57 #  if defined(_MSC_VER)
58   *plock = 0;
59 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
60   *plock = 0;
61 #  else
62   pthread_mutex_unlock( plock );
63 #  endif
64 }
65
66
67 void CONV
68 lock( lock_t *plock )
69 {
70 #  if defined(_MSC_VER)
71   while ( _InterlockedExchange( (void *)plock, 1 ) )
72     {
73       while ( *plock ) { tlp_yield();}
74     }
75 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
76   int itemp;
77
78   for ( ;; )
79     {
80       asm ( "1:   movl     $1,  %1 \n\t"
81             "     xchgl   (%0), %1 \n\t"
82             : "=g" (plock), "=r" (itemp) : "0" (plock) );
83       if ( ! itemp ) { return; }
84       while ( *plock ) { tlp_yield();}
85     }
86 #  else
87   pthread_mutex_lock( plock );
88 #  endif
89 }
90
91
92 void
93 tlp_yield( void )
94 {
95 #if defined(_WIN32)
96   Sleep( 0 );
97 #else
98   sched_yield();
99 #endif
100 }
101 #endif /* TLP || DFPN_CLIENT */
102
103
104 #if defined(DFPN_CLIENT)
105
106 static int CONV proce_line( char *line_buf );
107 #  if defined(_WIN32)
108 static unsigned int __stdcall dfpn_client_receiver( void *arg );
109 #  else
110 static void *dfpn_client_receiver( void *arg );
111 #  endif
112
113 void CONV
114 dfpn_client_start( const tree_t * restrict ptree )
115 {
116   if ( root_turn != min_posi_no_handicap.turn_to_move
117        || HAND_B != min_posi_no_handicap.hand_black
118        || HAND_W != min_posi_no_handicap.hand_white
119        || memcmp( BOARD, min_posi_no_handicap.asquare, nsquare ) )
120     {
121       sckt_shutdown( dfpn_client_sckt );
122       dfpn_client_sckt = SCKT_NULL;
123       return;
124     }
125
126   if ( dfpn_client_sckt        != SCKT_NULL ) { return; }
127   if ( dfpn_client_str_addr[0] == '\0' )      { return; }
128
129   dfpn_client_sckt = sckt_connect( dfpn_client_str_addr, dfpn_client_port );
130   if ( dfpn_client_sckt == SCKT_NULL )
131     {
132       out_warning( "Connection to DFPN server failed." );
133       return;
134     }
135   else {
136     Out( "New connection to DFPN server: %s %d\n",
137          dfpn_client_str_addr, dfpn_client_port );
138   }
139
140 #  if defined(_WIN32)
141   if ( ! _beginthreadex( 0, 0, &dfpn_client_receiver, NULL, 0, 0 ) )
142     {
143       sckt_shutdown( dfpn_client_sckt );
144       dfpn_client_sckt = SCKT_NULL;
145       out_warning( "_beginthreadex() failed." );
146     }
147 #  else
148   {
149     pthread_t pt;
150     if ( pthread_create( &pt, &pthread_attr, &dfpn_client_receiver, NULL ) )
151       {
152         sckt_shutdown( dfpn_client_sckt );
153         dfpn_client_sckt = SCKT_NULL;
154         out_warning( "_beginthreadex() failed." );
155       }
156   }
157 #  endif
158
159   dfpn_client_out( "Client: anonymous\n" );
160 }
161
162
163 #  if defined(_MSC_VER)
164 #    pragma warning(disable:4100)
165 #  elif defined(__ICC)
166 #    pragma warning(disable:869)
167 #  endif
168
169 #  if defined(_MSC_VER)
170 static unsigned int __stdcall dfpn_client_receiver( void *arg )
171 #  else
172 static void *dfpn_client_receiver( void *arg )
173 #endif
174 {
175 #define SIZE_RECV_BUF ( 1024 * 16 )
176 #define SIZE_LINE_BUF 1024
177   char recv_buf[ SIZE_RECV_BUF ];
178   char line_buf[ SIZE_LINE_BUF ];
179   char *str_end, *str_line_end;
180   size_t size;
181   int len_recv_buf;
182   struct timeval tv;
183   fd_set readfds;
184   int iret;
185
186   recv_buf[0] = '\0';
187
188   /* recv loop */
189   for ( ;; ) {
190
191     /* select loop */
192     for ( ;; ) {
193       tv.tv_sec  = SEC_KEEP_ALIVE;
194       tv.tv_usec = 0;
195       FD_ZERO( &readfds );
196 #  if defined(_MSC_VER)
197 #    pragma warning(disable:4127)
198 #  endif
199       FD_SET( dfpn_client_sckt, &readfds );
200 #  if defined(_MSC_VER)
201 #    pragma warning(default:4127)
202 #  endif
203       
204       iret = select( (int)dfpn_client_sckt+1, &readfds, NULL, NULL, &tv );
205       if ( iret == SOCKET_ERROR )
206         {
207           out_warning( "%s", str_error );
208           goto dfpn_client_receiver_shutdown;
209         }
210
211       /* message arrived */
212       if ( iret ) { break; }
213
214       /* timeout and keepalive */
215       lock( &dfpn_client_lock);
216       iret = dfpn_client_out( "ping\n" );
217       unlock( &dfpn_client_lock);
218       if ( iret < 0 ) { return 0; }
219     }
220
221     /* read messages */
222     len_recv_buf = (int)strlen( recv_buf );
223     str_end      = recv_buf + len_recv_buf;
224
225     iret = recv( dfpn_client_sckt, str_end, SIZE_RECV_BUF-1-len_recv_buf, 0 );
226     if ( iret == SOCKET_ERROR )
227       {
228         str_error = str_WSAError( "recv() failed:" );
229         out_warning( "%s", str_error );
230         goto dfpn_client_receiver_shutdown;
231       }
232     if ( ! iret ) { goto dfpn_client_receiver_shutdown; }
233     recv_buf[ len_recv_buf + iret ] = '\0';
234
235     /* take each line */
236     lock( &dfpn_client_lock );
237     for ( ;; ) {
238
239       str_line_end = strchr( recv_buf, '\n' );
240       if ( str_line_end == NULL )
241         {
242           if ( iret + len_recv_buf + 1 >= SIZE_RECV_BUF )
243             {
244               unlock( &dfpn_client_lock );
245               out_warning( "%s", str_ovrflw_line );
246               goto dfpn_client_receiver_shutdown;
247             }
248           break;
249         }
250
251       size = str_line_end - recv_buf;
252       if ( size + 1 >= SIZE_LINE_BUF )
253         {
254           unlock( &dfpn_client_lock );
255           out_warning( "%s", str_ovrflw_line );
256           goto dfpn_client_receiver_shutdown;
257         }
258       
259       memcpy( line_buf, recv_buf, size );
260       memmove( recv_buf, str_line_end+1, strlen(str_line_end+1) + 1 );
261
262       line_buf[size] = '\0';
263
264       if ( proce_line( line_buf ) < 0 )
265         {
266           unlock( &dfpn_client_lock );
267           out_warning( "invalid messages from DFPN server" );
268           goto dfpn_client_receiver_shutdown;
269         }
270     }
271     unlock( &dfpn_client_lock );
272   }
273
274  dfpn_client_receiver_shutdown:
275   sckt_shutdown( dfpn_client_sckt );
276   dfpn_client_sckt = SCKT_NULL;
277   out_warning( "A connection to DFPN server is down." );
278
279   return 0;
280 }
281 #  if defined(_MSC_VER)
282 #    pragma warning(default:4100)
283 #  elif defined(__ICC)
284 #    pragma warning(default:869)
285 #endif
286
287
288 static int CONV proce_line( char *line_buf )
289 {
290   const char *token;
291   volatile dfpn_client_cresult_t *pcresult;
292   char *last;
293
294   token = strtok_r( line_buf, str_delimiters, &last );
295   if ( token == NULL ) { return -1; }
296
297   /* check signature */
298   if ( strcmp( token, (const char *)dfpn_client_signature ) ) { return 1; }
299
300   token = strtok_r( NULL, str_delimiters, &last );
301   if ( token == NULL ) { return -1; }
302
303   /* root node */
304   if ( ! strcmp( token, "WIN" ) )
305     {
306       token = strtok_r( NULL, str_delimiters, &last );
307       if ( token == NULL || ! is_move( token ) ) { return -1; }
308       dfpn_client_rresult   = dfpn_client_win;
309       dfpn_client_flag_read = 1;
310       memcpy( (char *)dfpn_client_str_move, token, 7 );
311       return 1;
312     }
313
314   if ( ! strcmp( token, "LOSE" ) )
315     {
316       dfpn_client_rresult   = dfpn_client_lose;
317       dfpn_client_flag_read = 1;
318       return 1;
319     }
320
321   if ( ! strcmp( token, "UNSOLVED" ) )
322     {
323       dfpn_client_rresult   = dfpn_client_misc;
324       dfpn_client_flag_read = 1;
325       return 1;
326     }
327
328   /* child node */
329   if ( ! is_move( token ) ) { return -1; }
330   if ( MAX_LEGAL_MOVES <= dfpn_client_num_cresult ) { return -1; }
331   pcresult = &dfpn_client_cresult[dfpn_client_num_cresult];
332   memcpy( (char *)pcresult->str_move, token, 7 );
333
334   token = strtok_r( NULL, str_delimiters, &last );
335   if ( token == NULL ) { return -1; }
336   
337   if ( ! strcmp( token, "WIN" ) )
338     {
339       pcresult->result         = dfpn_client_win;
340       dfpn_client_flag_read    = 1;
341       dfpn_client_num_cresult += 1;
342       return 1;
343     }
344
345   if ( ! strcmp( token, "LOSE" ) )
346     {
347       pcresult->result         = dfpn_client_lose;
348       dfpn_client_flag_read    = 1;
349       dfpn_client_num_cresult += 1;
350       return 1;
351     }
352
353   if ( ! strcmp( token, "UNSOLVED" ) )
354     {
355       pcresult->result         = dfpn_client_misc;
356       dfpn_client_flag_read    = 1;
357       dfpn_client_num_cresult += 1;
358       return 1;
359     }
360
361   return -1;
362 }
363
364 #endif /* DFPN_CLINET */
365
366
367 #if defined(TLP)
368
369 #  if defined(_WIN32)
370 static unsigned int __stdcall start_address( void *arg );
371 #  else
372 static void *start_address( void *arg );
373 #  endif
374
375 static tree_t *find_child( void );
376 static void init_state( const tree_t * restrict parent,
377                         tree_t * restrict child );
378 static void copy_state( tree_t * restrict parent,
379                         const tree_t * restrict child, int value );
380 static void wait_work( int tid, tree_t *parent );
381
382 int
383 tlp_start( void )
384 {
385   int work[ TLP_MAX_THREADS ];
386   int num;
387
388   if ( tlp_num ) { return 1; }
389
390   for ( num = 1; num < tlp_max; num++ )
391     {
392       work[num] = num;
393       
394 #  if defined(_WIN32)
395       if ( ! _beginthreadex( 0, 0, start_address, work+num, 0, 0 ) )
396         {
397           str_error = "_beginthreadex() failed.";
398           return -2;
399         }
400 #  else
401       {
402         pthread_t pt;
403         if ( pthread_create( &pt, &pthread_attr, start_address, work+num ) )
404           {
405             str_error = "pthread_create() failed.";
406             return -2;
407           }
408       }
409 #  endif
410     }
411   while ( tlp_num +1 < tlp_max ) { tlp_yield(); }
412
413   return 1;
414 }
415
416
417 void
418 tlp_end( void )
419 {
420   tlp_abort = 1;
421   while ( tlp_num ) { tlp_yield(); }
422   tlp_abort = 0;
423 }
424
425
426 int
427 tlp_split( tree_t * restrict ptree )
428 {
429   tree_t *child;
430   int num, nchild, i;
431
432   lock( &tlp_lock );
433
434   if ( ! tlp_idle || ptree->tlp_abort )
435     {
436       unlock( &tlp_lock );
437       return 0;
438     }
439
440   tlp_ptrees[ ptree->tlp_id ] = NULL;
441   ptree->tlp_nsibling         = 0;
442   nchild                      = 0;
443   for ( num = 0; num < tlp_max; num++ )
444     {
445       if ( tlp_ptrees[num] ) { ptree->tlp_ptrees_sibling[num] = 0; }
446       else {
447         child = find_child();
448         if ( ! child ) { continue; }
449
450         nchild += 1;
451
452         for ( i=0; i<tlp_max; i++ ) { child->tlp_ptrees_sibling[i] = NULL; }
453         child->tlp_ptree_parent        = ptree;
454         child->tlp_id                  = (unsigned char)num;
455         child->tlp_used                = 1;
456         child->tlp_abort               = 0;
457         ptree->tlp_ptrees_sibling[num] = child;
458         ptree->tlp_nsibling           += 1;
459         init_state( ptree, child );
460
461         tlp_ptrees[num] = child;
462       }
463     }
464
465   if ( ! nchild )
466     {
467       tlp_ptrees[ ptree->tlp_id ] = ptree;
468       unlock( &tlp_lock );
469       return 0;
470     }
471   
472   tlp_nsplit += 1;
473   tlp_idle   += 1;
474
475   unlock( &tlp_lock );
476   
477   wait_work( ptree->tlp_id, ptree );
478
479   return 1;
480 }
481
482
483 void
484 tlp_set_abort( tree_t * restrict ptree )
485 {
486   int num;
487
488   ptree->tlp_abort = 1;
489   for ( num = 0; num < tlp_max; num++ )
490     if ( ptree->tlp_ptrees_sibling[num] )
491       {
492         tlp_set_abort( ptree->tlp_ptrees_sibling[num] );
493       }
494 }
495
496
497 #if defined(MNJ_LAN) || defined(USI)
498 uint64_t
499 tlp_count_node( tree_t * restrict ptree )
500 {
501   uint64_t uret = ptree->node_searched;
502   int num;
503
504   for ( num = 0; num < tlp_max; num++ )
505     if ( ptree->tlp_ptrees_sibling[num] )
506       {
507         uret += tlp_count_node( ptree->tlp_ptrees_sibling[num] );
508       }
509
510   return uret;
511 }
512 #endif
513
514
515 int
516 tlp_is_descendant( const tree_t * restrict ptree, int slot_ancestor )
517 {
518   int slot = (int)ptree->tlp_slot;
519
520   for ( ;; ) {
521     if ( slot == slot_ancestor ) { return 1; }
522     else if ( ! slot )           { return 0; }
523     else { slot = tlp_atree_work[slot].tlp_ptree_parent->tlp_slot; }
524   }
525 }
526
527
528 #  if defined(_MSC_VER)
529 static unsigned int __stdcall start_address( void *arg )
530 #  else
531 static void *start_address( void *arg )
532 #endif
533 {
534   int tid = *(int *)arg;
535
536   tlp_ptrees[tid] = NULL;
537
538   lock( &tlp_lock );
539   Out( "Hi from thread no.%d\n", tid );
540   tlp_num  += 1;
541   tlp_idle += 1;
542   unlock( &tlp_lock );
543
544   wait_work( tid, NULL );
545
546   lock( &tlp_lock );
547   Out( "Bye from thread no.%d\n", tid );
548   tlp_num  -= 1;
549   tlp_idle -= 1;
550   unlock( &tlp_lock );
551
552   return 0;
553 }
554
555
556 static void
557 wait_work( int tid, tree_t *parent )
558 {
559   tree_t *slot;
560   int value;
561
562   for ( ;; ) {
563
564     for ( ;; ) {
565       if ( tlp_ptrees[tid] )                  { break; }
566       if ( parent && ! parent->tlp_nsibling ) { break; }
567       if ( tlp_abort )                        { return; }
568
569       tlp_yield();
570     }
571
572     lock( &tlp_lock );
573     if ( ! tlp_ptrees[tid] ) { tlp_ptrees[tid] = parent; }
574     tlp_idle -= 1;
575     unlock( &tlp_lock );
576
577     slot = tlp_ptrees[tid];
578     if ( slot == parent ) { return; }
579
580     value = tlp_search( slot,
581                         slot->tlp_ptree_parent->tlp_best,
582                         slot->tlp_ptree_parent->tlp_beta,
583                         slot->tlp_ptree_parent->tlp_turn,
584                         slot->tlp_ptree_parent->tlp_depth,
585                         slot->tlp_ptree_parent->tlp_ply,
586                         slot->tlp_ptree_parent->tlp_state_node );
587     
588     lock( &tlp_lock );
589     copy_state( slot->tlp_ptree_parent, slot, value );
590     slot->tlp_ptree_parent->tlp_nsibling            -= 1;
591     slot->tlp_ptree_parent->tlp_ptrees_sibling[tid]  = NULL;
592     slot->tlp_used   = 0;
593     tlp_ptrees[tid]  = NULL;
594     tlp_idle        += 1;
595     unlock( &tlp_lock);
596   }
597 }
598
599
600 static tree_t *
601 find_child( void )
602 {
603   int i;
604
605   for ( i = 1; i < TLP_NUM_WORK && tlp_atree_work[i].tlp_used; i++ );
606   if ( i == TLP_NUM_WORK ) { return NULL; }
607   if ( i > tlp_nslot ) { tlp_nslot = i; }
608
609   return tlp_atree_work + i;
610 }
611
612
613 static void
614 init_state( const tree_t * restrict parent, tree_t * restrict child )
615 {
616   int i, ply;
617
618   child->posi                  = parent->posi;
619   child->node_searched         = 0;
620   child->null_pruning_done     = 0;
621   child->null_pruning_tried    = 0;
622   child->check_extension_done  = 0;
623   child->recap_extension_done  = 0;
624   child->onerp_extension_done  = 0;
625   child->neval_called          = 0;
626   child->nquies_called         = 0;
627   child->nfour_fold_rep        = 0;
628   child->nperpetual_check      = 0;
629   child->nsuperior_rep         = 0;
630   child->nrep_tried            = 0;
631   child->ntrans_always_hit     = 0;
632   child->ntrans_prefer_hit     = 0;
633   child->ntrans_probe          = 0;
634   child->ntrans_exact          = 0;
635   child->ntrans_lower          = 0;
636   child->ntrans_upper          = 0;
637   child->ntrans_superior_hit   = 0;
638   child->ntrans_inferior_hit   = 0;
639   child->fail_high             = 0;
640   child->fail_high_first       = 0;
641   ply = parent->tlp_ply;
642
643   child->anext_move[ply].value_cap1 = parent->anext_move[ply].value_cap1;
644   child->anext_move[ply].value_cap2 = parent->anext_move[ply].value_cap2;
645   child->anext_move[ply].move_cap1  = parent->anext_move[ply].move_cap1;
646   child->anext_move[ply].move_cap2  = parent->anext_move[ply].move_cap2;
647
648   child->move_last[ply]        = child->amove;
649   child->save_eval[ply]        = parent->save_eval[ply];
650   child->current_move[ply-1]   = parent->current_move[ply-1];
651   child->nsuc_check[ply-1]     = parent->nsuc_check[ply-1];
652   child->nsuc_check[ply]       = parent->nsuc_check[ply];
653   child->nrep                  = parent->nrep;
654
655   memcpy( child->hist_good,  parent->hist_good,  sizeof(parent->hist_good) );
656   memcpy( child->hist_tried, parent->hist_tried, sizeof(parent->hist_tried) );
657
658   for ( i = 0; i < child->nrep + ply - 1; i++ )
659     {
660       child->rep_board_list[i] = parent->rep_board_list[i];
661       child->rep_hand_list[i]  = parent->rep_hand_list[i];
662     }
663   for ( i = ply; i < PLY_MAX; i++ )
664     {
665       child->amove_killer[i] = parent->amove_killer[i];
666       child->killers[i]      = parent->killers[i];
667     }
668
669 }
670
671
672 static void
673 copy_state( tree_t * restrict parent, const tree_t * restrict child,
674             int value )
675 {
676   int i, ply;
677
678   parent->check_extension_done += child->check_extension_done;
679   parent->recap_extension_done += child->recap_extension_done;
680
681   if ( ! child->node_searched ) { return; }
682
683   parent->node_searched        += child->node_searched;
684   parent->null_pruning_done    += child->null_pruning_done;
685   parent->null_pruning_tried   += child->null_pruning_tried;
686   parent->onerp_extension_done += child->onerp_extension_done;
687   parent->neval_called         += child->neval_called;
688   parent->nquies_called        += child->nquies_called;
689   parent->nrep_tried           += child->nrep_tried;
690   parent->nfour_fold_rep       += child->nfour_fold_rep;
691   parent->nperpetual_check     += child->nperpetual_check;
692   parent->nsuperior_rep        += child->nsuperior_rep;
693   parent->ntrans_always_hit    += child->ntrans_always_hit;
694   parent->ntrans_prefer_hit    += child->ntrans_prefer_hit;
695   parent->ntrans_probe         += child->ntrans_probe;
696   parent->ntrans_exact         += child->ntrans_exact;
697   parent->ntrans_lower         += child->ntrans_lower;
698   parent->ntrans_upper         += child->ntrans_upper;
699   parent->ntrans_superior_hit  += child->ntrans_superior_hit;
700   parent->ntrans_inferior_hit  += child->ntrans_inferior_hit;
701   parent->fail_high_first      += child->fail_high_first;
702   parent->fail_high            += child->fail_high;
703
704   if ( child->tlp_abort || value <= parent->tlp_best ) { return; }
705
706   ply              = parent->tlp_ply;
707   parent->tlp_best = (short)value;
708   parent->pv[ply]  = child->pv[ply];
709
710   lock( &parent->tlp_lock );
711   parent->current_move[ply] = child->current_move[ply];
712   memcpy( parent->hist_tried, child->hist_tried, sizeof(child->hist_tried) );
713   memcpy( parent->hist_good,  child->hist_good,  sizeof(child->hist_good) );
714   for ( i = ply; i < PLY_MAX; i++ ) 
715     {
716       parent->amove_killer[i] = child->amove_killer[i];
717       parent->killers[i]      = child->killers[i];
718     }
719   unlock( &parent->tlp_lock );
720 }
721
722
723 #endif /* TLP */