チームラボ天下一武道会

チームラボ主催、今回で4回目、社外の方の参加を募るようになってからは2回目のプログラミングコンテスト「天下一武道会」に参加しました。今回は遠いお茶とみかんの県からリモート参加をしました。

課題は「オセロボットをつくれ！」そうはいっても、8x8のいわゆる「リバーシ」だけでなく、ところどころ置けないマスや変形盤面があるなどエクストリームなルールです。それだけではありません。自分の石の数が相手の1/5以下になったときに、ゲーム中1回だけ発動できる「全ての石をひっくり返す」という革命的な必殺技をルールに盛り込んだ、まさにX-Gameでした。定石もよく分からない中、これを1手あたり平均2秒で処理するbotを、3時間一本勝負で作らなければなりませんでした。しかも、作ったアプリケーションはWebからAPIを叩ける形にしなければなりません。

最初はEclipseのサーバーでいいかと思いましたが、作業場所は大学の研究室。大学のゲートウェイが通過できなかったので、GAE/Jを使うことにしました。パフォーマンスがよく分からない中、処理時間はどうか、転送量はどうか…などいろいろな不安点を抱えた中開発は進んでいきました。

取り急ぎソース。

クラス本体

大会のときに使ったソースはあまりに汚いので、書き直しました。
かなりいい加減だったし、冗長だったと思います。x-y座標を間違えてパッチワーク的に直した部分もありますし、角判定は4近傍しか見ていませんでした。

package net.dolpen.www.reverse;



public class Board {
	private int[][] bd = null,cl = null;
	@SuppressWarnings("unused")
	private int max_x,max_y,out_x,out_y,c_w=100,stat = 0;
	Board(String s,int r){
		Init(s);
		this.stat=r;
		Clone();
	}
	public void Init(String sin){
		String[] l=sin.split("\\.");
		max_x=l[0].length();max_y=l.length;
		out_x=max_x+2;out_y=max_y+2;
		bd=new int[out_y][out_x];
		cl=new int[out_y][out_x];
		for(int i=0;i<max_y;i++){
			for(int j=0;j<max_x;j++){
				switch(l[i].charAt(j)){
					case '0':bd[i+1][j+1]=0;break;
					case 'P':bd[i+1][j+1]=1;break;
					case 'E':bd[i+1][j+1]=2;break;
					default:bd[i+1][j+1]=3;
				}
			}
		}
		for(int i=0;i<out_y;i++)bd[i][max_x+1]=bd[i][0]=3;
		for(int j=0;j<out_x;j++)bd[max_y+1][j]=bd[0][j]=3;
	}
	private void Clone(){for(int i=0;i<out_y;i++)for(int j=0;j<out_x;j++)cl[i][j]=bd[i][j];}
	private boolean isCorner(int y,int x){x+=1;y+=1;return (!(bd[y][x+1]!=3 && bd[y][x-1]!=3) && !(bd[y+1][x]!=3 && bd[y-1][x]!=3) && !(bd[y+1][x+1]!=3 && bd[y-1][x-1]!=3) && !(bd[y+1][x-1]!=3 && bd[y-1][x+1]!=3));}
	public String Search(){
		int t,n=1000000,x=-1,y=-1;
		for(int i=0;i<max_y;i++){
			for(int j=0;j<max_x;j++){
				if((t=Count(n,i,j))==-1)continue;
				if(isCorner(i,j))t-=c_w;
				if(n>=t){n=t;x=j;y=i;}
			}
		}
		System.out.println(n);
		return y+","+x;
	}
	private int Count(int n,int i,int j){
		if(PutAll(i,j)<=0)return -1;
		int t=0;
		for(int p=0;p<max_y;p++){
			for(int q=0;q<max_x;q++){
				if(ReSeekAll(p,q)){
					t+=((isCorner(p,q))?c_w:1);
					if(t>n){Clone();return -1;}
				}
			}
		}
		Clone();
		return t;
	}
	private boolean ReSeekAll(int y,int x){
		for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++)if(i!=0||j!=0)if(reSeek(y+1,x+1,i,j)>0)return true;
		return false;
	}
	private int PutAll(int y,int x){
		int n=0;
		for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++)if(i!=0||j!=0)n+=Put(y+1,x+1,i,j);
		if(n>0){cl[y+1][x+1]=1;n++;}
		return n;
	}
	private int Put(int y,int x,int sy,int sx){
		if(cl[y][x]!=0)return 0;
		int n=-1;do{x+=sx;y+=sy;n++;}while(cl[y][x]==2);
		if(cl[y][x]==1){while(cl[y][x]!=0){cl[y][x]=1;x-=sx;y-=sy;}return n;}
		return 0;
	}
	private int reSeek(int y,int x,int sy,int sx){
		if(cl[y][x]!=0)return 0;
		int n=-1;do{x+=sx;y+=sy;n++;}while(cl[y][x]==1);
		return (cl[y][x]==2)?n:0;
	}

}

サーブレット

オーシンプルネー

package net.dolpen.www.reverse;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.*;

@SuppressWarnings("serial")
public class ReverseServlet  extends HttpServlet {
	@Override
	protected void doGet(HttpServletRequest req, HttpServletResponse res) throws ServletException,IOException {
		Board b = new Board(req.getParameter("board"),Integer.parseInt(req.getParameter("reverse")));
		res.setContentType("text/html; charset=UTF-8");
		PrintWriter out = res.getWriter();
		out.println(b.Search());
		out.close();
	}
}

感想

「革命」については「出場者は並みいる強豪なので、大差をつけられて負けることはあっても、こっちが革命されて痛くなるような場面はない」とか想定して、かなり適当な処理をしてあります。ほぼ使わないのと同義でしょう。
あと、数手先を読むなどの深い探索では、かかった計算時間に対してパフォーマンスがそれほどでないだろうと思い「そこに打ったら相手はどれくらい多くの場所におけるか、その中で危険な角(隅)はどれくらいあるか」というのをテーマにしました。うまくはまってくれたようです。
そんなこんなで1位を獲得できたので、とてもうれしかったです。次回があれば是非参加したいと思います。最後に、チームラボの皆様、ならびに参加者の皆様、本当にお疲れ様でした。

おまけ

そんなアルゴリズムですが、サンプル2(リバースを狙う夫)に負けます。
僕もこんなことは許されない、あってはならないと思いました。次回以降はこんなことにならないように頑張りたいです。