1 /*
  2 * Copyright (c) 2012-2014 Nonki Takahashi. All rights reserved.
  3 *
  4 * History:
  5 *  0.9 2014-01-29 Changed to return true when calcVectors is successful.  Changed Move object interface.
  6 *  0.8 2013-06-24 Changed the name of boolean variable playout to isPlayoutRule.  Kept possible move as property.
  7 *  0.7 2013-06-15 Supported JsDoc Toolkit.
  8 *  0.6 2013-04-26 Inhibited moving to an self eye which is not enclosed by atari stones for playout.
  9 *  0.5 2013-04-08 Inhibited moving to an self eye.
 10 *  0.4 2013-03-29 Simplified expressions.  Displayed liberty.
 11 *  0.3 2013-03-18 Supported ko.
 12 *  0.2 2012-05-17 Changed for disabling SixVectors.  Added method clear.
 13 *  0.1 2012-05-15 Created.  Ported from Java version.
 14 *
 15 * Reference:
 16 *  [1] Satou, M., Anada, K. and Tsutsumi, M.: A Mathematical Model for the Game of Go
 17 *      and its Application, The 16th Game Programming Workshop 2011, Vol.2011 No.6,
 18 *      pp.100-103, 2011.
 19 */
 20 
 21 /**
 22  * @fileOverview Go game position object using B-W graph model.
 23  * For arguments in this object, the sequence column then row is used as well as
 24  * Go game does so.
 25  * Be careful that the matrix row i and column j are opposite sequence i, j.
 26  * @author Nonki Takahashi
 27  * @version 0.9
 28  */
 29 // column co-ordinate
 30 var COL = 0;
 31 // row co-ordinate
 32 var ROW = 1;
 33 // space
 34 var SPACE = 0;
 35 // black stone
 36 var BLACK = 1;
 37 // white stone
 38 var WHITE = 2;
 39 // black stone (for prisoner, liberty, score, player name)
 40 var P_BLACK = 0;
 41 // white stone (for prisoner, liberty, score, player name)
 42 var P_WHITE = 1;
 43 // constant to obtain enemy
 44 var OPPOSITE = 3;
 45 // true if changing possible move expression for playout
 46 var isPlayoutRule = true;
 47 
 48 /**
 49  * Object to represent n ro Go board position.
 50  * @class Represents Go board position
 51  * @this {Pos}
 52  * @param {Number} n number of lines
 53  * @property {Number} ro number of lines
 54  * @property {Number} order vector order
 55  * @property {BMatrix} F0 adjacency relationship
 56  * @property {Number[]} prisoner prisoner
 57  * @property {Number[]} liberty number of liberty
 58  * @property {SixVectors} v6 6 vector（option）
 59  * @property {BMatrix} F unit adjacency relationship
 60  * @property {BVector} b black stone or space
 61  * @property {BVector} w white stone or space
 62  * @property {BVector} l space
 63  * @property {BVector} h atari
 64  * @property {BVector} k ko
 65  * @property {BVector} ib black stone liberty
 66  * @property {BVector} iw white stone liberty
 67  * @property {BVector} c movable points
 68  * @property {BVector} watch watched vector
 69  * @property {Number} turn turn (BLACK or WHITE)
 70  * @property {Number} moves number of moves
 71  * @since 0.1
 72  */
 73 Pos = function(n) {
 74     // number of lines
 75     this.ro = n;
 76     // order of vector
 77     this.order = n * n;
 78     // adjacency relationship
 79     this.F0 = new BMatrix(this.order, this.order);
 80     this.initF0();
 81     // prisoner
 82     this.prisoner = new Array(2);
 83     // number of liberty
 84     this.liberty = new Array(2);
 85     try {
 86         // 6 vector
 87         this.v6 = new SixVectors(this);
 88     } catch(e) {
 89         this.v6 = null;
 90     }
 91     this.clear();
 92 };
 93 
 94 Pos.prototype = {
 95     /**
 96      * Initialize adjacency relationship F0
 97      * @since 0.1
 98      */
 99     initF0 : function() {
100         var adj = new Array(4);
101         adj = [
102         // adjacent relative co-ordinate
103         // @formatter:off		  
104 			         [0, -1],
105 			[-1, 0], [0, 0], [1, 0],
106 			         [0, 1]
107         // @formatter:on
108         ];
109         for (var row = 1; row <= this.ro; row++)
110             for (var col = 1; col <= this.ro; col++)
111                 for (var i = 0; i < adj.length; i++) {
112                     var ar = row + adj[i][ROW];
113                     var ac = col + adj[i][COL];
114                     if (ar > 0 && ar <= this.ro && ac > 0 && ac <= this.ro)
115                         this.F0.setValue(this.toIndex(col, row), this.toIndex(ac, ar), 1);
116                 }
117     },
118 
119     /**
120      * Initialize game position
121      * @since 0.3
122      */
123     clear : function() {
124         // unit adjacency relationship
125         this.F = this.F0.clone();
126         // black stone or space
127         this.b = new BVector(this.order, 1);
128         // white stone or space
129         this.w = this.b.clone();
130         // space
131         this.l = this.b.and(this.w);
132         // atari
133         this.h = new BVector(this.order);
134         // ko
135         this.k = new BVector(this.order);
136         // black stone liberty
137         this.ib = new BVector(this.order);
138         // white stone liberty
139         this.iw = new BVector(this.order);
140         // movable points
141         this.c = new BVector(this.order, 1);
142         if (this.v6 != null)
143             this.v6.calcSixVectors(this);
144         // watched BVector
145         this.watch = null;
146         // next turn
147         this.turn = BLACK;
148         // number of moves
149         this.moves = 0;
150         // prisoners (captured stones)
151         this.prisoner = [0, 0];
152         // number of liberty
153         this.liberty = [0, 0];
154     },
155 
156     /**
157      * Set watching BVector
158      * @param {BVector} watch watching BVector. If null then stop watching.
159      * @since 0.1
160      */
161     setWatch : function(watch) {
162         this.watch = watch;
163     },
164 
165     /**
166      * Get watching BVector
167      * @return {BVector} watching BVector or null if not exist
168      * @since 0.1
169      */
170     getWatch : function() {
171         return this.watch;
172     },
173 
174     /**
175      * Convert move position to index for vector element
176      * @param {number} col column of move
177      * @param {Number} row row of move
178      * @return {Number} index (1 origin)
179      * @since 0.1
180      */
181     toIndex : function(col, row) {
182         return (row - 1) * this.ro + col;
183     },
184 
185     /**
186      * Convert index for vector element to move position on board
187      * @param {Number} index (1 origin)
188      * @return {Move} position on board as Move object
189      * @since 0.1
190      */
191     toMove : function(index) {
192         var row = Math.floor((index - 1) / this.ro) + 1;
193         var col = (index - 1) % this.ro + 1;
194         var mv = new Move(col, row);
195         return mv;
196     },
197 
198     /**
199      * Return opposite of turn
200      * @param {Number} turn (BLACK or WHITE)
201      * @return {Number} opposite of turn
202      * @since 0.1
203      */
204     opposite : function(turn) {
205         return OPPOSITE - turn;
206     },
207 
208     /**
209      * Update game position by move.  ro+1 for either col or row means pass.
210      * @example
211      * p.move(new Move(col, row));
212      * @param {Move} mv position to move (to place stone)
213      * @return {Boolean} true for leagal move, false for illeagal move
214      * @since 0.9
215      */
216     move : function(mv) {
217         if (!mv.isPass) {
218             if (!this.isMovable(mv.col, mv.row))
219                 return false;
220             this.calcVectors(mv);
221             if (this.v6 != null)
222                 this.v6.calcSixVectors(this);
223         } else
224             this.calcVectors(mv);
225         this.turn = this.opposite(this.turn);
226         this.moves++;
227         return true;
228     },
229 
230     /**
231      * Check if the point is movable
232      * @param {Number} col column co-ordinate for the point to check
233      * @param {Number} row row co-ordinate for the point to check
234      * @return {Boolean} true if movable
235      * @since 0.3
236      */
237     isMovable : function(col, row) {
238         // the point to check
239         var i = this.toIndex(col, row);
240         var ei = new BVector(this.order);
241         ei.setValue(i, 1);
242         if (this.c.and(ei).equals(ei))
243             return true;
244         return false;
245     },
246 
247     /**
248      * Calculate vectors and matrices for B-W Graph Model.  Targets are:<br>
249      * a - added stone vector by move i<br>
250      * d - deleted unit vector by move i<br>
251      * A - added unit adjacent points matrix by move i<br>
252      * D - reset unit adjacent points matrix by move i<br>
253      * b - black stone or space vector after move<br>
254      * w - white stone or space vector after move<br>
255      * l - space vector after move<br>
256      * F - unit adjacent points matrix after move<br>
257      * k - ko vectoer after move<br>
258      * h - atari stones vector after move<br>
259      * c - movable points after move<br>
260      * ib - black stone liberties after move<br>
261      * iw - white stone liberties after move
262      * @param {Move} mv move i
263      * @return {Boolean} false if error
264      * @since 0.9
265      */
266     calcVectors : function(mv) {
267         // all 0 (zero)
268         var z = new BVector(this.order);
269         if (!mv.isPass) {
270             // move point
271             var i = this.toIndex(mv.col, mv.row);
272             var ei = new BVector(this.order);
273             ei.setValue(i, 1);
274             // points that move point i is unit-adjointed by
275             var Fei = this.F.mul(ei);
276             // points that move point i adjoints to
277             var F0ei = this.F0.mul(ei);
278             if (this.turn == BLACK) {
279                 // black stones that move point is unit-adjonted by and move point
280                 this.a = (Fei.diff(this.w)).or(ei);
281                 // white atari stones that move point is unit-adjointed by
282                 this.d = (Fei.and(this.h)).diff(this.b);
283                 if (F0ei.diff(ei).and(this.b).abs() == 0 && this.d.abs() == 1)
284                     this.k = this.d;
285                 else
286                     this.k = z;
287                 this.b = this.b.or(this.d);
288                 this.w = this.w.diff(ei);
289                 this.prisoner[P_BLACK] += this.d.abs();
290             } else if (this.turn == WHITE) {
291                 // white stones that move point is unit-adjointed by and move point
292                 this.a = (Fei.diff(this.b)).or(ei);
293                 // black atari stones that move point is unit-adjointed by
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             // transposed F (before move)
304             var tF = this.F.tran();
305             this.A = this.a.cross(tF.mul(this.a));
306             // all 1 (one)
307             var o = new BVector(this.order, 1);
308             this.D = this.F0.or((this.d.inv()).cross(o));
309             this.F = (this.F.or(this.A)).and(this.D);
310             this.l = this.b.and(this.w);
311             // black stone liberties
312             this.ib = (tF.mul((this.w).inv())).and(this.l);
313             // number of black stone libeties
314             this.liberty[P_BLACK] = this.ib.abs();
315             // white stone libaties
316             this.iw = (tF.mul((this.b).inv())).and(this.l);
317             // number of white stone libeties
318             this.liberty[P_WHITE] = this.iw.abs();
319         } else {
320             this.k = z;
321         }
322         // transposed F (after move)
323         tF = this.F.tran();
324         for (var i = 1; i <= this.order; i++) {
325             var ei = new BVector(this.order);
326             ei.setValue(i, 1);
327             var tFei = tF.mul(ei);
328             if ((tFei.and(this.l)).abs() == 1)
329                 this.h.setValue(i, 1);
330             else
331                 this.h.setValue(i, 0);
332         }
333         if (isPlayoutRule) {
334             // restricted black move points for playout
335             var rb = new BVector(this.order);
336             // restricted white move points for playout
337             var rw = new BVector(this.order);
338             // all 0 (zero)
339             var z = new BVector(this.order);
340             for (var i = 1; i <= this.order; i++) {
341                 var ei = new BVector(this.order);
342                 ei.setValue(i, 1);
343                 var F0ei_ei = this.F0.mul(ei).diff(ei);
344                 if (F0ei_ei.diff(this.w.inv().diff(this.h)).equals(z))
345                     rb.setValue(i, 1);
346                 if (F0ei_ei.diff(this.b.inv().diff(this.h)).equals(z))
347                     rw.setValue(i, 1);
348             }
349             if (this.turn == BLACK)
350                 this.c = this.F.mul(this.w.xor(this.h)).and(this.l).diff(this.k).diff(rw);
351             else if (this.turn == WHITE)
352                 this.c = this.F.mul(this.b.xor(this.h)).and(this.l).diff(this.k).diff(rb);
353             else
354                 return false;
355         } else {
356             if (this.turn == BLACK)
357                 this.c = this.F.mul(this.w.xor(this.h)).and(this.l).diff(this.k);
358             else if (this.turn == WHITE)
359                 this.c = this.F.mul(this.b.xor(this.h)).and(this.l).diff(this.k);
360             else
361                 return false;
362         }
363         return true;
364     },
365 
366     /**
367      * Returns stone color or space from board intersection co-ordinate
368      * @param {Number} col column co-ordinate
369      * @param {Number} row row co-ordinate
370      * @return {Number} SPACE, BLACK or WHITE (or -1 if error)
371      * @since 0.1
372      */
373     getStone : function(col, row) {
374         if (row <= 0 || row > this.ro || col <= 0 || col > this.ro)
375             return -1;
376         var b1 = this.b.getValue(this.toIndex(col, row));
377         var w1 = this.w.getValue(this.toIndex(col, row));
378         var stone = ((b1 & w1) == 1) ? SPACE : ((b1 == 1) ? BLACK : WHITE);
379         return stone;
380     },
381 
382     /**
383      * Convert board position state to string
384      * @return {String} board position
385      * @since 0.3
386      */
387     toString : function() {
388         var turn = ["-", "B", "W"];
389         var str = new String();
390         str = "#" + this.moves + "\n";
391         str += "F'=\n" + this.F.toString();
392         str += "b'=" + this.b.toString() + "\n";
393         str += "w'=" + this.w.toString() + "\n";
394         str += "l=" + this.l.toString() + "\n";
395         str += "h=" + this.h.toString() + "\n";
396         str += "Σ|db|=" + this.prisoner[P_BLACK] + "\n";
397         str += "Σ|dw|=" + this.prisoner[P_WHITE] + "\n";
398         str += "k=" + this.k.toString() + "\n";
399         if (this.moves > 0) {
400             str += "a=" + this.a.toString() + "\n";
401             str += "d=" + this.d.toString() + "\n";
402             str += "A=\n" + this.A.toString();
403             str += "D=\n" + this.D.toString();
404         }
405         str += "turn:" + turn[this.turn] + "\n";
406         return str;
407     },
408 
409     /**
410      * Convert board position state to TeX string
411      * @return {String} TeX string which represents board position
412      * @since 0.3
413      */
414     toTeX : function() {
415         var turn = ["-", "B", "W"];
416         var str = new String();
417         str = "#" + this.moves + "\n";
418         str += "$$F'=" + this.F.toTeX() + "$$\n";
419         str += "$$\\boldsymbol{b}'=" + this.b.toTeX() + "$$\n";
420         str += "$$\\boldsymbol{w}'=" + this.w.toTeX() + "$$\n";
421         str += "$$\\boldsymbol{l}=" + this.l.toTeX() + "$$\n";
422         str += "$$\\boldsymbol{h}=" + this.h.toTeX() + "$$\n";
423         str += "$$\\sum \\left| \\boldsymbol{d}_b \\right| =" + this.prisoner[P_BLACK] + "$$\n";
424         str += "$$\\sum \\left| \\boldsymbol{d}_w \\right| =" + this.prisoner[P_WHITE] + "$$\n";
425         str += "$$\\boldsymbol{k}=" + this.k.toTeX() + "$$\n";
426         if (this.moves > 0) {
427             str += "$$\\boldsymbol{a}=" + this.a.toTeX() + "$$\n";
428             str += "$$\\boldsymbol{d}=" + this.d.toTeX() + "$$\n";
429             str += "$$A=" + this.A.toTeX() + "$$\n";
430             str += "$$D=" + this.D.toTeX() + "$$\n";
431         }
432         str += "turn:" + turn[this.turn] + "\n";
433         return str;
434     },
435 
436     /**
437      * Convert board position state to picture string
438      * @return {String} picture string of board position
439      * @since 0.1
440      */
441     toPicStr : function() {
442         var figure = ["┼", "●", "○"];
443         var grid = ["┏", "┯", "┓", "┠", "┼", "┨", "┗", "┷", "┛"];
444         var str = new String();
445         str = "";
446         for (var row = 1; row <= this.ro; row++) {
447             for (var col = 1; col <= this.ro; col++) {
448                 var stone = this.getStone(col, row);
449                 if (stone == SPACE) {
450                     var rx = Math.ceil((row - 1) / (this.ro - 1) * 2);
451                     var cx = Math.ceil((col - 1) / (this.ro - 1) * 2);
452                     str += grid[rx * this.ro + cx];
453                 } else
454                     str += figure[stone];
455             }
456             str += "\n";
457         }
458         return str;
459     }
460 };
461