1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include <iostream>
#include <string>
#include <climits>
#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);
}
}
|
