1 /*
  2  * Copyright (c) 2012-2013 たかはしのんき. All rights reserved.
  3  *
  4  * History:
  5  *  0.8 2013-06-24 ブール変数 playout の名前を isPlayoutRule に変更。着手可能点をプロパティとして保持。 
  6  *  0.7 2013-06-15 JsDoc Toolkit対応。
  7  *  0.6 2013-04-26 プレイアウトのためにアタリの石で囲まれていない自分の1目の眼への着手を禁止。
  8  *  0.5 2013-04-08 プレイアウトのために自分の1目の眼への着手を禁止。
  9  *  0.4 2013-03-29 式の整理、活路の表示。
 10  *  0.3 2013-03-18 コウの処理を追加。
 11  *  0.2 2012-05-17 SixVectors オブジェクトを外せるよう変更。メソッド clear の追加。
 12  *  0.1 2012-05-15 新規作成。Java 版より移植。
 13  *
 14  * Reference:
 15  *  [1] 佐藤真史,穴田浩一,堤正義:囲碁の数理モデル化とその応用,
 16  *      第16回ゲームプログラミングワークショップ2011,Vol.2011 No.6,
 17  *      pp.100-103(2011)
 18  */
 19 
 20 /**
 21  * @fileOverview 囲碁の局面 (position) を B-W graph model で表したオブジェクトです。
 22  * このオブジェクトで扱う メソッドの引数に盤面の桁位置 col と行位置 row を 指定する
 23  * 場合は、囲碁に合わせ、col, row の順で指定します。
 24  * 行列の行 i、 列 j を指定する場合の i, j の順と逆になるので注意してください。
 25  * @author たかはしのんき
 26  * @version 0.8
 27  */
 28 var COL = 0;			// 横座標
 29 var ROW = 1;			// 縦座標
 30 var SPACE = 0;			// 空点
 31 var BLACK = 1;			// 黒石
 32 var WHITE = 2;			// 白石
 33 var P_BLACK = 0;		// 黒石（アゲハマと活路用）
 34 var P_WHITE = 1;		// 白石（アゲハマと活路用）
 35 var OPPOSITE = 3;		// 敵石計算用定数
 36 var isPlayoutRule = true;	// true ならプレイアウト用に着手可能の式を変更
 37 
 38 /**
 39  * n 路盤の局面を表すオブジェクトです。
 40  * @constructor
 41  * @this {Pos}
 42  * @param n 路数を指定します。
 43  * @since 0.1
 44  */
 45 Pos = function(n) {
 46 	this.ro = n;							// 路数
 47 	this.order = n * n;						// ベクトルの次数
 48 	this.F0 = new BMatrix(this.order, this.order);	// 隣接関係
 49 	this.initF0();
 50 	this.prisoner = new Array(2);					// アゲハマ
 51 	this.liberty = new Array(2);					// 活路の数
 52 	try {
 53 		this.v6 = new SixVectors(this);				// 6ベクトル
 54 	} catch(e) {
 55 		this.v6 = null;
 56 	}
 57 	this.clear();
 58 };
 59 
 60 Pos.prototype = {
 61 	/**
 62 	 * 隣接関係 F0 を初期化します。
 63 	 * @since 0.1
 64 	 */
 65 	initF0 : function() {
 66 		var adj = new Array(4);
 67 		adj = [				// 隣接する(adjacent)相対座標
 68 				[0, -1],
 69 				[-1, 0], [0, 0], [1, 0],
 70 				[0, 1]
 71 		];
 72 		for (var row = 1; row <= this.ro; row++)
 73 			for (var col = 1; col <= this.ro; col++)
 74 				for (var i = 0; i < adj.length; i++) {
 75 					var ar = row + adj[i][ROW];
 76 					var ac = col + adj[i][COL];
 77 					if (ar > 0 && ar <= this.ro && ac > 0 && ac <= this.ro)
 78 						this.F0.setValue(this.toIndex(col, row), this.toIndex(ac, ar), 1);
 79 				}
 80 	},
 81 
 82 	/**
 83 	 * 局面を初期化します。
 84 	 * @since 0.3
 85 	 */
 86 	clear : function() {
 87 		this.F = this.F0.clone();				// 連接関係
 88 		this.b = new BVector(this.order, 1);			// 黒の着点∨空点
 89 		this.w = this.b.clone();				// 白の着点∨空点
 90 		this.l = this.b.and(this.w);				// 空点
 91 		this.k = new BVector(this.order);			// コウ
 92 		this.ib = new BVector(this.order);			// 黒石の活路
 93 		this.iw = new BVector(this.order);			// 白石の活路
 94 		this.h = new BVector(this.order);			// アタリ
 95 		this.c = new BVector(this.order, 1);			// 着手可能点
 96 		this.calcVectors(0, 0);
 97 		if (this.v6 != null)
 98 			this.v6.calcSixVectors(this);
 99 		this.watch = null;					// 監視する BVector
100 		this.turn = BLACK;					// 手番（次の番）
101 		this.moves = 0;						// 手数
102 		this.prisoner = [0, 0];					// アゲハマ
103 		this.liberty = [0, 0];					// 活路の数
104 	},
105 
106 	/**
107 	 * 監視する BVector を設定します。
108 	 * @param watch 監視する BVector を指定します。 null なら監視を解除します。
109 	 * @since 0.1
110 	 */
111 	setWatch : function(watch) {
112 		this.watch = watch;
113 	},
114 
115 	/**
116 	 * 監視する BVector を返します。
117 	 * @return 監視する BVector を返します。なければ null を返します。
118 	 * @since 0.1
119 	 */
120 	getWatch : function() {
121 		return this.watch;
122 	},
123 
124 	/**
125 	 * 碁盤上の点 (move) をベクトル要素の添字 (index) に変換します。
126 	 * @param col 点の横方向の座標
127 	 * @param row 点の縦方向の座標
128 	 * @return 添字を返します。(1 origin)
129 	 * @since 0.1
130 	 */
131 	toIndex : function(col, row) {
132 		return (row - 1) * this.ro + col;
133 	},
134 
135 	/**
136 	 * ベクトル要素の添字 (index) を碁盤上の点 (move) に変換します。
137 	 * @param index 添字を渡します。 (1 origin)
138 	 * @return 碁盤上の点の座標をクラス Move のオブジェクトとして返します。
139 	 * @since 0.1
140 	 */
141 	toMove : function(index) {
142 		var mv = new Move();
143 		mv.row = Math.floor((index - 1) / this.ro) + 1;
144 		mv.col = (index - 1) % this.ro + 1;
145 		return mv;
146 	},
147 
148 	/**
149 	 * turn の反対のプレイヤーを返します。
150 	 * @param turn BLACK か WHITE を指定します。
151 	 * @return turn の反対のプレイヤーを返します。
152 	 * @since 0.1
153 	 */
154 	opposite : function(turn) {
155 		return OPPOSITE - turn;
156 	},
157 
158 	/**
159 	 * 着手により局面を更新します。 col と row のいずれかを ro+1 にするとパスできます。
160 	 * @param col 着手の横座標
161 	 * @param row 着手の縦座標
162 	 * @return 着手できたら true、着手できない手なら false を返します。
163 	 * @since 0.1
164 	 */
165 	move : function(col, row) {
166 		var mv = new Move(col, row);
167 		if (!mv.isPass(this.ro)) {
168 			if (!this.isMovable(col, row))
169 				return false;
170 			this.calcVectors(col, row);
171 			if (this.v6 != null)
172 				this.v6.calcSixVectors(this);
173 		} else
174 			this.calcVectors(col, row);
175 		this.turn = this.opposite(this.turn);
176 		this.moves++;
177 		return true;
178 	},
179 
180 	/**
181 	 * 与えられた交点に着手できるかどうかを調べます。
182 	 * @param col 調べる交点の桁位置
183 	 * @param row 調べる交点の行位置
184 	 * @return 着手可能なら true を返します。
185 	 * @since 0.3
186 	 */
187 	isMovable : function(col, row) {
188 		var i = this.toIndex(col, row);			// 調べる着点
189 		var ei = new BVector(this.order);
190 		ei.setValue(i, 1);
191 		if (this.c.and(ei).equals(ei))
192 			return true;
193 		return false;
194 	},
195 
196 	/**
197 	 * BWモデルに関連するベクトルと行列を計算します。計算の対象は以下のとおり。<br>
198 	 * a - 着手iによって形成される連を表すベクトル<br>
199 	 * d - 着手iによって削除される石を表すベクトル<br>
200 	 * A - 着手iによって追加される連接点を表す行列<br>
201 	 * D - 着手iによってリセットされる連接点を表す行列<br>
202 	 * b - 着手後の黒石∨空点を表すベクトル<br>
203 	 * w - 着手後の白石∨空点を表すベクトル<br>
204 	 * l - 着手後の空点を表すベクトル<br>
205 	 * F - 着手後の連接点を表す行列<br>
206 	 * k - 着手後のコウを表すベクトル<br>
207 	 * h - 着手後のアタリの石の集合を表すベクトル<br>
208 	 * c - 着手後の着手可能点を表すベクトル<br>
209 	 * ib - 着手後の黒石の活路を表すベクトル<br>
210 	 * iw - 着手後の白石の活路を表すベクトル
211 	 * @param col 着手する点iの横座標
212 	 * @param row 着手する点iの縦座標
213 	 * @since 0.3
214 	 */
215 	calcVectors : function(col, row) {
216 		if (row == 0 && col == 0)
217 			return;
218 		var z = new BVector(this.order);				// all 0 (zero)
219 		var mv = new Move(col, row);
220 		if (!mv.isPass(this.ro)) {
221 			var i = this.toIndex(col, row);				// 着点
222 			var ei = new BVector(this.order);
223 			ei.setValue(i, 1);
224 			var Fei = this.F.mul(ei);				// 着点を連接点とする交点
225 			var F0ei = this.F0.mul(ei);				// 着点の隣接点
226 			if (this.turn == BLACK) {
227 				this.a = (Fei.diff(this.w)).or(ei);		// 着点を連接点とする黒石と着点
228 				this.d = (Fei.and(this.h)).diff(this.b);	// 着点を連接点とする白石のアタリの連
229 				if (F0ei.diff(ei).and(this.b).abs() == 0 && this.d.abs() == 1)
230 					this.k = this.d;
231 				else
232 					this.k = z;
233 				this.b = this.b.or(this.d);
234 				this.w = this.w.diff(ei);
235 				this.prisoner[P_BLACK] += this.d.abs();
236 			} else if (this.turn == WHITE) {
237 				this.a = (Fei.diff(this.b)).or(ei);		// 着点を連接点とする白石と着点
238 				this.d = (Fei.and(this.h)).diff(this.w);	// 着点を連接点とする黒石のアタリの連
239 				if (F0ei.diff(ei).and(this.w).abs() == 0 && this.d.abs() == 1)
240 					this.k = this.d;
241 				else
242 					this.k = z;
243 				this.b = this.b.diff(ei);
244 				this.w = this.w.or(this.d);
245 				this.prisoner[P_WHITE] += this.d.abs();
246 			}
247 			var tF = this.F.tran();					// Fの転置（着手前）
248 			this.A = this.a.cross(tF.mul(this.a));
249 			var o = new BVector(this.order, 1);			// all 1 (one)
250 			this.D = this.F0.or((this.d.inv()).cross(o));
251 			this.F = (this.F.or(this.A)).and(this.D);
252 			this.l = this.b.and(this.w);
253 			this.ib = (tF.mul((this.w).inv())).and(this.l);		// 黒石の活路
254 			this.liberty[P_BLACK] = this.ib.abs();			// 黒石の活路の数
255 			this.iw = (tF.mul((this.b).inv())).and(this.l);		// 白石の活路
256 			this.liberty[P_WHITE] = this.iw.abs();			// 白石の活路の数
257 		} else {
258 			this.k = z;
259 		}
260 		tF = this.F.tran();						// Fの転置（着手後）
261 		for (var i = 1; i <= this.order; i++) {
262 			var ei = new BVector(this.order);
263 			ei.setValue(i, 1);
264 			var tFei = tF.mul(ei); 
265 			if ((tFei.and(this.l)).abs() == 1)
266 				this.h.setValue(i, 1);
267 			else
268 				this.h.setValue(i, 0);
269 		}
270 		if (isPlayoutRule) {
271 			var rb = new BVector(this.order);	// プレイアウトでの黒石の着手禁止点を表すベクトル
272 			var rw = new BVector(this.order);	// プレイアウトでの白石の着手禁止点を表すベクトル
273 			var z = new BVector(this.order);	// all 0 (zero)
274 			for (var i = 1; i <= this.order; i++) {
275 				var ei = new BVector(this.order);
276 				ei.setValue(i, 1);
277 				var F0ei_ei = this.F0.mul(ei).diff(ei);
278 				if (F0ei_ei.diff(this.w.inv().diff(this.h)).equals(z))
279 					rb.setValue(i, 1);
280 				if (F0ei_ei.diff(this.b.inv().diff(this.h)).equals(z))
281 					rw.setValue(i, 1);
282 			}
283 			if (this.turn == BLACK)
284 				this.c = this.F.mul(this.w.xor(this.h)).and(this.l).diff(this.k).diff(rw);
285 			else if (this.turn == WHITE)
286 				this.c = this.F.mul(this.b.xor(this.h)).and(this.l).diff(this.k).diff(rb);
287 			else
288 				return false;
289 		} else {
290 			if (this.turn == BLACK)
291 				this.c = this.F.mul(this.w.xor(this.h)).and(this.l).diff(this.k);
292 			else if (this.turn == WHITE)
293 				this.c = this.F.mul(this.b.xor(this.h)).and(this.l).diff(this.k);
294 			else
295 				return false;
296 		}
297 	},
298 
299 	/**
300 	 * 局面の座標より、石または空点を返します。エラーのときは -1 を返します。
301 	 * @param col 横座標
302 	 * @param row 縦座標
303 	 * @return SPACE, BLACK, WHITE のいずれかを返します。 
304 	 * @since 0.1
305 	 */
306 	getStone : function(col, row) {
307 		if (row <= 0 || row > this.ro || col <=0 || col > this.ro)
308 			return -1;
309 		var b1 = this.b.getValue(this.toIndex(col, row));
310 		var w1 = this.w.getValue(this.toIndex(col, row));
311 		var stone = ((b1 & w1) == 1) ? SPACE : ((b1 == 1) ? BLACK : WHITE);
312 		return stone;
313 	},
314 
315 	/* 局面の状態を文字列に変換します。
316 	 * @return 文字列を返します。
317 	 * @since 0.3
318 	 */
319 	toString : function() {
320 		var turn = ["-", "B", "W"];
321 		var str = new String();
322 		str = "#" + this.moves + "\n";
323 		str += "F'=\n" + this.F.toString();
324 		str += "b'=" + this.b.toString() + "\n";
325 		str += "w'=" + this.w.toString() + "\n";
326 		str += "l=" + this.l.toString() + "\n";
327 		str += "h=" + this.h.toString() + "\n";
328 		str += "Σ|db|=" + this.prisoner[P_BLACK] + "\n";
329 		str += "Σ|dw|=" + this.prisoner[P_WHITE] + "\n";
330 		str += "k=" + this.k.toString() + "\n";
331 		if (this.moves > 0) {
332 			str += "a=" + this.a.toString() + "\n";
333 			str += "d=" + this.d.toString() + "\n";
334 			str += "A=\n" + this.A.toString();
335 			str += "D=\n" + this.D.toString();
336 		}
337 		str += "turn:" + turn[this.turn] + "\n";
338 		return str;
339 	},
340 
341 	/* 局面の状態を TeX 文字列に変換します。
342 	 * @return TeX 文字列を返します。
343 	 * @since 0.3
344 	 */
345 	toTeX : function() {
346 		var turn = ["-", "B", "W"];
347 		var str = new String();
348 		str = "#" + this.moves + "\n";
349 		str += "$$F'=" + this.F.toTeX() +"$$\n";
350 		str += "$$\\boldsymbol{b}'=" + this.b.toTeX() + "$$\n";
351 		str += "$$\\boldsymbol{w}'=" + this.w.toTeX() + "$$\n";
352 		str += "$$\\boldsymbol{l}=" + this.l.toTeX() + "$$\n";
353 		str += "$$\\boldsymbol{h}=" + this.h.toTeX() + "$$\n";
354 		str += "$$\\sum \\left| \\boldsymbol{d}_b \\right| =" + this.prisoner[P_BLACK] + "$$\n";
355 		str += "$$\\sum \\left| \\boldsymbol{d}_w \\right| =" + this.prisoner[P_WHITE] + "$$\n";
356 		str += "$$\\boldsymbol{k}=" + this.k.toTeX() + "$$\n";
357 		if (this.moves > 0) {
358 			str += "$$\\boldsymbol{a}=" + this.a.toTeX() + "$$\n";
359 			str += "$$\\boldsymbol{d}=" + this.d.toTeX() + "$$\n";
360 			str += "$$A=" + this.A.toTeX() + "$$\n";
361 			str += "$$D=" + this.D.toTeX() + "$$\n";
362 		}
363 		str += "turn:" + turn[this.turn] + "\n";
364 		return str;
365 	},
366 
367 	/* 局面の状態を絵文字列に変換します。
368 	 * @return 絵文字列を返します。
369 	 * @since 0.1
370 	 */
371 	toPicStr : function() {
372 		var figure = ["┼", "●", "○"];
373 		var grid = ["┏", "┯", "┓", "┠", "┼", "┨", "┗", "┷", "┛"];
374 		var str = new String();
375 		str = "";
376 		for (var row = 1; row <= this.ro; row++) {
377 			for (var col = 1; col <= this.ro; col++) {
378 				var stone = this.getStone(col, row);
379 				if (stone == SPACE) {
380 					var rx = Math.ceil((row - 1) / (this.ro - 1) * 2);
381 					var cx = Math.ceil((col - 1) / (this.ro - 1) * 2);
382 					str += grid[rx * this.ro + cx];
383 				} else
384 					str += figure[stone];
385 			}
386 			str += "\n";
387 		}
388 		return str;
389 	}
390 };
391