home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / OPENSTEP / Games / NeXTGo-3.0-MIS / smartgotree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-07-06  |  6.9 KB  |  428 lines
  1. #include "comment.header"
  2.  
  3. /* $Id: smartgotree.c,v 1.3 1997/07/06 19:35:11 ergo Exp $ */
  4.  
  5. /*
  6.  * $Log: smartgotree.c,v $
  7.  * Revision 1.3  1997/07/06 19:35:11  ergo
  8.  * actual version
  9.  *
  10.  * Revision 1.2  1997/05/04 18:57:15  ergo
  11.  * added time control for moves
  12.  *
  13.  */
  14.  
  15. #include "smartgo.h"
  16.  
  17. /*  Define the following variable for debugging information.  */
  18. /*  #define _DEBUG_ON_  */
  19.  
  20. #ifdef _DEBUG_ON_
  21. #include <stdio.h>
  22.  
  23. void display_tree(node* root_node)
  24. {
  25.   node *tnode;
  26.  
  27.   tnode = root_node;
  28.  
  29.   while (tnode != NULL)
  30.     {
  31.       if (tnode->properties != NULL)
  32.     printf(";");
  33.       if (tnode->variants != NULL)
  34.     {
  35.       printf("(");
  36.       display_tree(tnode->variants);
  37.       printf(")");
  38.     }
  39.       if (tnode->next == NULL)
  40.     {
  41.       while (tnode->prev != NULL)
  42.         tnode = tnode->prev;
  43.       tnode = tnode->next_var;
  44.       if (tnode != NULL)
  45.         printf(")(");
  46.     }
  47.       else
  48.     {
  49.       tnode = tnode->next;
  50.     }
  51.     }
  52. }
  53. #endif
  54.  
  55. node* forwardOneNode(node* currentNode)
  56. {
  57.   node *tnode;
  58.  
  59.   if (currentNode->variants != NULL)
  60.     {
  61.       currentNode->variants->recurse = 0;
  62.       return currentNode->variants;
  63.     }
  64.   else if (currentNode->next != NULL)
  65.     {
  66.       currentNode->next->recurse = 0;
  67.       return currentNode->next;
  68.     }
  69.   else
  70.     {
  71.       tnode = currentNode;
  72.       while (tnode->prev != NULL)
  73.     tnode = tnode->prev;
  74.       if (tnode->next_var != NULL)
  75.     {
  76.       tnode->next_var->recurse = 1;
  77.       return tnode->next_var;
  78.     }
  79.       else
  80.     {
  81.       return forwardOneNode0(currentNode->parent);
  82.     }
  83.     }
  84. }
  85.  
  86. node* forwardOneNode0(node* currentNode)
  87. {
  88.   node *tnode;
  89.  
  90.   if (currentNode->next != NULL)
  91.     {
  92.       currentNode->next->recurse = 1;
  93.       return currentNode->next;
  94.     }
  95.   else
  96.     {
  97.       tnode = currentNode;
  98.       while (tnode->prev != NULL)
  99.     tnode = tnode->prev;
  100.       if (tnode->next_var != NULL)
  101.     {
  102.       tnode->next_var->recurse = 1;
  103.       return tnode->next_var;
  104.     }
  105.       else
  106.     {
  107.       if (currentNode->parent != NULL)
  108.         {
  109.           return forwardOneNode0(currentNode->parent);
  110.         }
  111.       else
  112.         {
  113.           tnode->recurse = 1;
  114.           return tnode;
  115.         }
  116.     }
  117.     }
  118. }
  119.  
  120. node* backOneNode(node* currentNode)
  121. {
  122.   if (currentNode->prev != NULL)
  123.     {
  124.       if (currentNode->prev->variants != NULL)
  125.     {
  126.       return findLast(currentNode->prev->variants);
  127.     }
  128.       else
  129.     {
  130.       currentNode->prev->recurse = 1;
  131.       return currentNode->prev;
  132.     }
  133.     }
  134.   else
  135.     {
  136.       if (currentNode->prev_var != NULL)
  137.     {
  138.       return findLast0(currentNode->prev_var);
  139.     }
  140.       else
  141.     {
  142.       if (currentNode->parent != NULL)
  143.         {
  144.           currentNode->parent->recurse = 1;
  145.           return currentNode->parent;
  146.         }
  147.       else
  148.         {
  149.           return findLast(currentNode);
  150.         }
  151.     }
  152.     }
  153. }
  154.  
  155. node* findLast(node* currentNode)
  156. {
  157.   node *tnode;
  158.  
  159.   tnode = currentNode;
  160.  
  161.   while (tnode->next_var != NULL)
  162.     tnode = tnode->next_var;
  163.  
  164.   while (tnode->next != NULL)
  165.     tnode = tnode->next;
  166.  
  167.   if (tnode->variants != NULL)
  168.     {
  169.       return findLast(tnode->variants);
  170.     }
  171.   else
  172.     {
  173.       tnode->recurse = 1;
  174.       return tnode;
  175.     }
  176. }
  177.  
  178. node* findLast0(node* currentNode)
  179. {
  180.   node *tnode;
  181.  
  182.   tnode = currentNode;
  183.  
  184.   while (tnode->next != NULL)
  185.     tnode = tnode->next;
  186.  
  187.   if (tnode->variants != NULL)
  188.     {
  189.       return findLast(tnode->variants);
  190.     }
  191.   else
  192.     {
  193.       tnode->recurse = 1;
  194.       return tnode;
  195.     }
  196. }
  197.  
  198. node* forwardOneVariant(node* currentNode)
  199. {
  200.   node *tnode;
  201.  
  202.   tnode = currentNode;
  203.  
  204.   while (tnode->prev != NULL)
  205.     tnode = tnode->prev;
  206.  
  207.   if (tnode->next_var != NULL)
  208.     {
  209.       tnode->next_var->recurse = 1;
  210.       return tnode->next_var;
  211.     }
  212.   else
  213.     {
  214.       tnode->parent->variants->recurse = 1;
  215.       return tnode->parent->variants;
  216.     }
  217. }
  218.  
  219. node* backOneVariant(node* currentNode)
  220. {
  221.   node *tnode;
  222.  
  223.   tnode = currentNode;
  224.  
  225.   while (tnode->prev != NULL)
  226.     tnode = tnode->prev;
  227.  
  228.   if (tnode->prev_var != NULL)
  229.     {
  230.       tnode->prev_var->recurse = 1;
  231.       return tnode->prev_var;
  232.     }
  233.   else
  234.     {
  235.       while (tnode->next_var != NULL)
  236.     tnode = tnode->next_var;
  237.  
  238.       tnode->recurse = 1;
  239.       return tnode;
  240.     }
  241. }
  242.  
  243. void clearNodeFlags(node* currentNode)
  244. {
  245.   node *r, *v;
  246.  
  247.   r = currentNode;
  248.   while (r != NULL)
  249.     {
  250.       r->flag = 0;
  251.       r->recurse = 0;
  252.       v = r->variants;
  253.       while (v != NULL)
  254.     {
  255.       clearNodeFlags(v);
  256.       v = v->next_var;
  257.     }
  258.       r = r->next;
  259.     }
  260. }
  261.  
  262. int foundNode;
  263.  
  264. int evaluateSteps(node* currentNode, node* targetNode, unsigned char b[19][19])
  265. {
  266.   node *tnode, *vnodes;
  267.   int i, j;
  268.   extern int MAXX, MAXY;
  269.   unsigned char b0[19][19];
  270.  
  271.   for (i = 0; i < 19; i++)
  272.     for (j = 0; j < 19; j++)
  273.       b0[i][j] = b[i][j];
  274.  
  275.   tnode = currentNode;
  276.   while (tnode != targetNode)
  277.     {
  278.       if (tnode->properties != NULL)
  279.     {
  280.       evaluateNode(tnode->properties, b0);
  281.       tnode->flag = 1;
  282.     }
  283.  
  284.       vnodes = tnode->variants;
  285.       while (vnodes != NULL)
  286.     {
  287.       evaluateSteps(vnodes, targetNode, b0);
  288.       if (foundNode)
  289.         {
  290.           for (i = 0; i < MAXX; i++)
  291.         for (j = 0; j < MAXY; j++)
  292.           b[i][j] = b0[i][j];
  293.  
  294.           return 0;
  295.         }
  296.       vnodes = vnodes->next_var;
  297.     }
  298.  
  299.       if (tnode->next == NULL)
  300.     return 0;
  301.  
  302.       tnode = tnode->next;
  303.     }
  304.  
  305.   if (tnode == targetNode)
  306.     {
  307.       foundNode = 1;
  308.     }
  309.  
  310.   if ((tnode == targetNode) && (!tnode->flag) && (tnode->properties != NULL))
  311.     {
  312.       evaluateNode(tnode->properties, b0);
  313.       tnode->flag = 1;
  314.  
  315.       for (i = 0; i < MAXX; i++)
  316.     for (j = 0; j < MAXY; j++)
  317.       b[i][j] = b0[i][j];
  318.     }
  319.  
  320.   return 0;
  321. }
  322.  
  323. void buildToNode(node* targetNode)
  324. {
  325.   int i, j;
  326.   extern int blackCaptured, whiteCaptured, lastMove, hist[19][19];
  327.   extern unsigned char p[19][19];
  328.   extern node *rootNode;
  329.  
  330.   for (i = 0; i < 19; i++)
  331.     for (j = 0; j < 19; j++)
  332.       p[i][j] = hist[i][j] = 0;
  333.   blackCaptured = whiteCaptured = lastMove = 0;
  334.   clearNodeFlags(rootNode);
  335.  
  336.   foundNode = 0;
  337.  
  338.   evaluateSteps(rootNode, targetNode, p);
  339. }
  340.  
  341. node* stepForward(node* currentNode)
  342. {
  343.   node *tnode;
  344.   extern node *rootNode;
  345.  
  346.   tnode = currentNode;
  347.   do
  348.     {
  349.       tnode = forwardOneNode(tnode);
  350.     }
  351.   while ((tnode->properties == NULL) && (tnode != currentNode));
  352.  
  353.   if (tnode == currentNode)
  354.     {
  355.       tnode = rootNode;
  356.  
  357.       do
  358.     {
  359.       tnode = forwardOneNode(tnode);
  360.     }
  361.       while (tnode->properties == NULL);
  362.     }
  363.  
  364.   buildToNode(tnode);
  365.  
  366.   return tnode;
  367. }
  368.  
  369. node* stepBackward(node* currentNode)
  370. {
  371.   node *tnode;
  372.   extern node *rootNode;
  373.  
  374.   tnode = currentNode;
  375.   do
  376.     {
  377.       tnode = backOneNode(tnode);
  378.     }
  379.   while ((tnode->properties == NULL) && (tnode != currentNode));
  380.  
  381.   if (tnode == currentNode)
  382.     {
  383.       tnode = rootNode;
  384.  
  385.       tnode = findLast(tnode);
  386.     }
  387.  
  388.   buildToNode(tnode);
  389.  
  390.   return tnode;
  391. }
  392.  
  393. node* jumpForward(node* currentNode)
  394. {
  395.   node *tnode;
  396.  
  397.   tnode = currentNode;
  398.  
  399.   tnode = forwardOneVariant(tnode);
  400.  
  401.   while (tnode->properties == NULL)
  402.     {
  403.       tnode = forwardOneNode(tnode);
  404.     }
  405.  
  406.   buildToNode(tnode);
  407.  
  408.   return tnode;
  409. }
  410.  
  411. node* jumpBackward(node* currentNode)
  412. {
  413.   node *tnode;
  414.  
  415.   tnode = currentNode;
  416.   tnode = backOneVariant(tnode);
  417.  
  418.   while (tnode->properties == NULL)
  419.     {
  420.       tnode = forwardOneNode(tnode);
  421.     }
  422.  
  423.   buildToNode(tnode);
  424.  
  425.   return tnode;
  426. }
  427.  
  428.