diff options
| -rw-r--r-- | Makefile | 27 | ||||
| -rw-r--r-- | _player_mcb.cpp | 73 | ||||
| -rw-r--r-- | _player_mcmaxb.cpp | 77 | ||||
| -rw-r--r-- | common.h | 144 | ||||
| -rw-r--r-- | interactor/.gitignore (renamed from .gitignore) | 0 | ||||
| -rw-r--r-- | interactor/common.js (renamed from common.js) | 0 | ||||
| -rw-r--r-- | interactor/index.html (renamed from index.html) | 0 | ||||
| -rwxr-xr-x | interactor/interactor.js (renamed from interactor.js) | 0 | ||||
| -rw-r--r-- | interactor/package.json (renamed from package.json) | 0 | ||||
| -rw-r--r-- | jscalc/chainreaction.js | 108 | ||||
| -rw-r--r-- | jscalc/chainreaction_4x4.txt | 1 | ||||
| -rw-r--r-- | manager.cpp | 199 | ||||
| -rw-r--r-- | player_d1.cpp | 46 | ||||
| -rw-r--r-- | player_mcwin.cpp | 75 | ||||
| -rwxr-xr-x | player_mm | bin | 0 -> 20388 bytes | |||
| -rw-r--r-- | player_mm.cpp | 112 | ||||
| -rw-r--r-- | player_mmbias.cpp | 87 | ||||
| -rw-r--r-- | player_rand.cpp | 31 | ||||
| -rw-r--r-- | referee.cpp | 141 |
19 files changed, 1121 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..8cbd306 --- /dev/null +++ b/Makefile @@ -0,0 +1,27 @@ +CXX := g++ +CXXFLAGS := -Wall -Wextra -O2 -std=c++11 + +SOURCES := $(wildcard *.cpp) +BINARIES := $(SOURCES:.cpp=) + +space := +space += #$(space) now contains a space +comma := , + +PLAYERLIST := $(subst $(space),$(comma),$(filter player_%,$(BINARIES))) + + + +all: $(BINARIES) + +clean: + rm -f $(BINARIES) + +cleanlogs: + find playerlogs/ -type f -delete + find refereelogs/ -type f -delete + +remake: clean all + +competition: all + ./caiaio -f $(PLAYERLIST) -m manager diff --git a/_player_mcb.cpp b/_player_mcb.cpp new file mode 100644 index 0000000..8e91eb3 --- /dev/null +++ b/_player_mcb.cpp @@ -0,0 +1,73 @@ +#include <iostream> +#include <string> +#include <sys/time.h> +#include "common.h" + +using namespace std; + +const int NPLAYOUTS=300,PLAYOUTLEN=20; + +//returns +turns if `me` wins, -turns if an opponent wins +int mcplayout(Board &bd,int me){ + bool lost[NPLAYERS]; + memset(lost,0,NPLAYERS*sizeof(bool)); + int nlost=0; + int win; + int turnidx; + for(turnidx=1;turnidx<=PLAYOUTLEN;turnidx++){ //turnidx=1: one after `me` + const int onturn=(me+turnidx)%NPLAYERS; + if(lost[onturn])continue; + if(bd.ballcount(onturn)==0){ + lost[onturn]=true; + nlost++; + if(nlost==NPLAYERS)break; //? someone would have won... + continue; + } + bd.put(randommove(bd,onturn).idx(),onturn); + win=bd.checkwin(); + if(win!=-1)break; + } + return bd.ballcount(me); +} + +Move calcmove(Board &bd,int me){ + int i,j; + int score,maxscore=INT_MIN,maxat=0; + for(i=0;i<WID*HEI;i++){ + Board bd2=bd; + if(!bd2.put(i,me))continue; + score=0; + for(j=0;j<NPLAYOUTS;j++) + score+=mcplayout(bd2,me); + if(score>maxscore){ + maxscore=score; + maxat=i; + } + } + return Move(maxat%WID,maxat/WID); +} + +int main(void){ + struct timeval tv; + gettimeofday(&tv,NULL); + srand(tv.tv_sec*1000000+tv.tv_usec); + + Board bd; + char c; + Move mv; + cin>>c; cin.ignore(1024,'\n'); + int me=c-'A'; + int x,y,i; + while(true){ + c=cin.peek(); + if(c=='q'||c=='Q')break; + for(i=me+1;i%NPLAYERS!=me;i++){ + cin>>x>>y; + if(x!=-1&&y!=-1)bd.put(x,y,i%NPLAYERS); + } + cin.ignore(1024,'\n'); + mv=calcmove(bd,me); + cout<<mv.x<<' '<<mv.y<<endl; + bd.put(mv.idx(),me); + } +} diff --git a/_player_mcmaxb.cpp b/_player_mcmaxb.cpp new file mode 100644 index 0000000..4148ba5 --- /dev/null +++ b/_player_mcmaxb.cpp @@ -0,0 +1,77 @@ +#include <iostream> +#include <string> +#include <sys/time.h> +#include "common.h" + +using namespace std; + +const int NPLAYOUTS=300,PLAYOUTLEN=20; + +//returns +turns if `me` wins, -turns if an opponent wins +int mcplayout(Board &bd,int me){ + bool lost[NPLAYERS]; + memset(lost,0,NPLAYERS*sizeof(bool)); + int nlost=0; + int win; + int turnidx; + int maxballs=-1; + int bc; + for(turnidx=1;turnidx<=PLAYOUTLEN;turnidx++){ //turnidx=1: one after `me` + const int onturn=(me+turnidx)%NPLAYERS; + if(lost[onturn])continue; + bc=bd.ballcount(onturn); + if(bc==0){ + lost[onturn]=true; + nlost++; + if(nlost==NPLAYERS)break; //? someone would have won... + continue; + } + if(onturn==me)maxballs=max(maxballs,bc); + bd.put(randommove(bd,onturn).idx(),onturn); + win=bd.checkwin(); + if(win!=-1)break; + } + return maxballs; +} + +Move calcmove(Board &bd,int me){ + int i,j; + int score,maxscore=INT_MIN,maxat=0; + for(i=0;i<WID*HEI;i++){ + Board bd2=bd; + if(!bd2.put(i,me))continue; + score=0; + for(j=0;j<NPLAYOUTS;j++) + score+=mcplayout(bd2,me); + if(score>maxscore){ + maxscore=score; + maxat=i; + } + } + return Move(maxat%WID,maxat/WID); +} + +int main(void){ + struct timeval tv; + gettimeofday(&tv,NULL); + srand(tv.tv_sec*1000000+tv.tv_usec); + + Board bd; + char c; + Move mv; + cin>>c; cin.ignore(1024,'\n'); + int me=c-'A'; + int x,y,i; + while(true){ + c=cin.peek(); + if(c=='q'||c=='Q')break; + for(i=me+1;i%NPLAYERS!=me;i++){ + cin>>x>>y; + if(x!=-1&&y!=-1)bd.put(x,y,i%NPLAYERS); + } + cin.ignore(1024,'\n'); + mv=calcmove(bd,me); + cout<<mv.x<<' '<<mv.y<<endl; + bd.put(mv.idx(),me); + } +} diff --git a/common.h b/common.h new file mode 100644 index 0000000..2597c41 --- /dev/null +++ b/common.h @@ -0,0 +1,144 @@ +#include <iostream> +#include <iomanip> +#include <vector> +#include <cstring> +#include <cstdlib> +#include <cassert> + +using namespace std; + +const int NPLAYERS=2; +const int WID=7,HEI=8; + + +template <typename T> +ostream& operator<<(ostream &os,const vector<T> &v){ + const int sz=v.size(); + if(sz==0)return os; + os<<v[0]; + for(int i=1;i<sz;i++)os<<' '<<v[i]; + return os; +} + + +struct Move{ + int x,y; + + Move(void):x(-1),y(-1){} + Move(int idx):x(idx%WID),y(idx/WID){} + Move(int _x,int _y):x(_x),y(_y){} + + int idx(void){return WID*y+x;} +}; + +class Board{ + int balls[WID*HEI],colour[WID*HEI]; + int wonby=-1; //kept up-to-date by stabilise() + int nballs=0; + +public: + inline Board(void){ + memset(balls,0,WID*HEI*sizeof(int)); + memset(colour,0,WID*HEI*sizeof(int)); + } + inline Board(const Board &other):wonby(other.wonby){ + memcpy(balls,other.balls,WID*HEI*sizeof(int)); + memcpy(colour,other.colour,WID*HEI*sizeof(int)); + } + + inline int getballs(int idx){return balls[idx];} + inline int getballs(int x,int y){return getballs(WID*y+x);} + inline int getcolour(int idx){return colour[idx];} + inline int getcolour(int x,int y){return getcolour(WID*y+x);} + + inline bool put(int x,int y,int c){ + const int idx=WID*y+x; + if(balls[idx]&&colour[idx]!=c)return false; + balls[idx]++; + colour[idx]=c; + nballs++; + stabilise(); + return true; + } + inline bool put(int idx,int c){return put(idx%WID,idx/WID,c);} + + inline bool putq(int idx,int c) const{return !balls[idx]||colour[idx]==c;} + inline bool putq(int x,int y,int c) const{return putq(WID*y+x,c);} + + inline void stabilise(void){ + int nballs[WID*HEI],ncolour[WID*HEI]; //new values + bool changed; + int x,y; + do { + changed=false; + memcpy(nballs,balls,WID*HEI*sizeof(int)); + memcpy(ncolour,colour,WID*HEI*sizeof(int)); + + for(y=0;y<HEI;y++)for(x=0;x<WID;x++){ + const int idx=WID*y+x; + const int nnei=(y>0)+(x>0)+(y<HEI-1)+(x<WID-1); + if(balls[idx]>=nnei){ + const int quo=balls[idx]/nnei; + nballs[idx]-=nnei*quo; + if(y>0){nballs[idx-WID]+=quo;ncolour[idx-WID]=colour[idx];} + if(x>0){nballs[idx-1]+=quo;ncolour[idx-1]=colour[idx];} + if(y<HEI-1){nballs[idx+WID]+=quo;ncolour[idx+WID]=colour[idx];} + if(x<WID-1){nballs[idx+1]+=quo;ncolour[idx+1]=colour[idx];} + changed=true; + } + } + wonby=-1; + for(int i=0;i<WID*HEI;i++){ + if(nballs[i]==0)continue; + if(wonby==-1)wonby=ncolour[i]; + else if(wonby!=ncolour[i]){ + wonby=-1; + break; + } + } + + memcpy(balls,nballs,WID*HEI*sizeof(int)); + memcpy(colour,ncolour,WID*HEI*sizeof(int)); + } while(changed&&wonby==-1); + } + + //returns -1 for no win yet, >=0 for that colour + inline int checkwin(void) const{return wonby;} + + inline int ballcount(int c) const{ + int i,count=0; + for(i=0;i<WID*HEI;i++){ + count+=balls[i]*(colour[i]==c); + } + return count; + } + + inline int totalballcount(void) const{return nballs;} + + void print(ostream &os){ + int x,y; + for(y=0;y<HEI;y++){ + for(x=0;x<WID;x++){ + if(balls[WID*y+x]){ + os<<"\x1B[3"<<colour[WID*y+x]+1<<'m'<<setw(2)<<balls[WID*y+x]<<"\x1B[0m "; + } else os<<".. "; + } + os<<endl; + } + } +}; + +Move randommove(const Board &bd,int c){ + Move poss[WID*HEI]; + int nposs=0; + int i; + for(i=0;i<WID*HEI;i++){ + if(bd.putq(i,c)){ + poss[nposs].x=i%WID; + poss[nposs].y=i/WID; + nposs++; + } + } + if(nposs==0)return Move(); + return poss[rand()%nposs]; +} diff --git a/.gitignore b/interactor/.gitignore index 3c3629e..3c3629e 100644 --- a/.gitignore +++ b/interactor/.gitignore diff --git a/common.js b/interactor/common.js index dbc3484..dbc3484 100644 --- a/common.js +++ b/interactor/common.js diff --git a/index.html b/interactor/index.html index c861c82..c861c82 100644 --- a/index.html +++ b/interactor/index.html diff --git a/interactor.js b/interactor/interactor.js index 2d38cbb..2d38cbb 100755 --- a/interactor.js +++ b/interactor/interactor.js diff --git a/package.json b/interactor/package.json index 38f7446..38f7446 100644 --- a/package.json +++ b/interactor/package.json diff --git a/jscalc/chainreaction.js b/jscalc/chainreaction.js new file mode 100644 index 0000000..b1ffbbe --- /dev/null +++ b/jscalc/chainreaction.js @@ -0,0 +1,108 @@ +#!/usr/bin/env node +var b=[[1,2,1],[1,4,2],[1,2,1]]; + +S=JSON.stringify.bind(JSON); +Eq=function(a,b){return a.map(function(r,i){return r.map(function(v,j){return b[i][j]==v;}).reduce(function(a,b){return a&&b;});}).reduce(function(a,b){return a&&b;});}; + +printboard=function(b){ + if(!Array.isArray(b)){ + console.log(b); + return; + } + b.forEach(function(r){ + console.log(r.join(" ")); + }); +}; + +evolve=function(b){ + var w=b[0].length,h=b.length,x,y,nnei,dif; + var nb=b.map(function(r){return r.slice(0);}); + for(y=0;y<h;y++)for(x=0;x<w;x++){ + nnei=(x>0)+(x<w-1)+(y>0)+(y<h-1); + if(b[y][x]>=nnei){ + dif=~~(b[y][x]/nnei); + nb[y][x]-=dif*nnei; + if(x>0)nb[y][x-1]+=dif; + if(y>0)nb[y-1][x]+=dif; + if(x<w-1)nb[y][x+1]+=dif; + if(y<h-1)nb[y+1][x]+=dif; + } + } + return nb; +}; + +fullevolve=function(b){ + var nb,lst,i; + nb=evolve(b); + lst=[b,nb]; + while(true){ + b=nb; + nb=evolve(nb); + if(Eq(b,nb))return lst; + for(i=0;i<lst.length;i++)if(Eq(nb,lst[i]))return lst.concat([nb,Infinity]); + lst.push(nb); + } +}; + +repcheck=function(b){ + var nb,lst,i; + nb=evolve(b); + lst=[b,nb]; + while(true){ + b=nb; + nb=evolve(nb); + if(Eq(b,nb))return false; + for(i=0;i<lst.length;i++)if(Eq(nb,lst[i]))return true; + lst.push(nb); + } +}; + +convform=function(a,w,h){ + var y,res; + res=new Array(h); + for(y=0;y<h;y++)res[y]=a.slice(w*y,w*y+w); + return res; +}; + +solvewh=function(w,h){ + var maxmap,x,y,stk,i; + var res=[]; + maxmap=new Array(w*h); + maxmap[0]=maxmap[w-1]=maxmap[w*(h-1)]=maxmap[w*(h-1)+w-1]=2; + for(x=1;x<w-1;x++)maxmap[x]=maxmap[w*(h-1)+x]=3; + for(y=1;y<h-1;y++)maxmap[w*y]=maxmap[w*y+w-1]=3; + for(y=1;y<h-1;y++)for(x=1;x<w-1;x++)maxmap[w*y+x]=4; + console.log("maxmap="+S(maxmap)); + stk=new Array(w*h).fill(0); + while(true){ + //console.log("stk="+S(stk)); + for(i=0;i<w*h;i++){ + stk[i]++; + if(repcheck(convform(stk,w,h)))res.push(convform(stk,w,h)); + stk[i]--; + } + stk[stk.length-1]++; + while(stk[stk.length-1]>=maxmap[stk.length-1]){stk.pop();stk[stk.length-1]++;} + if(stk.length==0)break; + while(stk.length<w*h)stk.push(0); + } + return res; +}; + +solveallminimal=function(w,h){ + var res=solvewh(w,h); + var ressorted=res.map(function(b){return [b,b.reduce(function(a,b){return a+b.reduce(function(a,b){return a+b;});},0)];}).sort(function(a,b){return a[1]-b[1];}); + var smallest=ressorted.filter(function(r){return r[1]==ressorted[0][1];}).map(function(r){return r[0];}); + return smallest; +}; + +printboardlist=function(blist){ + blist.forEach(function(b){printboard(b);console.log();}); +}; + +printallminimal=function(w,h){printboardlist(solveallminimal(w,h));} + +printallminimal(3,3); + + +require("repl").start({prompt:"> ",useGlobal:true}).context=this; diff --git a/jscalc/chainreaction_4x4.txt b/jscalc/chainreaction_4x4.txt new file mode 100644 index 0000000..0eb5b58 --- /dev/null +++ b/jscalc/chainreaction_4x4.txt @@ -0,0 +1 @@ |