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