home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / comp / opponent.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1991-06-05  |  16.0 KB  |  525 lines
  1. // documentation
  2.     // Copyright (C) 1991 David Stoutamire (daves@alpha.ces.cwru.edu)
  3.     //
  4.     // This program is free software; you can redistribute it and/or modify
  5.     // it under the terms of the GNU General Public License as published by
  6.     // the Free Software Foundation, version 2.
  7.     // 
  8.     // This program is distributed in the hope that it will be useful,
  9.     // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.     // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.     // GNU General Public License for more details.
  12.     // 
  13.     // You should have received a copy of the GNU General Public License
  14.     // along with this program (file "COPYING"); if not, write to the Free
  15.     // Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16.     //
  17.     // This files holds all the code associated with the Opponent
  18.     // class.  An Opponent is an object which can accept a description
  19.     // of the state of the game and recommend a move.
  20.  
  21. // includes
  22.     #include "iku.h"
  23.     #include <MLCG.h>
  24.     #include <Uniform.h>
  25.     #include <RandomInteger.h>  // I believe this changes in g++ 1.39
  26.  
  27. // variables
  28.     static MLCG rgen;        // Used for random number generation
  29.     static Uniform rnd(0.0,1.0,&rgen);
  30.  
  31. // class Opponent
  32.     void Opponent::evaluate(Board& b) {
  33.     // evaluate gets an evaluation for each legal move on the board,
  34.     // and marks which are playable.  Two techniques are defined
  35.     // to facilitate building new Opponents.  The evaluate call
  36.     // gets a Board and is expected to rank all moves at once.
  37.     // It defaults to caling evalpos, which is a move-at-a-time
  38.     // evaluator.  Using evalpos thus eliminates the outer loop
  39.     // and reference to play{evals,able}[][].
  40.         int i,j;
  41.         doboard(i,j) {
  42.             Pos p(i,j);
  43.             if (b.islegalmove(Move(play,p))) {
  44.                 playevals[i][j]=evalpos(b,p);
  45.                 playable[i][j]=true;
  46.                 }
  47.             else
  48.                 playable[i][j]=false;
  49.             }
  50.         }
  51.     float Opponent::evalpos(Board& b, Pos p) {
  52.         fatal("default evaluate(Board,Pos) called.");
  53.         }
  54.     Move Opponent::getmove(Board& b) {
  55.     // simply returns the best ranking move.
  56.         evaluate(b);
  57.         float best=reallylowfloat;
  58.         moveenum kind=play;
  59.         int bestrow=0, bestcol=0;
  60.         int i,j;
  61.     
  62.         doboard(i,j)
  63.             if (playable[i][j]&&best<playevals[i][j]) {
  64.                 bestrow=i;
  65.                 bestcol=j;
  66.                 best=playevals[i][j];
  67.                 }
  68.  
  69.         if (best<0.0)
  70.             kind=pass;
  71.  
  72.         return Move(kind,Pos(bestrow,bestcol));
  73.         }
  74.     void Opponent::docheckpt() {
  75.     // This saves state for those opponents which need it.
  76.         }
  77.     static Opponent* opPosptcomp=NULL;
  78.     static int Posptcomp(Pos* a, Pos* b) {
  79.         float t=opPosptcomp->playevals[a->row][a->col]
  80.                           -opPosptcomp->playevals[b->row][b->col];
  81.         if (t>0.0)
  82.             return(-1);
  83.         else if (t<0.0)
  84.             return(1);
  85.         else
  86.             return(0);
  87.         }
  88.     void Opponent::study(Board& b, Move m) {
  89.     // this routine is where the action is during learning.
  90.         if (m.kind==resign)
  91.             fatal("Asked to study a resignation in Opponent::study.");
  92.  
  93.         // evaluate moves and report the result.
  94.         evaluate(b);
  95.         takescore(b.movenum,score(m));
  96.  
  97.         float target=0.0;
  98.         if (m.kind==play)
  99.             target=playevals[m.where.row][m.where.col];
  100.  
  101.         int count=0,i,j=0;
  102.     if (dolearn) {
  103.         doboard(i,j)
  104.         if (playable[i][j])
  105.             count++;
  106.         float rec=1/((float)count+1);      // legal moves + pass
  107.  
  108.         int bad=0;
  109.         doboard(i,j)
  110.         if (playable[i][j]&&playevals[i][j]>=target) {
  111.             bad++;
  112.             if (playevals[i][j]==target)
  113.             slide(b,Pos(i,j),-rec*0.5);
  114.             else {
  115.             bad++;
  116.             slide(b,Pos(i,j),-rec);
  117.             }
  118.             }
  119.         
  120.         if (target<=0.0)
  121.         bad++;
  122.         if (target<0.0)
  123.         bad++;
  124.  
  125.         if (m.kind==play) 
  126.         slide(b,m.where,rec*bad*0.5);
  127.         }
  128.  
  129.         if (evalfile!="nofile") {
  130.             Pos worst[361];
  131.             int next=0;
  132.             doboard(i,j)
  133.                 if (playable[i][j]) {
  134.                     worst[next++]=Pos(i,j);
  135.             }
  136.             opPosptcomp=this;
  137.             qsort((char*)worst,next,sizeof(Pos),Posptcomp);
  138.             FILE *psfp=NULL;
  139.  
  140.         // make postscript file if wanted
  141.             if (postscriptdir!="nodir") {
  142.                 psfp=fopen((char*)(postscriptdir+"/"+dec(b.movenum)),"w");
  143.                 fprintf(psfp,"%%%%BoundingBox: 160 290 440 570\n");
  144.                 int j,k;
  145.                 doboard(j,k)
  146.                     if (b.board[j][k]==blackstone)
  147.                         fprintf(psfp,"%d %d () B\n",k+1,j+1);
  148.                     else if (b.board[j][k]==whitestone)
  149.                         fprintf(psfp,"%d %d () W\n",k+1,j+1);
  150.                 }
  151.  
  152.         // make COSMOS format file
  153.             FILE *fp=fopen((char*)evalfile,"a");
  154.             fprintf(fp,"%c %d ",(b.turntoplay==blackstone)?'B':'W',b.movenum);
  155.             fprintf(fp,"%s\n",(char *)m.str());
  156.             float last=reallylowfloat;
  157.             int rank=0,after=0;
  158.             for (i=0;i<next;i++) {
  159.                 float now=playevals[worst[i].row][worst[i].col];
  160.                 if (now!=last) {
  161.             if (now<target)
  162.             after++;
  163.             if (after>=10)
  164.             break;
  165.                     rank=i+1;
  166.             }
  167.                 fprintf(fp,"MARK %d@%s\n",rank,(char *)worst[i].str());
  168.                 last=now;
  169.                 if (psfp!=NULL)
  170.                     if (m.where.row==worst[i].row&&m.where.col==worst[i].col)
  171.                         if (b.turntoplay==blackstone)
  172.                             fprintf(psfp,"%d %d (%d) MB\n",worst[i].col+1,worst[i].row+1,rank);
  173.                         else
  174.                             fprintf(psfp,"%d %d (%d) MW\n",worst[i].col+1,worst[i].row+1,rank);
  175.                     else
  176.                         fprintf(psfp,"%d %d (%d) C\n",worst[i].col+1,worst[i].row+1,rank);
  177.                 }
  178.             if (psfp!=NULL) {
  179.                 fprintf(psfp,"showpage\n");
  180.                 fclose(psfp);
  181.                 }
  182.         /*
  183.             fprintf(fp,"COM");
  184.             last=reallylowfloat;
  185.             for (i=0;i<next;i++) {
  186.                 float now=playevals[worst[i].row][worst[i].col];
  187.                 if (now!=last)
  188.                     fprintf(fp,"\n\n%d - %g\n",i+1,now);
  189.                 last=now;
  190.                 }
  191.             fprintf(fp,"\nENDCOM\n");
  192.         */
  193.             fclose(fp);
  194.             }
  195.         }
  196.     void Opponent::slide(Board& b, Pos p, float deriv) {
  197.     // slide is how the gradient gets communicated back to
  198.     // the opponent.
  199.  
  200.         // fatal("Default slide() called.");
  201.         }
  202.     float Opponent::score(Move m) {
  203.     // this computes the error of the evaluation.
  204.         float target;
  205.         int numwrong=0;
  206.         int numseen=0;
  207.         if (m.kind==play)
  208.             target=playevals[m.where.row][m.where.col];
  209.         else if (m.kind==pass)
  210.             target=0.0;
  211.         else if (m.kind==resign)    //  how should resignations be handled?
  212.             fatal("Asked to score a resignation.");
  213.         else
  214.             fatal("Bad kind in printscore.");
  215.         int i,j;
  216.         doboard(i,j) {
  217.             if (playable[i][j]) {
  218.                 if (playevals[i][j]>target)
  219.                     numwrong++;
  220.                 if (playevals[i][j]>=target)
  221.                     numwrong++;
  222.                 numseen++;
  223.                 }
  224.             }
  225.         if (m.kind==play) {
  226.             if (target<0.0)
  227.                 numwrong++;
  228.             if (target<=0.0)
  229.                 numwrong++;
  230.             }
  231.         numseen++;
  232.         /*
  233.         if (printevals) {
  234.             for (i=0;i<19;i++) {
  235.                 for (j=0;j<19;j++)
  236.                     if (playable[i][j])
  237.                         cout << form("%3d ",playevals[i][j]);
  238.                     else
  239.                         cout << "*** ";
  240.                 cout << "\n";
  241.                 }
  242.             }
  243.         */
  244.         return ((float)numwrong)*0.5/((float)numseen);
  245.         }
  246.     Opponent::~Opponent() {
  247.         }
  248.  
  249.     // a PatternusingOpponent characterizes moves by some local
  250.     // pattern on the board.  When one is created it gets information
  251.     // about which kind from the command line.
  252.     PatternusingOpponent::PatternusingOpponent() {
  253.         String s=nextarg();
  254.         if (s=="nxn") {    
  255.             patterntouse=patnxn;
  256.             getnum(nxnsize);    
  257.             }
  258.         else if (s=="diamond") {
  259.             patterntouse=patdiamond;
  260.             getnum(mindiamondsize);
  261.             getnum(maxdiamondsize);
  262.             getnum(diamondmustsee);
  263.             getnum(libscutoff);
  264.             }
  265.         else if (s=="group") {
  266.             patterntouse=patgroup;
  267.             getnum(groupradius);
  268.             }
  269.         else
  270.             fatal("Bad pattern type specifier: "+s);
  271.         }
  272.     Pattern PatternusingOpponent::extract(Board& b, Move m) {
  273.         Pattern p(patterntouse);
  274.         p.extract(*this,b,m);
  275.         return p;
  276.         }
  277.  
  278. // class MetaOpponent
  279.     // a MetaOpponent is a convenience class which allows using the
  280.     // sum of the evaluations of multiple other opponents for the
  281.     // computation of error and gradient calculation.  For example,
  282.     // noise can be added by using the command line specification
  283.     // "meta 2 random <opponent>", where 2 specifies that we will
  284.     // be adding the evaluations of 2 opponents.  By definition,
  285.     // gradient info is copied to all sub-opponents equally.
  286.     MetaOpponent::MetaOpponent() {
  287.         getnum(numagents);
  288.         agents=malloc(sizeof(Opponent*)*numagents);
  289.         for (int i=0;i<numagents;i++)
  290.             agents[i]=makeopponent();
  291.         }
  292.     MetaOpponent::~MetaOpponent() {
  293.         for (int i=0;i<numagents;i++)
  294.             delete agents[i];
  295.         free(agents);
  296.         }
  297.     void MetaOpponent::evaluate(Board& b) {
  298.         int i,j;
  299.         doboard(i,j)
  300.             if (b.islegalmove(Move(play,Pos(i,j)))) {
  301.                 playevals[i][j]=0.0;
  302.                 playable[i][j]=true;
  303.                 }
  304.             else
  305.                 playable[i][j]=false;
  306.         for (int k=0;k<numagents;k++) {
  307.             agents[k]->evaluate(b);
  308.             doboard(i,j)
  309.                 if (playable[i][j])
  310.                     playevals[i][j]+=agents[k]->playevals[i][j];
  311.             }
  312.         }
  313.     void MetaOpponent::study(Board& b, Move m) {
  314.         evaluate(b);
  315.         int i,j;
  316.         dontprint=true;
  317.         for (int k=0;k<numagents;k++) {
  318.             doboard(i,j)
  319.                 agents[k]->playevals[i][j]=playevals[i][j];
  320.             agents[k]->study(b,m);
  321.             }
  322.         dontprint=false;
  323.         takescore(b.movenum,score(m));
  324.         }
  325.  
  326. // class HashOpponent
  327.     HashOpponent::HashOpponent() {
  328.         getnum(hashsize);
  329.         table=new float[hashsize];
  330.         filename=nextarg();
  331.     if (filename!="nofile") {
  332.             FILE* fp=fopen(filename,"r");
  333.             if (fp==NULL) {
  334.                 for (int i=0;i<hashsize;i++)
  335.                     table[i]=0.0;
  336.                 docheckpt();
  337.                 }
  338.             else {
  339.                 fread(table,sizeof(float),hashsize,fp);
  340.                 fclose(fp);
  341.                 }
  342.             }
  343.         else
  344.             for (int i=0;i<hashsize;i++)
  345.                 table[i]=0.0;
  346.         }
  347.     HashOpponent::~HashOpponent() {
  348.         // delete [hashsize] table;   g++ issues a warning on this
  349.         delete table;
  350.         }
  351.     void HashOpponent::docheckpt() {
  352.         if (filename!="nofile") {
  353.             FILE* fp=fopen(filename,"w");
  354.             fwrite(table,sizeof(float),hashsize,fp);
  355.             fclose(fp);
  356.             }
  357.         }
  358.     float HashOpponent::evalpos(Board& b, Pos p) {
  359.         return table[extract(b,Move(play,p)).hash(hashsize)];
  360.         }
  361.     void HashOpponent::slide(Board& b, Pos p, float deriv) {
  362.         table[extract(b,Move(play,p)).hash(hashsize)]+=deriv;
  363.         }
  364.  
  365. // class MapOpponent
  366.     MapOpponent::MapOpponent():vals(0.0,49999) {
  367.         filename=nextarg();
  368.         if (filename!="nofile") {
  369.             #ifdef IRIX
  370.                 fatal("Never rewrote MapOpponent::loading.");
  371.             #endif // IRIX
  372.             filebuf f;
  373.             f.open(filename,input);
  374.             istream from(&f);
  375.             while (from.readable()) {
  376.                 String s;
  377.                 from >> s;
  378.                 if (s=="EOF")
  379.                     break;
  380.                 Pattern p(patterntouse,s);
  381.                 from >> vals[p];
  382.                 }
  383.             }
  384.         if (vals.contains(Pattern()))
  385.             fatal("At initialization, contained null pattern.\n");
  386.         }
  387.     float MapOpponent::evalpos(Board& b, Pos p) {
  388.         return vals[extract(b,Move(play,p))];
  389.         }
  390.     void MapOpponent::docheckpt() {
  391.         if (filename!="nofile") {
  392.             #ifdef IRIX
  393.                 fatal("Never rewrote MapOpponent::docheckpt.");
  394.             #endif // IRIX
  395.             File f(filename,io_writeonly,a_create);
  396.             for (Pix i=vals.first();i!=0;vals.next(i)) {
  397.                 f.put(vals.key(i).str()+form(" %g\n",vals.contents(i)));
  398.                 }
  399.             f.put("EOF\n");
  400.             }
  401.         }
  402.     void MapOpponent::slide(Board& b, Pos p, float deriv) {
  403.         vals[extract(b,Move(play,p))]+=deriv;
  404.         }
  405.  
  406. // class RandomOpponent
  407.     float RandomOpponent::evalpos(Board& b, Pos p) {
  408.         return rnd()*0.001;
  409.         }
  410.  
  411. // class GreedyOpponent
  412.     float GreedyOpponent::evalpos(Board& b, Pos p) {
  413.         Board bd(b);
  414.         bd.applymove(Move(play,p));
  415.         if (b.turntoplay==blackstone)
  416.             return bd.whitetaken-b.whitetaken-(bd.blacktaken-b.blacktaken);
  417.         else
  418.             return bd.blacktaken-b.blacktaken-(bd.whitetaken-b.whitetaken);
  419.         }
  420.  
  421. // class CursesOpponent
  422.     CursesOpponent::CursesOpponent() {
  423.         w=new CursesWindow(stdscr);
  424.         w->clear();
  425.         crmode();
  426.         noecho();
  427.         }
  428.     CursesOpponent::~CursesOpponent() {
  429.         w->clear();
  430.         w->refresh();
  431.         delete w;
  432.         }
  433.     void CursesOpponent::evaluate(Board& b) {
  434.         moveenum kind=play;
  435.         w->erase();
  436.         w->addstr(b.str());
  437.         loop {
  438.             w->move(19-row,2*col+4);
  439.             w->refresh();
  440.             char  c=getchar();
  441.     
  442.             if (c==' ')
  443.                 if (b.islegalmove(Move(play,Pos(row,col))))
  444.                     break;
  445.     
  446.             if (c==' ') {
  447.                 w->clear();
  448.                 w->addstr(b.str());
  449.                 w->refresh();
  450.                 continue;
  451.                 }
  452.  
  453.         if (c=='c') {
  454.         w->move(22,0);
  455.         w->addstr("Comment (press cntl-c when done):\n");
  456.         w->refresh();
  457.         echo();
  458.         system((char*)("echo COM >>"+dribble));
  459.         system((char*)("cat >>"+dribble));
  460.         system((char*)("echo \" \" >>"+dribble));
  461.         system((char*)("echo ENDCOM >>"+dribble));
  462.         w->clear();
  463.         w->addstr(b.str());
  464.         w->refresh();
  465.         noecho();
  466.         continue;
  467.         }
  468.     
  469.             if (c=='p') {
  470.                 kind=pass;
  471.                 break;
  472.                 }
  473.                 
  474.             if (c=='q') {
  475.                 w->erase();
  476.                 w->refresh();
  477.                 exit(0);
  478.                 }
  479.     
  480.             if (c=='h'||c=='b'||c=='y') col--;
  481.             if (c=='j'||c=='n'||c=='b') row--;
  482.             if (c=='k'||c=='y'||c=='u') row++;
  483.             if (c=='l'||c=='u'||c=='n') col++;
  484.     
  485.             if (col<0) col+=19;
  486.             else if (col>18) col-=19;
  487.             if (row<0) row+=19;
  488.             else if (row>18) row-=19;
  489.             }
  490.     
  491.         int i,j;
  492.         doboard(i,j) {
  493.             playevals[i][j]= -1.0;
  494.             playable[i][j]=b.islegalmove(Move(play,Pos(i,j)));
  495.             }
  496.  
  497.         if (kind==play) {
  498.             playevals[row][col]=1.0;
  499.             Board bd(b);
  500.             bd.applymove(Move(play,Pos(row,col)));
  501.             bd.comment="Thinking...";
  502.             w->erase();
  503.             w->addstr(bd.str());
  504.             w->refresh();
  505.             }
  506.         }
  507.  
  508. Opponent* makeopponent() {
  509.     String s=nextarg();
  510.     if (s=="curses")
  511.         return(new CursesOpponent);
  512.     else if (s=="random")
  513.         return(new RandomOpponent);
  514.     else if (s=="map")
  515.         return(new MapOpponent);
  516.     else if (s=="hash")
  517.         return(new HashOpponent);
  518.     else if (s=="greedy")
  519.         return(new GreedyOpponent);
  520.     else if (s=="meta")
  521.         return(new MetaOpponent);
  522.     else
  523.         fatal("Bad opponent specifier.");
  524.     }
  525.