1 files changed, 112 insertions, 0 deletions
diff --git a/player_mm.cpp b/player_mm.cpp
new file mode 100644
index 0000000..be6858d
--- /dev/null
+++ b/player_mm.cpp
@@ -0,0 +1,112 @@
+#include <iostream>
+#include <string>
+#include <sys/time.h>
+#include "common.h"
+
+#define INFINITY (2100000000)
+
+using namespace std;
+
+const int MMDEPTH=2;
+
+void search(int *best,Board &bd,int me,int win,int depth=MMDEPTH){
+	int i;
+	if(win!=-1||depth<=0){
+		for(i=0;i<NPLAYERS;i++)best[i]=bd.ballcount(i);
+		if(win!=-1)best[win]=best[win]*11/10; //*=1.1
+		return;
+	}
+	int res[NPLAYERS];
+	for(i=0;i<WID*HEI;i++){
+		Board bd2(bd);
+		if(!bd2.put(i,me))continue;
+		memset(res,0,NPLAYERS*sizeof(int));
+		search(res,bd2,(me+1)%NPLAYERS,bd2.checkwin(),depth-1);
+		if(res[me]>best[me]){
+			memcpy(best,res,NPLAYERS*sizeof(int));
+		}
+	}
+}
+
+#if 1
+Move calcmove(Board &bd,int me){
+	int i;
+	int score,maxscore=INT_MIN,maxat=-1;
+	int res[NPLAYERS];
+	for(i=0;i<WID*HEI;i++){
+		Board bd2=bd;
+		if(!bd2.put(i,me))continue;
+		memset(res,0,NPLAYERS*sizeof(int));
+		search(res,bd2,(me+1)%NPLAYERS,bd2.checkwin());
+		score=res[me];
+		if(score>maxscore){
+			maxscore=score;
+			maxat=i;
+		}
+	}
+	return Move(maxat);
+}
+#else
+Move calcmove(Board &bd,int me){
+	if(bd.totalballcount()<2*NPLAYERS){
+		if(bd.getballs(0)==0)return 0;
+		if(bd.getballs(WID-1)==0)return WID-1;
+		if(bd.getballs(WID*(HEI-1))==0)return WID*(HEI-1);
+		if(bd.getballs(WID*HEI-1)==0)return WID*HEI-1;
+	}
+	struct Item{
+		Board bd;
+		int score,i;
+	};
+	Item items[WID*HEI];
+	int i;
+	for(i=0;i<WID*HEI;i++){
+		items[i].i=i;
+		items[i].score=INT_MIN;
+		items[i].bd=bd;
+		if(!items[i].bd.put(i,me))continue;
+		//memset(items[i].res,0,NPLAYERS*sizeof(int));
+		//search(items[i].res,items[i].bd,(me+1)%NPLAYERS,items[i].bd.checkwin());
+		items[i].score=items[i].bd.ballcount(me);
+	}
+	sort(items,items+WID*HEI,[](const Item &i1,const Item &i2) ->bool{
+		return i1.score>i2.score;
+	});
+	int res[NPLAYERS];
+	int maxscore=-1,maxat=-1;
+	for(i=0;items[i].score>=items[0].score*9/10&&i<WID*HEI/5;i++){
+		memset(res,0,NPLAYERS*sizeof(int));
+		search(res,items[i].bd,(me+1)&NPLAYERS,items[i].bd.checkwin());
+		if(res[me]>maxscore){
+			maxscore=res[me];
+			maxat=items[i].i;
+		}
+	}
+	return Move(maxat);
+}
+#endif
+
+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);
+	}
+}