1// garbochess.js code as of 2012-12-24
2// from the garbochess repository https://github.com/glinscott/Garbochess-JS/
3// See README.txt for more info including full credits and license.
4// Changes to the orginal code, if any, are marked with the "pgn4web" tag.
5
6"use strict";
7
8// Perf TODO:
9// Merge material updating with psq values
10// Put move scoring inline in generator
11// Remove need for fliptable in psq tables.  Access them by color
12// Optimize pawn move generation
13
14// Non-perf todo:
15// Checks in first q?
16// Pawn eval.
17// Better king evaluation
18// Better move sorting in PV nodes (especially root)
19
20var g_debug = true;
21var g_timeout = 40;
22
23function GetFen(){
24    var result = "";
25    for (var row = 0; row < 8; row++) {
26        if (row != 0)
27            result += '/';
28        var empty = 0;
29        for (var col = 0; col < 8; col++) {
30            var piece = g_board[((row + 2) << 4) + col + 4];
31            if (piece == 0) {
32                empty++;
33            }
34            else {
35                if (empty != 0)
36                    result += empty;
37                empty = 0;
38
39                var pieceChar = [" ", "p", "n", "b", "r", "q", "k", " "][(piece & 0x7)];
40                result += ((piece & colorWhite) != 0) ? pieceChar.toUpperCase() : pieceChar;
41            }
42        }
43        if (empty != 0) {
44            result += empty;
45        }
46    }
47
48    result += g_toMove == colorWhite ? " w" : " b";
49    result += " ";
50    if (g_castleRights == 0) {
51        result += "-";
52    }
53    else {
54        if ((g_castleRights & 1) != 0)
55            result += "K";
56        if ((g_castleRights & 2) != 0)
57            result += "Q";
58        if ((g_castleRights & 4) != 0)
59            result += "k";
60        if ((g_castleRights & 8) != 0)
61            result += "q";
62    }
63
64    result += " ";
65
66    if (g_enPassentSquare == -1) {
67        result += '-';
68    }
69    else {
70        result += FormatSquare(g_enPassentSquare);
71    }
72
73    return result;
74}
75
76function GetMoveSAN(move, validMoves) {
77	var from = move & 0xFF;
78	var to = (move >> 8) & 0xFF;
79
80	if (move & moveflagCastleKing) return "O-O";
81	if (move & moveflagCastleQueen) return "O-O-O";
82
83	var pieceType = g_board[from] & 0x7;
84	var result = ["", "", "N", "B", "R", "Q", "K", ""][pieceType];
85
86	var dupe = false, rowDiff = true, colDiff = true;
87	if (validMoves == null) {
88		validMoves = GenerateValidMoves();
89	}
90	for (var i = 0; i < validMoves.length; i++) {
91		var moveFrom = validMoves[i] & 0xFF;
92		var moveTo = (validMoves[i] >> 8) & 0xFF;
93		if (moveFrom != from &&
94			moveTo == to &&
95			(g_board[moveFrom] & 0x7) == pieceType) {
96			dupe = true;
97			if ((moveFrom & 0xF0) == (from & 0xF0)) {
98				rowDiff = false;
99			}
100			if ((moveFrom & 0x0F) == (from & 0x0F)) {
101				colDiff = false;
102			}
103		}
104	}
105
106	if (dupe) {
107		if (colDiff) {
108			result += FormatSquare(from).charAt(0);
109		} else if (rowDiff) {
110			result += FormatSquare(from).charAt(1);
111		} else {
112			result += FormatSquare(from);
113		}
114	} else if (pieceType == piecePawn && (g_board[to] != 0 || (move & moveflagEPC))) {
115		result += FormatSquare(from).charAt(0);
116	}
117
118	if (g_board[to] != 0 || (move & moveflagEPC)) {
119		result += "x";
120	}
121
122	result += FormatSquare(to);
123
124	if (move & moveflagPromotion) {
125		if (move & moveflagPromoteBishop) result += "=B";
126		else if (move & moveflagPromoteKnight) result += "=N";
127		else if (move & moveflagPromoteQueen) result += "=Q";
128		else result += "=R";
129	}
130
131	MakeMove(move);
132	if (g_inCheck) {
133	    result += GenerateValidMoves().length == 0 ? "#" : "+";
134	}
135	UnmakeMove(move);
136
137	return result;
138}
139
140function FormatSquare(square) {
141    var letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
142    return letters[(square & 0xF) - 4] + ((9 - (square >> 4)) + 1);
143}
144
145function FormatMove(move) {
146    var result = FormatSquare(move & 0xFF) + FormatSquare((move >> 8) & 0xFF);
147    if (move & moveflagPromotion) {
148        if (move & moveflagPromoteBishop) result += "b";
149        else if (move & moveflagPromoteKnight) result += "n";
150        else if (move & moveflagPromoteQueen) result += "q";
151        else result += "r";
152    }
153    return result;
154}
155
156function GetMoveFromString(moveString) {
157    var moves = GenerateValidMoves();
158    for (var i = 0; i < moves.length; i++) {
159        if (FormatMove(moves[i]) == moveString) {
160            return moves[i];
161        }
162    }
163    alert("busted! ->" + moveString + " fen:" + GetFen());
164}
165
166function PVFromHash(move, ply) {
167    if (ply == 0)
168        return "";
169
170    if (move == 0) {
171	if (g_inCheck) return "checkmate";
172	return "stalemate";
173    }
174
175    var pvString = " " + GetMoveSAN(move);
176    MakeMove(move);
177
178    var hashNode = g_hashTable[g_hashKeyLow & g_hashMask];
179    if (hashNode != null && hashNode.lock == g_hashKeyHigh && hashNode.bestMove != null) {
180        pvString += PVFromHash(hashNode.bestMove, ply - 1);
181    }
182
183    UnmakeMove(move);
184
185    return pvString;
186}
187
188//
189// Searching code
190//
191
192var g_startTime;
193
194var g_nodeCount;
195var g_qNodeCount;
196var g_searchValid;
197var g_globalPly = 0;
198
199function Search(finishMoveCallback, maxPly, finishPlyCallback) {
200    var lastEval;
201    var alpha = minEval;
202    var beta = maxEval;
203
204	g_globalPly++;
205    g_nodeCount = 0;
206    g_qNodeCount = 0;
207    g_searchValid = true;
208
209    var bestMove = 0;
210    var value;
211
212    g_startTime = (new Date()).getTime();
213
214    var i;
215    for (i = 1; i <= maxPly && g_searchValid; i++) {
216        var tmp = AlphaBeta(i, 0, alpha, beta);
217        if (!g_searchValid) break;
218
219        value = tmp;
220
221        if (value > alpha && value < beta) {
222            alpha = value - 500;
223            beta = value + 500;
224
225            if (alpha < minEval) alpha = minEval;
226            if (beta > maxEval) beta = maxEval;
227        } else if (alpha != minEval) {
228            alpha = minEval;
229            beta = maxEval;
230            i--;
231        }
232
233        if (g_hashTable[g_hashKeyLow & g_hashMask] != null) {
234            bestMove = g_hashTable[g_hashKeyLow & g_hashMask].bestMove;
235        }
236
237        if (finishPlyCallback != null) {
238            finishPlyCallback(bestMove, value, (new Date()).getTime() - g_startTime, i);
239        }
240    }
241
242    if (finishMoveCallback != null) {
243        finishMoveCallback(bestMove, value, (new Date()).getTime() - g_startTime, i - 1);
244    }
245}
246
247var minEval = -2000000;
248var maxEval = +2000000;
249
250var minMateBuffer = minEval + 2000;
251var maxMateBuffer = maxEval - 2000;
252
253var materialTable = [0, 800, 3350, 3450, 5000, 9750, 600000];
254
255var pawnAdj =
256[
257  0, 0, 0, 0, 0, 0, 0, 0,
258  -25, 105, 135, 270, 270, 135, 105, -25,
259  -80, 0, 30, 176, 176, 30, 0, -80,
260  -85, -5, 25, 175, 175, 25, -5, -85,
261  -90, -10, 20, 125, 125, 20, -10, -90,
262  -95, -15, 15, 75, 75, 15, -15, -95,
263  -100, -20, 10, 70, 70, 10, -20, -100,
264  0, 0, 0, 0, 0, 0, 0, 0
265];
266
267var knightAdj =
268    [-200, -100, -50, -50, -50, -50, -100, -200,
269      -100, 0, 0, 0, 0, 0, 0, -100,
270      -50, 0, 60, 60, 60, 60, 0, -50,
271      -50, 0, 30, 60, 60, 30, 0, -50,
272      -50, 0, 30, 60, 60, 30, 0, -50,
273      -50, 0, 30, 30, 30, 30, 0, -50,
274      -100, 0, 0, 0, 0, 0, 0, -100,
275      -200, -50, -25, -25, -25, -25, -50, -200
276     ];
277
278var bishopAdj =
279    [ -50,-50,-25,-10,-10,-25,-50,-50,
280      -50,-25,-10,  0,  0,-10,-25,-50,
281      -25,-10,  0, 25, 25,  0,-10,-25,
282      -10,  0, 25, 40, 40, 25,  0,-10,
283      -10,  0, 25, 40, 40, 25,  0,-10,
284      -25,-10,  0, 25, 25,  0,-10,-25,
285      -50,-25,-10,  0,  0,-10,-25,-50,
286      -50,-50,-25,-10,-10,-25,-50,-50
287     ];
288
289var rookAdj =
290    [ -60, -30, -10, 20, 20, -10, -30, -60,
291       40,  70,  90,120,120,  90,  70,  40,
292      -60, -30, -10, 20, 20, -10, -30, -60,
293      -60, -30, -10, 20, 20, -10, -30, -60,
294      -60, -30, -10, 20, 20, -10, -30, -60,
295      -60, -30, -10, 20, 20, -10, -30, -60,
296      -60, -30, -10, 20, 20, -10, -30, -60,
297      -60, -30, -10, 20, 20, -10, -30, -60
298     ];
299
300var kingAdj =
301    [  50, 150, -25, -125, -125, -25, 150, 50,
302       50, 150, -25, -125, -125, -25, 150, 50,
303       50, 150, -25, -125, -125, -25, 150, 50,
304       50, 150, -25, -125, -125, -25, 150, 50,
305       50, 150, -25, -125, -125, -25, 150, 50,
306       50, 150, -25, -125, -125, -25, 150, 50,
307       50, 150, -25, -125, -125, -25, 150, 50,
308      150, 250, 75, -25, -25, 75, 250, 150
309     ];
310
311var emptyAdj =
312    [0, 0, 0, 0, 0, 0, 0, 0,
313        0, 0, 0, 0, 0, 0, 0, 0,
314        0, 0, 0, 0, 0, 0, 0, 0,
315        0, 0, 0, 0, 0, 0, 0, 0,
316        0, 0, 0, 0, 0, 0, 0, 0,
317        0, 0, 0, 0, 0, 0, 0, 0,
318        0, 0, 0, 0, 0, 0, 0, 0,
319        0, 0, 0, 0, 0, 0, 0, 0,
320     ];
321
322var pieceSquareAdj = new Array(8);
323
324// Returns the square flipped
325var flipTable = new Array(256);
326
327function PawnEval(color) {
328    var pieceIdx = (color | 1) << 4;
329    var from = g_pieceList[pieceIdx++];
330    while (from != 0) {
331        from = g_pieceList[pieceIdx++];
332    }
333}
334
335function Mobility(color) {
336    var result = 0;
337    var from, to, mob, pieceIdx;
338    var enemy = color == 8 ? 0x10 : 0x8
339    var mobUnit = color == 8 ? g_mobUnit[0] : g_mobUnit[1];
340
341    // Knight mobility
342    mob = -3;
343    pieceIdx = (color | 2) << 4;
344    from = g_pieceList[pieceIdx++];
345    while (from != 0) {
346        mob += mobUnit[g_board[from + 31]];
347        mob += mobUnit[g_board[from + 33]];
348        mob += mobUnit[g_board[from + 14]];
349        mob += mobUnit[g_board[from - 14]];
350        mob += mobUnit[g_board[from - 31]];
351        mob += mobUnit[g_board[from - 33]];
352        mob += mobUnit[g_board[from + 18]];
353        mob += mobUnit[g_board[from - 18]];
354        from = g_pieceList[pieceIdx++];
355    }
356    result += 65 * mob;
357
358    // Bishop mobility
359    mob = -4;
360    pieceIdx = (color | 3) << 4;
361    from = g_pieceList[pieceIdx++];
362    while (from != 0) {
363        to = from - 15; while (g_board[to] == 0) { to -= 15; mob++; }
364        if (g_board[to] & enemy) {
365          mob++;
366          if (!(g_board[to] & piecePawn)) {
367            to -= 15; while (g_board[to] == 0) to -= 15;
368            mob += mobUnit[g_board[to]] << 2;
369          }
370        }
371
372        to = from - 17; while (g_board[to] == 0) { to -= 17; mob++; }
373        if (g_board[to] & enemy) {
374          mob++;
375          if (!(g_board[to] & piecePawn)) {
376            to -= 17; while (g_board[to] == 0) to -= 17;
377            mob += mobUnit[g_board[to]] << 2;
378          }
379        }
380
381        to = from + 15; while (g_board[to] == 0) { to += 15; mob++; }
382        if (g_board[to] & enemy) {
383          mob++;
384          if (!(g_board[to] & piecePawn)) {
385            to += 15; while (g_board[to] == 0) to += 15;
386            mob += mobUnit[g_board[to]] << 2;
387          }
388        }
389
390        to = from + 17; while (g_board[to] == 0) { to += 17; mob++; }
391        if (g_board[to] & enemy) {
392          mob++;
393          if (!(g_board[to] & piecePawn)) {
394            to += 17; while (g_board[to] == 0) to += 17;
395            mob += mobUnit[g_board[to]] << 2;
396          }
397        }
398
399        from = g_pieceList[pieceIdx++];
400    }
401    result += 44 * mob;
402
403    // Rook mobility
404    mob = -4;
405    pieceIdx = (color | 4) << 4;
406    from = g_pieceList[pieceIdx++];
407    while (from != 0) {
408        to = from - 1; while (g_board[to] == 0) { to--; mob++;}  if (g_board[to] & enemy) mob++;
409        to = from + 1; while (g_board[to] == 0) { to++; mob++; } if (g_board[to] & enemy) mob++;
410        to = from + 16; while (g_board[to] == 0) { to += 16; mob++; } if (g_board[to] & enemy) mob++;
411        to = from - 16; while (g_board[to] == 0) { to -= 16; mob++; } if (g_board[to] & enemy) mob++;
412        from = g_pieceList[pieceIdx++];
413    }
414    result += 25 * mob;
415
416    // Queen mobility
417    mob = -2;
418    pieceIdx = (color | 5) << 4;
419    from = g_pieceList[pieceIdx++];
420    while (from != 0) {
421        to = from - 15; while (g_board[to] == 0) { to -= 15; mob++; } if (g_board[to] & enemy) mob++;
422        to = from - 17; while (g_board[to] == 0) { to -= 17; mob++; } if (g_board[to] & enemy) mob++;
423        to = from + 15; while (g_board[to] == 0) { to += 15; mob++; } if (g_board[to] & enemy) mob++;
424        to = from + 17; while (g_board[to] == 0) { to += 17; mob++; } if (g_board[to] & enemy) mob++;
425        to = from - 1; while (g_board[to] == 0) { to--; mob++; } if (g_board[to] & enemy) mob++;
426        to = from + 1; while (g_board[to] == 0) { to++; mob++; } if (g_board[to] & enemy) mob++;
427        to = from + 16; while (g_board[to] == 0) { to += 16; mob++; } if (g_board[to] & enemy) mob++;
428        to = from - 16; while (g_board[to] == 0) { to -= 16; mob++; } if (g_board[to] & enemy) mob++;
429        from = g_pieceList[pieceIdx++];
430    }
431    result += 22 * mob;
432
433    return result;
434}
435
436function Evaluate() {
437    var curEval = g_baseEval;
438
439    var evalAdjust = 0;
440    // Black queen gone, then cancel white's penalty for king movement
441    if (g_pieceList[pieceQueen << 4] == 0)
442        evalAdjust -= pieceSquareAdj[pieceKing][g_pieceList[(colorWhite | pieceKing) << 4]];
443    // White queen gone, then cancel black's penalty for king movement
444    if (g_pieceList[(colorWhite | pieceQueen) << 4] == 0)
445        evalAdjust += pieceSquareAdj[pieceKing][flipTable[g_pieceList[pieceKing << 4]]];
446
447    // Black bishop pair
448    if (g_pieceCount[pieceBishop] >= 2)
449        evalAdjust -= 500;
450    // White bishop pair
451    if (g_pieceCount[pieceBishop | colorWhite] >= 2)
452        evalAdjust += 500;
453
454    var mobility = Mobility(8) - Mobility(0);
455
456    if (g_toMove == 0) {
457        // Black
458        curEval -= mobility;
459        curEval -= evalAdjust;
460    }
461    else {
462        curEval += mobility;
463        curEval += evalAdjust;
464    }
465
466    return curEval;
467}
468
469function ScoreMove(move){
470    var moveTo = (move >> 8) & 0xFF;
471    var captured = g_board[moveTo] & 0x7;
472    var piece = g_board[move & 0xFF];
473    var score;
474    if (captured != 0) {
475        var pieceType = piece & 0x7;
476        score = (captured << 5) - pieceType;
477    } else {
478        score = historyTable[piece & 0xF][moveTo];
479    }
480    return score;
481}
482
483function QSearch(alpha, beta, ply) {
484    g_qNodeCount++;
485
486    var realEval = g_inCheck ? (minEval + 1) : Evaluate();
487
488    if (realEval >= beta)
489        return realEval;
490
491    if (realEval > alpha)
492        alpha = realEval;
493
494    var moves = new Array();
495    var moveScores = new Array();
496    var wasInCheck = g_inCheck;
497
498    if (wasInCheck) {
499        // TODO: Fast check escape generator and fast checking moves generator
500        GenerateCaptureMoves(moves, null);
501        GenerateAllMoves(moves);
502
503        for (var i = 0; i < moves.length; i++) {
504            moveScores[i] = ScoreMove(moves[i]);
505        }
506    } else {
507        GenerateCaptureMoves(moves, null);
508
509        for (var i = 0; i < moves.length; i++) {
510            var captured = g_board[(moves[i] >> 8) & 0xFF] & 0x7;
511            var pieceType = g_board[moves[i] & 0xFF] & 0x7;
512
513            moveScores[i] = (captured << 5) - pieceType;
514        }
515    }
516
517    for (var i = 0; i < moves.length; i++) {
518        var bestMove = i;
519        for (var j = moves.length - 1; j > i; j--) {
520            if (moveScores[j] > moveScores[bestMove]) {
521                bestMove = j;
522            }
523        }
524        {
525            var tmpMove = moves[i];
526            moves[i] = moves[bestMove];
527            moves[bestMove] = tmpMove;
528
529            var tmpScore = moveScores[i];
530            moveScores[i] = moveScores[bestMove];
531            moveScores[bestMove] = tmpScore;
532        }
533
534        if (!wasInCheck && !See(moves[i])) {
535            continue;
536        }
537
538        if (!MakeMove(moves[i])) {
539            continue;
540        }
541
542        var value = -QSearch(-beta, -alpha, ply - 1);
543
544        UnmakeMove(moves[i]);
545
546        if (value > realEval) {
547            if (value >= beta)
548                return value;
549
550            if (value > alpha)
551                alpha = value;
552
553            realEval = value;
554        }
555    }
556
557    /* Disable checks...  Too slow currently
558
559    if (ply == 0 && !wasInCheck) {
560        moves = new Array();
561        GenerateAllMoves(moves);
562
563        for (var i = 0; i < moves.length; i++) {
564            moveScores[i] = ScoreMove(moves[i]);
565        }
566
567        for (var i = 0; i < moves.length; i++) {
568            var bestMove = i;
569            for (var j = moves.length - 1; j > i; j--) {
570                if (moveScores[j] > moveScores[bestMove]) {
571                    bestMove = j;
572                }
573            }
574            {
575                var tmpMove = moves[i];
576                moves[i] = moves[bestMove];
577                moves[bestMove] = tmpMove;
578
579                var tmpScore = moveScores[i];
580                moveScores[i] = moveScores[bestMove];
581                moveScores[bestMove] = tmpScore;
582            }
583
584            if (!MakeMove(moves[i])) {
585                continue;
586            }
587            var checking = g_inCheck;
588            UnmakeMove(moves[i]);
589
590            if (!checking) {
591                continue;
592            }
593
594            if (!See(moves[i])) {
595                continue;
596            }
597
598            MakeMove(moves[i]);
599
600            var value = -QSearch(-beta, -alpha, ply - 1);
601
602            UnmakeMove(moves[i]);
603
604            if (value > realEval) {
605                if (value >= beta)
606                    return value;
607
608                if (value > alpha)
609                    alpha = value;
610
611                realEval = value;
612            }
613        }
614    }
615    */
616
617    return realEval;
618}
619
620function StoreHash(value, flags, ply, move, depth) {
621	if (value >= maxMateBuffer)
622		value += depth;
623	else if (value <= minMateBuffer)
624		value -= depth;
625	g_hashTable[g_hashKeyLow & g_hashMask] = new HashEntry(g_hashKeyHigh, value, flags, ply, move);
626}
627
628function IsHashMoveValid(hashMove) {
629    var from = hashMove & 0xFF;
630    var to = (hashMove >> 8) & 0xFF;
631    var ourPiece = g_board[from];
632    var pieceType = ourPiece & 0x7;
633    if (pieceType < piecePawn || pieceType > pieceKing) return false;
634    // Can't move a piece we don't control
635    if (g_toMove != (ourPiece & 0x8))
636        return false;
637    // Can't move to a square that has something of the same color
638    if (g_board[to] != 0 && (g_toMove == (g_board[to] & 0x8)))
639        return false;
640    if (pieceType == piecePawn) {
641        if (hashMove & moveflagEPC) {
642            return false;
643        }
644
645        // Valid moves are push, capture, double push, promotions
646        var dir = to - from;
647        if ((g_toMove == colorWhite) != (dir < 0))  {
648            // Pawns have to move in the right direction
649            return false;
650        }
651
652        var row = to & 0xF0;
653        if (((row == 0x90 && !g_toMove) ||
654             (row == 0x20 && g_toMove)) != (hashMove & moveflagPromotion)) {
655            // Handle promotions
656            return false;
657        }
658
659        if (dir == -16 || dir == 16) {
660            // White/Black push
661            return g_board[to] == 0;
662        } else if (dir == -15 || dir == -17 || dir == 15 || dir == 17) {
663            // White/Black capture
664            return g_board[to] != 0;
665        } else if (dir == -32) {
666            // Double white push
667            if (row != 0x60) return false;
668            if (g_board[to] != 0) return false;
669            if (g_board[from - 16] != 0) return false;
670        } else if (dir == 32) {
671            // Double black push
672            if (row != 0x50) return false;
673            if (g_board[to] != 0) return false;
674            if (g_board[from + 16] != 0) return false;
675        } else {
676            return false;
677        }
678
679        return true;
680    } else {
681        // This validates that this piece type can actually make the attack
682        if (hashMove >> 16) return false;
683        return IsSquareAttackableFrom(to, from);
684    }
685}
686
687function IsRepDraw() {
688    var stop = g_moveCount - 1 - g_move50;
689    stop = stop < 0 ? 0 : stop;
690    for (var i = g_moveCount - 5; i >= stop; i -= 2) {
691        if (g_repMoveStack[i] == g_hashKeyLow)
692            return true;
693    }
694    return false;
695}
696
697function MovePicker(hashMove, depth, killer1, killer2) {
698    this.hashMove = hashMove;
699    this.depth = depth;
700    this.killer1 = killer1;
701    this.killer2 = killer2;
702
703    this.moves = new Array();
704    this.losingCaptures = null;
705    this.moveCount = 0;
706    this.atMove = -1;
707    this.moveScores = null;
708    this.stage = 0;
709
710    this.nextMove = function () {
711        if (++this.atMove == this.moveCount) {
712            this.stage++;
713            if (this.stage == 1) {
714                if (this.hashMove != null && IsHashMoveValid(hashMove)) {
715                    this.moves[0] = hashMove;
716                    this.moveCount = 1;
717                }
718                if (this.moveCount != 1) {
719                    this.hashMove = null;
720                    this.stage++;
721                }
722            }
723
724            if (this.stage == 2) {
725                GenerateCaptureMoves(this.moves, null);
726                this.moveCount = this.moves.length;
727                this.moveScores = new Array(this.moveCount);
728                // Move ordering
729                for (var i = this.atMove; i < this.moveCount; i++) {
730                    var captured = g_board[(this.moves[i] >> 8) & 0xFF] & 0x7;
731                    var pieceType = g_board[this.moves[i] & 0xFF] & 0x7;
732                    this.moveScores[i] = (captured << 5) - pieceType;
733                }
734                // No moves, onto next stage
735                if (this.atMove == this.moveCount) this.stage++;
736            }
737
738            if (this.stage == 3) {
739                if (IsHashMoveValid(this.killer1) &&
740                    this.killer1 != this.hashMove) {
741                    this.moves[this.moves.length] = this.killer1;
742                    this.moveCount = this.moves.length;
743                } else {
744                    this.killer1 = 0;
745                    this.stage++;
746                }
747            }
748
749            if (this.stage == 4) {
750                if (IsHashMoveValid(this.killer2) &&
751                    this.killer2 != this.hashMove) {
752                    this.moves[this.moves.length] = this.killer2;
753                    this.moveCount = this.moves.length;
754                } else {
755                    this.killer2 = 0;
756                    this.stage++;
757                }
758            }
759
760            if (this.stage == 5) {
761                GenerateAllMoves(this.moves);
762                this.moveCount = this.moves.length;
763                // Move ordering
764                for (var i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]);
765                // No moves, onto next stage
766                if (this.atMove == this.moveCount) this.stage++;
767            }
768
769            if (this.stage == 6) {
770                // Losing captures
771                if (this.losingCaptures != null) {
772                    for (var i = 0; i < this.losingCaptures.length; i++) {
773                        this.moves[this.moves.length] = this.losingCaptures[i];
774                    }
775                    for (var i = this.atMove; i < this.moveCount; i++) this.moveScores[i] = ScoreMove(this.moves[i]);
776                    this.moveCount = this.moves.length;
777                }
778                // No moves, onto next stage
779                if (this.atMove == this.moveCount) this.stage++;
780            }
781
782            if (this.stage == 7)
783                return 0;
784        }
785
786        var bestMove = this.atMove;
787        for (var j = this.atMove + 1; j < this.moveCount; j++) {
788            if (this.moveScores[j] > this.moveScores[bestMove]) {
789                bestMove = j;
790            }
791        }
792
793        if (bestMove != this.atMove) {
794            var tmpMove = this.moves[this.atMove];
795            this.moves[this.atMove] = this.moves[bestMove];
796            this.moves[bestMove] = tmpMove;
797
798            var tmpScore = this.moveScores[this.atMove];
799            this.moveScores[this.atMove] = this.moveScores[bestMove];
800            this.moveScores[bestMove] = tmpScore;
801        }
802
803        var candidateMove = this.moves[this.atMove];
804        if ((this.stage > 1 && candidateMove == this.hashMove) ||
805            (this.stage > 3 && candidateMove == this.killer1) ||
806            (this.stage > 4 && candidateMove == this.killer2)) {
807            return this.nextMove();
808        }
809
810        if (this.stage == 2 && !See(candidateMove)) {
811            if (this.losingCaptures == null) {
812                this.losingCaptures = new Array();
813            }
814            this.losingCaptures[this.losingCaptures.length] = candidateMove;
815            return this.nextMove();
816        }
817
818        return this.moves[this.atMove];
819    }
820}
821
822function AllCutNode(ply, depth, beta, allowNull) {
823    if (ply <= 0) {
824        return QSearch(beta - 1, beta, 0);
825    }
826
827    if ((g_nodeCount & 127) == 127) {
828        if ((new Date()).getTime() - g_startTime > g_timeout) {
829            // Time cutoff
830            g_searchValid = false;
831            return beta - 1;
832        }
833    }
834
835    g_nodeCount++;
836
837    if (IsRepDraw())
838        return 0;
839
840    // Mate distance pruning
841    if (minEval + depth >= beta)
842       return beta;
843
844    if (maxEval - (depth + 1) < beta)
845	return beta - 1;
846
847    var hashMove = null;
848    var hashNode = g_hashTable[g_hashKeyLow & g_hashMask];
849    if (hashNode != null && hashNode.lock == g_hashKeyHigh) {
850        hashMove = hashNode.bestMove;
851        if (hashNode.hashDepth >= ply) {
852            var hashValue = hashNode.value;
853
854            // Fixup mate scores
855            if (hashValue >= maxMateBuffer)
856		hashValue -= depth;
857            else if (hashValue <= minMateBuffer)
858                hashValue += depth;
859
860            if (hashNode.flags == hashflagExact)
861                return hashValue;
862            if (hashNode.flags == hashflagAlpha && hashValue < beta)
863                return hashValue;
864            if (hashNode.flags == hashflagBeta && hashValue >= beta)
865                return hashValue;
866        }
867    }
868
869    // TODO - positional gain?
870
871    if (!g_inCheck &&
872        allowNull &&
873        beta > minMateBuffer &&
874        beta < maxMateBuffer) {
875        // Try some razoring
876        if (hashMove == null &&
877            ply < 4) {
878            var razorMargin = 2500 + 200 * ply;
879            if (g_baseEval < beta - razorMargin) {
880                var razorBeta = beta - razorMargin;
881                var v = QSearch(razorBeta - 1, razorBeta, 0);
882                if (v < razorBeta)
883                    return v;
884            }
885        }
886
887        // TODO - static null move
888
889        // Null move
890        if (ply > 1 &&
891            g_baseEval >= beta - (ply >= 4 ? 2500 : 0) &&
892            // Disable null move if potential zugzwang (no big pieces)
893            (g_pieceCount[pieceBishop | g_toMove] != 0 ||
894             g_pieceCount[pieceKnight | g_toMove] != 0 ||
895             g_pieceCount[pieceRook | g_toMove] != 0 ||
896             g_pieceCount[pieceQueen | g_toMove] != 0)) {
897            var r = 3 + (ply >= 5 ? 1 : ply / 4);
898            if (g_baseEval - beta > 1500) r++;
899
900	        g_toMove = 8 - g_toMove;
901	        g_baseEval = -g_baseEval;
902	        g_hashKeyLow ^= g_zobristBlackLow;
903	        g_hashKeyHigh ^= g_zobristBlackHigh;
904
905	        var value = -AllCutNode(ply - r, depth + 1, -(beta - 1), false);
906
907	        g_hashKeyLow ^= g_zobristBlackLow;
908	        g_hashKeyHigh ^= g_zobristBlackHigh;
909	        g_toMove = 8 - g_toMove;
910	        g_baseEval = -g_baseEval;
911
912            if (value >= beta)
913	            return beta;
914        }
915    }
916
917    var moveMade = false;
918    var realEval = minEval - 1;
919    var inCheck = g_inCheck;
920
921    var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]);
922
923    for (;;) {
924        var currentMove = movePicker.nextMove();
925        if (currentMove == 0) {
926            break;
927        }
928
929        var plyToSearch = ply - 1;
930
931        if (!MakeMove(currentMove)) {
932            continue;
933        }
934
935        var value;
936        var doFullSearch = true;
937
938        if (g_inCheck) {
939            // Check extensions
940            plyToSearch++;
941        } else {
942            var reduced = plyToSearch - (movePicker.atMove > 14 ? 2 : 1);
943
944            // Futility pruning
945/*            if (movePicker.stage == 5 && !inCheck) {
946                if (movePicker.atMove >= (15 + (1 << (5 * ply) >> 2)) &&
947                    realEval > minMateBuffer) {
948                    UnmakeMove(currentMove);
949                    continue;
950                }
951
952                if (ply < 7) {
953                    var reducedPly = reduced <= 0 ? 0 : reduced;
954                    var futilityValue = -g_baseEval + (900 * (reducedPly + 2)) - (movePicker.atMove * 10);
955                    if (futilityValue < beta) {
956                        if (futilityValue > realEval) {
957                            realEval = futilityValue;
958                        }
959                        UnmakeMove(currentMove);
960                        continue;
961                    }
962                }
963            }*/
964
965            // Late move reductions
966            if (movePicker.stage == 5 && movePicker.atMove > 5 && ply >= 3) {
967                value = -AllCutNode(reduced, depth + 1, -(beta - 1), true);
968                doFullSearch = (value >= beta);
969            }
970        }
971
972        if (doFullSearch) {
973            value = -AllCutNode(plyToSearch, depth + 1, -(beta  - 1), true);
974        }
975
976        moveMade = true;
977
978        UnmakeMove(currentMove);
979
980        if (!g_searchValid) {
981            return beta - 1;
982        }
983
984        if (value > realEval) {
985            if (value >= beta) {
986				var histTo = (currentMove >> 8) & 0xFF;
987				if (g_board[histTo] == 0) {
988				    var histPiece = g_board[currentMove & 0xFF] & 0xF;
989				    historyTable[histPiece][histTo] += ply * ply;
990				    if (historyTable[histPiece][histTo] > 32767) {
991				        historyTable[histPiece][histTo] >>= 1;
992				    }
993
994				    if (g_killers[depth][0] != currentMove) {
995				        g_killers[depth][1] = g_killers[depth][0];
996				        g_killers[depth][0] = currentMove;
997				    }
998				}
999
1000                StoreHash(value, hashflagBeta, ply, currentMove, depth);
1001                return value;
1002            }
1003
1004            realEval = value;
1005            hashMove = currentMove;
1006        }
1007    }
1008
1009    if (!moveMade) {
1010        // If we have no valid moves it's either stalemate or checkmate
1011        if (g_inCheck)
1012            // Checkmate.
1013            return minEval + depth;
1014        else
1015            // Stalemate
1016            return 0;
1017    }
1018
1019    StoreHash(realEval, hashflagAlpha, ply, hashMove, depth);
1020
1021    return realEval;
1022}
1023
1024function AlphaBeta(ply, depth, alpha, beta) {
1025    if (ply <= 0) {
1026        return QSearch(alpha, beta, 0);
1027    }
1028
1029    g_nodeCount++;
1030
1031    if (depth > 0 && IsRepDraw())
1032        return 0;
1033
1034    // Mate distance pruning
1035    var oldAlpha = alpha;
1036    alpha = alpha < minEval + depth ? alpha : minEval + depth;
1037    beta = beta > maxEval - (depth + 1) ? beta : maxEval - (depth + 1);
1038    if (alpha >= beta)
1039       return alpha;
1040
1041    var hashMove = null;
1042    var hashFlag = hashflagAlpha;
1043    var hashNode = g_hashTable[g_hashKeyLow & g_hashMask];
1044    if (hashNode != null && hashNode.lock == g_hashKeyHigh) {
1045        hashMove = hashNode.bestMove;
1046    }
1047
1048    var inCheck = g_inCheck;
1049
1050    var moveMade = false;
1051    var realEval = minEval;
1052
1053    var movePicker = new MovePicker(hashMove, depth, g_killers[depth][0], g_killers[depth][1]);
1054
1055    for (;;) {
1056        var currentMove = movePicker.nextMove();
1057        if (currentMove == 0) {
1058            break;
1059        }
1060
1061        var plyToSearch = ply - 1;
1062
1063        if (!MakeMove(currentMove)) {
1064            continue;
1065        }
1066
1067        if (g_inCheck) {
1068            // Check extensions
1069            plyToSearch++;
1070        }
1071
1072        var value;
1073        if (moveMade) {
1074            value = -AllCutNode(plyToSearch, depth + 1, -alpha, true);
1075            if (value > alpha) {
1076                value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha);
1077            }
1078        } else {
1079            value = -AlphaBeta(plyToSearch, depth + 1, -beta, -alpha);
1080        }
1081
1082        moveMade = true;
1083
1084        UnmakeMove(currentMove);
1085
1086        if (!g_searchValid) {
1087            return alpha;
1088        }
1089
1090        if (value > realEval) {
1091            if (value >= beta) {
1092                var histTo = (currentMove >> 8) & 0xFF;
1093                if (g_board[histTo] == 0) {
1094                    var histPiece = g_board[currentMove & 0xFF] & 0xF;
1095                    historyTable[histPiece][histTo] += ply * ply;
1096                    if (historyTable[histPiece][histTo] > 32767) {
1097                        historyTable[histPiece][histTo] >>= 1;
1098                    }
1099
1100                    if (g_killers[depth][0] != currentMove) {
1101                        g_killers[depth][1] = g_killers[depth][0];
1102                        g_killers[depth][0] = currentMove;
1103                    }
1104                }
1105
1106                StoreHash(value, hashflagBeta, ply, currentMove, depth);
1107                return value;
1108            }
1109
1110            if (value > oldAlpha) {
1111                hashFlag = hashflagExact;
1112                alpha = value;
1113            }
1114
1115            realEval = value;
1116            hashMove = currentMove;
1117        }
1118    }
1119
1120    if (!moveMade) {
1121        // If we have no valid moves it's either stalemate or checkmate
1122        if (inCheck)
1123            // Checkmate.
1124            return minEval + depth;
1125        else
1126            // Stalemate
1127            return 0;
1128    }
1129
1130    StoreHash(realEval, hashFlag, ply, hashMove, depth);
1131
1132    return realEval;
1133}
1134
1135//
1136// Board code
1137//
1138
1139// This somewhat funky scheme means that a piece is indexed by it's lower 4 bits when accessing in arrays.  The fifth bit (black bit)
1140// is used to allow quick edge testing on the board.
1141var colorBlack = 0x10;
1142var colorWhite = 0x08;
1143
1144var pieceEmpty = 0x00;
1145var piecePawn = 0x01;
1146var pieceKnight = 0x02;
1147var pieceBishop = 0x03;
1148var pieceRook = 0x04;
1149var pieceQueen = 0x05;
1150var pieceKing = 0x06;
1151
1152var g_vectorDelta = new Array(256);
1153
1154var g_bishopDeltas = [-15, -17, 15, 17];
1155var g_knightDeltas = [31, 33, 14, -14, -31, -33, 18, -18];
1156var g_rookDeltas = [-1, +1, -16, +16];
1157var g_queenDeltas = [-1, +1, -15, +15, -17, +17, -16, +16];
1158
1159var g_castleRightsMask = [
11600, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
11610, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
11620, 0, 0, 0, 7,15,15,15, 3,15,15,11, 0, 0, 0, 0,
11630, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11640, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11650, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11660, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11670, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11680, 0, 0, 0,15,15,15,15,15,15,15,15, 0, 0, 0, 0,
11690, 0, 0, 0,13,15,15,15,12,15,15,14, 0, 0, 0, 0,
11700, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
11710, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
1172
1173var moveflagEPC = 0x2 << 16;
1174var moveflagCastleKing = 0x4 << 16;
1175var moveflagCastleQueen = 0x8 << 16;
1176var moveflagPromotion = 0x10 << 16;
1177var moveflagPromoteKnight = 0x20 << 16;
1178var moveflagPromoteQueen = 0x40 << 16;
1179var moveflagPromoteBishop = 0x80 << 16;
1180
1181function MT() {
1182 	var N = 624;
1183	var M = 397;
1184	var MAG01 = [0x0, 0x9908b0df];
1185
1186    this.mt = new Array(N);
1187    this.mti = N + 1;
1188
1189    this.setSeed = function()
1190	{
1191		var a = arguments;
1192		switch (a.length) {
1193		case 1:
1194			if (a[0].constructor === Number) {
1195				this.mt[0]= a[0];
1196				for (var i = 1; i < N; ++i) {
1197					var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30);
1198					this.mt[i] = ((1812433253 * ((s & 0xffff0000) >>> 16))
1199							<< 16)
1200						+ 1812433253 * (s & 0x0000ffff)
1201						+ i;
1202				}
1203				this.mti = N;
1204				return;
1205			}
1206
1207			this.setSeed(19650218);
1208
1209			var l = a[0].length;
1210			var i = 1;
1211			var j = 0;
1212
1213			for (var k = N > l ? N : l; k != 0; --k) {
1214				var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30)
1215				this.mt[i] = (this.mt[i]
1216						^ (((1664525 * ((s & 0xffff0000) >>> 16)) << 16)
1217							+ 1664525 * (s & 0x0000ffff)))
1218					+ a[0][j]
1219					+ j;
1220				if (++i >= N) {
1221					this.mt[0] = this.mt[N - 1];
1222					i = 1;
1223				}
1224				if (++j >= l) {
1225					j = 0;
1226				}
1227			}
1228
1229			for (var k = N - 1; k != 0; --k) {
1230				var s = this.mt[i - 1] ^ (this.mt[i - 1] >>> 30);
1231				this.mt[i] = (this.mt[i]
1232						^ (((1566083941 * ((s & 0xffff0000) >>> 16)) << 16)
1233							+ 1566083941 * (s & 0x0000ffff)))
1234					- i;
1235				if (++i >= N) {
1236					this.mt[0] = this.mt[N-1];
1237					i = 1;
1238				}
1239			}
1240
1241			this.mt[0] = 0x80000000;
1242			return;
1243		default:
1244			var seeds = new Array();
1245			for (var i = 0; i < a.length; ++i) {
1246				seeds.push(a[i]);
1247			}
1248			this.setSeed(seeds);
1249			return;
1250		}
1251	}
1252
1253    this.setSeed(0x1BADF00D);
1254
1255    this.next = function (bits)
1256	{
1257		if (this.mti >= N) {
1258			var x = 0;
1259
1260			for (var k = 0; k < N - M; ++k) {
1261				x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff);
1262				this.mt[k] = this.mt[k + M] ^ (x >>> 1) ^ MAG01[x & 0x1];
1263			}
1264			for (var k = N - M; k < N - 1; ++k) {
1265				x = (this.mt[k] & 0x80000000) | (this.mt[k + 1] & 0x7fffffff);
1266				this.mt[k] = this.mt[k + (M - N)] ^ (x >>> 1) ^ MAG01[x & 0x1];
1267			}
1268			x = (this.mt[N - 1] & 0x80000000) | (this.mt[0] & 0x7fffffff);
1269			this.mt[N - 1] = this.mt[M - 1] ^ (x >>> 1) ^ MAG01[x & 0x1];
1270
1271			this.mti = 0;
1272		}
1273
1274		var y = this.mt[this.mti++];
1275		y ^= y >>> 11;
1276		y ^= (y << 7) & 0x9d2c5680;
1277		y ^= (y << 15) & 0xefc60000;
1278		y ^= y >>> 18;
1279		return (y >>> (32 - bits)) & 0xFFFFFFFF;
1280	}
1281}
1282
1283// Position variables
1284var g_board = new Array(256); // Sentinel 0x80, pieces are in low 4 bits, 0x8 for color, 0x7 bits for piece type
1285var g_toMove; // side to move, 0 or 8, 0 = black, 8 = white
1286var g_castleRights; // bitmask representing castling rights, 1 = wk, 2 = wq, 4 = bk, 8 = bq
1287var g_enPassentSquare;
1288var g_baseEval;
1289var g_hashKeyLow, g_hashKeyHigh;
1290var g_inCheck;
1291
1292// Utility variables
1293var g_moveCount = 0;
1294var g_moveUndoStack = new Array();
1295
1296var g_move50 = 0;
1297var g_repMoveStack = new Array();
1298
1299var g_hashSize = 1 << 22;
1300var g_hashMask = g_hashSize - 1;
1301var g_hashTable;
1302
1303var g_killers;
1304var historyTable = new Array(32);
1305
1306var g_zobristLow;
1307var g_zobristHigh;
1308var g_zobristBlackLow;
1309var g_zobristBlackHigh;
1310
1311// Evaulation variables
1312var g_mobUnit;
1313
1314var hashflagAlpha = 1;
1315var hashflagBeta = 2;
1316var hashflagExact = 3;
1317
1318function HashEntry(lock, value, flags, hashDepth, bestMove, globalPly) {
1319    this.lock = lock;
1320    this.value = value;
1321    this.flags = flags;
1322    this.hashDepth = hashDepth;
1323    this.bestMove = bestMove;
1324}
1325
1326function MakeSquare(row, column) {
1327    return ((row + 2) << 4) | (column + 4);
1328}
1329
1330function MakeTable(table) {
1331    var result = new Array(256);
1332    for (var i = 0; i < 256; i++) {
1333        result[i] = 0;
1334    }
1335    for (var row = 0; row < 8; row++) {
1336        for (var col = 0; col < 8; col++) {
1337            result[MakeSquare(row, col)] = table[row * 8 + col];
1338        }
1339    }
1340    return result;
1341}
1342
1343function ResetGame() {
1344    g_killers = new Array(128);
1345    for (var i = 0; i < 128; i++) {
1346        g_killers[i] = [0, 0];
1347    }
1348
1349    g_hashTable = new Array(g_hashSize);
1350
1351    for (var i = 0; i < 32; i++) {
1352        historyTable[i] = new Array(256);
1353        for (var j = 0; j < 256; j++)
1354            historyTable[i][j] = 0;
1355    }
1356
1357    var mt = new MT(0x1badf00d);
1358
1359    g_zobristLow = new Array(256);
1360    g_zobristHigh = new Array(256);
1361    for (var i = 0; i < 256; i++) {
1362        g_zobristLow[i] = new Array(16);
1363        g_zobristHigh[i] = new Array(16);
1364        for (var j = 0; j < 16; j++) {
1365            g_zobristLow[i][j] = mt.next(32);
1366            g_zobristHigh[i][j] = mt.next(32);
1367        }
1368    }
1369    g_zobristBlackLow = mt.next(32);
1370    g_zobristBlackHigh = mt.next(32);
1371
1372    for (var row = 0; row < 8; row++) {
1373        for (var col = 0; col < 8; col++) {
1374            var square = MakeSquare(row, col);
1375            flipTable[square] = MakeSquare(7 - row, col);
1376        }
1377    }
1378
1379    pieceSquareAdj[piecePawn] = MakeTable(pawnAdj);
1380    pieceSquareAdj[pieceKnight] = MakeTable(knightAdj);
1381    pieceSquareAdj[pieceBishop] = MakeTable(bishopAdj);
1382    pieceSquareAdj[pieceRook] = MakeTable(rookAdj);
1383    pieceSquareAdj[pieceQueen] = MakeTable(emptyAdj);
1384    pieceSquareAdj[pieceKing] = MakeTable(kingAdj);
1385
1386    var pieceDeltas = [[], [], g_knightDeltas, g_bishopDeltas, g_rookDeltas, g_queenDeltas, g_queenDeltas];
1387
1388    for (var i = 0; i < 256; i++) {
1389        g_vectorDelta[i] = new Object();
1390        g_vectorDelta[i].delta = 0;
1391        g_vectorDelta[i].pieceMask = new Array(2);
1392        g_vectorDelta[i].pieceMask[0] = 0;
1393        g_vectorDelta[i].pieceMask[1] = 0;
1394    }
1395
1396    // Initialize the vector delta table
1397    for (var row = 0; row < 0x80; row += 0x10)
1398        for (var col = 0; col < 0x8; col++) {
1399            var square = row | col;
1400
1401            // Pawn moves
1402            var index = square - (square - 17) + 128;
1403            g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn);
1404            index = square - (square - 15) + 128;
1405            g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << piecePawn);
1406
1407            index = square - (square + 17) + 128;
1408            g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn);
1409            index = square - (square + 15) + 128;
1410            g_vectorDelta[index].pieceMask[0] |= (1 << piecePawn);
1411
1412            for (var i = pieceKnight; i <= pieceKing; i++) {
1413                for (var dir = 0; dir < pieceDeltas[i].length; dir++) {
1414                    var target = square + pieceDeltas[i][dir];
1415                    while (!(target & 0x88)) {
1416                        index = square - target + 128;
1417
1418                        g_vectorDelta[index].pieceMask[colorWhite >> 3] |= (1 << i);
1419                        g_vectorDelta[index].pieceMask[0] |= (1 << i);
1420
1421                        var flip = -1;
1422                        if (square < target)
1423                            flip = 1;
1424
1425                        if ((square & 0xF0) == (target & 0xF0)) {
1426                            // On the same row
1427                            g_vectorDelta[index].delta = flip * 1;
1428                        } else if ((square & 0x0F) == (target & 0x0F)) {
1429                            // On the same column
1430                            g_vectorDelta[index].delta = flip * 16;
1431                        } else if ((square % 15) == (target % 15)) {
1432                            g_vectorDelta[index].delta = flip * 15;
1433                        } else if ((square % 17) == (target % 17)) {
1434                            g_vectorDelta[index].delta = flip * 17;
1435                        }
1436
1437                        if (i == pieceKnight) {
1438                            g_vectorDelta[index].delta = pieceDeltas[i][dir];
1439                            break;
1440                        }
1441
1442                        if (i == pieceKing)
1443                            break;
1444
1445                        target += pieceDeltas[i][dir];
1446                    }
1447                }
1448            }
1449        }
1450
1451    InitializeEval();
1452    InitializeFromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
1453}
1454
1455function InitializeEval() {
1456    g_mobUnit = new Array(2);
1457    for (var i = 0; i < 2; i++) {
1458        g_mobUnit[i] = new Array();
1459        var enemy = i == 0 ? 0x10 : 8;
1460        var friend = i == 0 ? 8 : 0x10;
1461        g_mobUnit[i][0] = 1;
1462        g_mobUnit[i][0x80] = 0;
1463        g_mobUnit[i][enemy | piecePawn] = 1;
1464        g_mobUnit[i][enemy | pieceBishop] = 2;
1465        g_mobUnit[i][enemy | pieceKnight] = 2;
1466        g_mobUnit[i][enemy | pieceRook] = 4;
1467        g_mobUnit[i][enemy | pieceQueen] = 6;
1468        g_mobUnit[i][enemy | pieceKing] = 6;
1469        g_mobUnit[i][friend | piecePawn] = 0;
1470        g_mobUnit[i][friend | pieceBishop] = 0;
1471        g_mobUnit[i][friend | pieceKnight] = 0;
1472        g_mobUnit[i][friend | pieceRook] = 0;
1473        g_mobUnit[i][friend | pieceQueen] = 0;
1474        g_mobUnit[i][friend | pieceKing] = 0;
1475    }
1476}
1477
1478function SetHash() {
1479    var result = new Object();
1480    result.hashKeyLow = 0;
1481    result.hashKeyHigh = 0;
1482
1483    for (var i = 0; i < 256; i++) {
1484        var piece = g_board[i];
1485        if (piece & 0x18) {
1486            result.hashKeyLow ^= g_zobristLow[i][piece & 0xF]
1487            result.hashKeyHigh ^= g_zobristHigh[i][piece & 0xF]
1488        }
1489    }
1490
1491    if (!g_toMove) {
1492        result.hashKeyLow ^= g_zobristBlackLow;
1493        result.hashKeyHigh ^= g_zobristBlackHigh;
1494    }
1495
1496    return result;
1497}
1498
1499function InitializeFromFen(fen) {
1500    var chunks = fen.split(' ');
1501
1502    for (var i = 0; i < 256; i++)
1503        g_board[i] = 0x80;
1504
1505    var row = 0;
1506    var col = 0;
1507
1508    var pieces = chunks[0];
1509    for (var i = 0; i < pieces.length; i++) {
1510        var c = pieces.charAt(i);
1511
1512        if (c == '/') {
1513            row++;
1514            col = 0;
1515        }
1516        else {
1517            if (c >= '0' && c <= '9') {
1518                for (var j = 0; j < parseInt(c); j++) {
1519                    g_board[MakeSquare(row, col)] = 0;
1520                    col++;
1521                }
1522            }
1523            else {
1524                var isBlack = c >= 'a' && c <= 'z';
1525                var piece = isBlack ? colorBlack : colorWhite;
1526                if (!isBlack)
1527                    c = pieces.toLowerCase().charAt(i);
1528                switch (c) {
1529                    case 'p':
1530                        piece |= piecePawn;
1531                        break;
1532                    case 'b':
1533                        piece |= pieceBishop;
1534                        break;
1535                    case 'n':
1536                        piece |= pieceKnight;
1537                        break;
1538                    case 'r':
1539                        piece |= pieceRook;
1540                        break;
1541                    case 'q':
1542                        piece |= pieceQueen;
1543                        break;
1544                    case 'k':
1545                        piece |= pieceKing;
1546                        break;
1547                }
1548
1549                g_board[MakeSquare(row, col)] = piece;
1550                col++;
1551            }
1552        }
1553    }
1554
1555    InitializePieceList();
1556
1557    g_toMove = chunks[1].charAt(0) == 'w' ? colorWhite : 0;
1558    var them = 8 - g_toMove;
1559
1560    g_castleRights = 0;
1561    if (chunks[2].indexOf('K') != -1) {
1562        if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) ||
1563            g_board[MakeSquare(7, 7)] != (pieceRook | colorWhite)) {
1564            return 'Invalid FEN: White kingside castling not allowed';
1565        }
1566        g_castleRights |= 1;
1567    }
1568    if (chunks[2].indexOf('Q') != -1) {
1569        if (g_board[MakeSquare(7, 4)] != (pieceKing | colorWhite) ||
1570            g_board[MakeSquare(7, 0)] != (pieceRook | colorWhite)) {
1571            return 'Invalid FEN: White queenside castling not allowed';
1572        }
1573        g_castleRights |= 2;
1574    }
1575    if (chunks[2].indexOf('k') != -1) {
1576        if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) ||
1577            g_board[MakeSquare(0, 7)] != (pieceRook | colorBlack)) {
1578            return 'Invalid FEN: Black kingside castling not allowed';
1579        }
1580        g_castleRights |= 4;
1581    }
1582    if (chunks[2].indexOf('q') != -1) {
1583        if (g_board[MakeSquare(0, 4)] != (pieceKing | colorBlack) ||
1584            g_board[MakeSquare(0, 0)] != (pieceRook | colorBlack)) {
1585            return 'Invalid FEN: Black queenside castling not allowed';
1586        }
1587        g_castleRights |= 8;
1588    }
1589
1590    g_enPassentSquare = -1;
1591    if (chunks[3].indexOf('-') == -1) {
1592	var col = chunks[3].charAt(0).charCodeAt() - 'a'.charCodeAt();
1593	var row = 8 - (chunks[3].charAt(1).charCodeAt() - '0'.charCodeAt());
1594	g_enPassentSquare = MakeSquare(row, col);
1595    }
1596
1597    var hashResult = SetHash();
1598    g_hashKeyLow = hashResult.hashKeyLow;
1599    g_hashKeyHigh = hashResult.hashKeyHigh;
1600
1601    g_baseEval = 0;
1602    for (var i = 0; i < 256; i++) {
1603        if (g_board[i] & colorWhite) {
1604            g_baseEval += pieceSquareAdj[g_board[i] & 0x7][i];
1605            g_baseEval += materialTable[g_board[i] & 0x7];
1606        } else if (g_board[i] & colorBlack) {
1607            g_baseEval -= pieceSquareAdj[g_board[i] & 0x7][flipTable[i]];
1608            g_baseEval -= materialTable[g_board[i] & 0x7];
1609        }
1610    }
1611    if (!g_toMove) g_baseEval = -g_baseEval;
1612
1613    g_move50 = 0;
1614    g_inCheck = IsSquareAttackable(g_pieceList[(g_toMove | pieceKing) << 4], them);
1615
1616    // Check for king capture (invalid FEN)
1617    if (IsSquareAttackable(g_pieceList[(them | pieceKing) << 4], g_toMove)) {
1618        return 'Invalid FEN: Can capture king';
1619    }
1620
1621    // Checkmate/stalemate
1622    if (GenerateValidMoves().length == 0) {
1623        return g_inCheck ? 'Checkmate' : 'Stalemate';
1624    }
1625
1626    return '';
1627}
1628
1629var g_pieceIndex = new Array(256);
1630var g_pieceList = new Array(2 * 8 * 16);
1631var g_pieceCount = new Array(2 * 8);
1632
1633function InitializePieceList() {
1634    for (var i = 0; i < 16; i++) {
1635        g_pieceCount[i] = 0;
1636        for (var j = 0; j < 16; j++) {
1637            // 0 is used as the terminator for piece lists
1638            g_pieceList[(i << 4) | j] = 0;
1639        }
1640    }
1641
1642    for (var i = 0; i < 256; i++) {
1643        g_pieceIndex[i] = 0;
1644        if (g_board[i] & (colorWhite | colorBlack)) {
1645			var piece = g_board[i] & 0xF;
1646
1647			g_pieceList[(piece << 4) | g_pieceCount[piece]] = i;
1648			g_pieceIndex[i] = g_pieceCount[piece];
1649			g_pieceCount[piece]++;
1650        }
1651    }
1652}
1653
1654function MakeMove(move){
1655    var me = g_toMove >> 3;
1656	var otherColor = 8 - g_toMove;
1657
1658    var flags = move & 0xFF0000;
1659    var to = (move >> 8) & 0xFF;
1660    var from = move & 0xFF;
1661    var captured = g_board[to];
1662    var piece = g_board[from];
1663    var epcEnd = to;
1664
1665    if (flags & moveflagEPC) {
1666        epcEnd = me ? (to + 0x10) : (to - 0x10);
1667        captured = g_board[epcEnd];
1668        g_board[epcEnd] = pieceEmpty;
1669    }
1670
1671    g_moveUndoStack[g_moveCount] = new UndoHistory(g_enPassentSquare, g_castleRights, g_inCheck, g_baseEval, g_hashKeyLow, g_hashKeyHigh, g_move50, captured);
1672    g_moveCount++;
1673
1674    g_enPassentSquare = -1;
1675
1676    if (flags) {
1677        if (flags & moveflagCastleKing) {
1678            if (IsSquareAttackable(from + 1, otherColor) ||
1679            	IsSquareAttackable(from + 2, otherColor)) {
1680                g_moveCount--;
1681                return false;
1682            }
1683
1684            var rook = g_board[to + 1];
1685
1686            g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF];
1687            g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF];
1688            g_hashKeyLow ^= g_zobristLow[to - 1][rook & 0xF];
1689            g_hashKeyHigh ^= g_zobristHigh[to - 1][rook & 0xF];
1690
1691            g_board[to - 1] = rook;
1692            g_board[to + 1] = pieceEmpty;
1693
1694            g_baseEval -= pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to + 1] : (to + 1)];
1695            g_baseEval += pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to - 1] : (to - 1)];
1696
1697            var rookIndex = g_pieceIndex[to + 1];
1698            g_pieceIndex[to - 1] = rookIndex;
1699            g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 1;
1700        } else if (flags & moveflagCastleQueen) {
1701            if (IsSquareAttackable(from - 1, otherColor) ||
1702            	IsSquareAttackable(from - 2, otherColor)) {
1703                g_moveCount--;
1704                return false;
1705            }
1706
1707            var rook = g_board[to - 2];
1708
1709            g_hashKeyLow ^= g_zobristLow[to -2][rook & 0xF];
1710            g_hashKeyHigh ^= g_zobristHigh[to - 2][rook & 0xF];
1711            g_hashKeyLow ^= g_zobristLow[to + 1][rook & 0xF];
1712            g_hashKeyHigh ^= g_zobristHigh[to + 1][rook & 0xF];
1713
1714            g_board[to + 1] = rook;
1715            g_board[to - 2] = pieceEmpty;
1716
1717            g_baseEval -= pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to - 2] : (to - 2)];
1718            g_baseEval += pieceSquareAdj[rook & 0x7][me == 0 ? flipTable[to + 1] : (to + 1)];
1719
1720            var rookIndex = g_pieceIndex[to - 2];
1721            g_pieceIndex[to + 1] = rookIndex;
1722            g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1;
1723        }
1724    }
1725
1726    if (captured) {
1727        // Remove our piece from the piece list
1728        var capturedType = captured & 0xF;
1729        g_pieceCount[capturedType]--;
1730        var lastPieceSquare = g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]];
1731        g_pieceIndex[lastPieceSquare] = g_pieceIndex[epcEnd];
1732        g_pieceList[(capturedType << 4) | g_pieceIndex[lastPieceSquare]] = lastPieceSquare;
1733        g_pieceList[(capturedType << 4) | g_pieceCount[capturedType]] = 0;
1734
1735        g_baseEval += materialTable[captured & 0x7];
1736        g_baseEval += pieceSquareAdj[captured & 0x7][me ? flipTable[epcEnd] : epcEnd];
1737
1738        g_hashKeyLow ^= g_zobristLow[epcEnd][capturedType];
1739        g_hashKeyHigh ^= g_zobristHigh[epcEnd][capturedType];
1740        g_move50 = 0;
1741    } else if ((piece & 0x7) == piecePawn) {
1742        var diff = to - from;
1743        if (diff < 0) diff = -diff;
1744        if (diff > 16) {
1745            g_enPassentSquare = me ? (to + 0x10) : (to - 0x10);
1746        }
1747        g_move50 = 0;
1748    }
1749
1750    g_hashKeyLow ^= g_zobristLow[from][piece & 0xF];
1751    g_hashKeyHigh ^= g_zobristHigh[from][piece & 0xF];
1752    g_hashKeyLow ^= g_zobristLow[to][piece & 0xF];
1753    g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF];
1754    g_hashKeyLow ^= g_zobristBlackLow;
1755    g_hashKeyHigh ^= g_zobristBlackHigh;
1756
1757    g_castleRights &= g_castleRightsMask[from] & g_castleRightsMask[to];
1758
1759    g_baseEval -= pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[from] : from];
1760
1761    // Move our piece in the piece list
1762    g_pieceIndex[to] = g_pieceIndex[from];
1763    g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[to]] = to;
1764
1765    if (flags & moveflagPromotion) {
1766        var newPiece = piece & (~0x7);
1767        if (flags & moveflagPromoteKnight)
1768            newPiece |= pieceKnight;
1769        else if (flags & moveflagPromoteQueen)
1770            newPiece |= pieceQueen;
1771        else if (flags & moveflagPromoteBishop)
1772            newPiece |= pieceBishop;
1773        else
1774            newPiece |= pieceRook;
1775
1776        g_hashKeyLow ^= g_zobristLow[to][piece & 0xF];
1777        g_hashKeyHigh ^= g_zobristHigh[to][piece & 0xF];
1778        g_board[to] = newPiece;
1779        g_hashKeyLow ^= g_zobristLow[to][newPiece & 0xF];
1780        g_hashKeyHigh ^= g_zobristHigh[to][newPiece & 0xF];
1781
1782        g_baseEval += pieceSquareAdj[newPiece & 0x7][me == 0 ? flipTable[to] : to];
1783        g_baseEval -= materialTable[piecePawn];
1784        g_baseEval += materialTable[newPiece & 0x7];
1785
1786        var pawnType = piece & 0xF;
1787        var promoteType = newPiece & 0xF;
1788
1789        g_pieceCount[pawnType]--;
1790
1791        var lastPawnSquare = g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]];
1792        g_pieceIndex[lastPawnSquare] = g_pieceIndex[to];
1793        g_pieceList[(pawnType << 4) | g_pieceIndex[lastPawnSquare]] = lastPawnSquare;
1794        g_pieceList[(pawnType << 4) | g_pieceCount[pawnType]] = 0;
1795        g_pieceIndex[to] = g_pieceCount[promoteType];
1796        g_pieceList[(promoteType << 4) | g_pieceIndex[to]] = to;
1797        g_pieceCount[promoteType]++;
1798    } else {
1799        g_board[to] = g_board[from];
1800
1801        g_baseEval += pieceSquareAdj[piece & 0x7][me == 0 ? flipTable[to] : to];
1802    }
1803    g_board[from] = pieceEmpty;
1804
1805    g_toMove = otherColor;
1806    g_baseEval = -g_baseEval;
1807
1808    if ((piece & 0x7) == pieceKing || g_inCheck) {
1809        if (IsSquareAttackable(g_pieceList[(pieceKing | (8 - g_toMove)) << 4], otherColor)) {
1810            UnmakeMove(move);
1811            return false;
1812        }
1813    } else {
1814        var kingPos = g_pieceList[(pieceKing | (8 - g_toMove)) << 4];
1815
1816        if (ExposesCheck(from, kingPos)) {
1817            UnmakeMove(move);
1818            return false;
1819        }
1820
1821        if (epcEnd != to) {
1822            if (ExposesCheck(epcEnd, kingPos)) {
1823                UnmakeMove(move);
1824                return false;
1825            }
1826        }
1827    }
1828
1829    g_inCheck = false;
1830
1831    if (flags <= moveflagEPC) {
1832        var theirKingPos = g_pieceList[(pieceKing | g_toMove) << 4];
1833
1834        // First check if the piece we moved can attack the enemy king
1835        g_inCheck = IsSquareAttackableFrom(theirKingPos, to);
1836
1837        if (!g_inCheck) {
1838            // Now check if the square we moved from exposes check on the enemy king
1839            g_inCheck = ExposesCheck(from, theirKingPos);
1840
1841            if (!g_inCheck) {
1842                // Finally, ep. capture can cause another square to be exposed
1843                if (epcEnd != to) {
1844                    g_inCheck = ExposesCheck(epcEnd, theirKingPos);
1845                }
1846            }
1847        }
1848    }
1849    else {
1850        // Castle or promotion, slow check
1851        g_inCheck = IsSquareAttackable(g_pieceList[(pieceKing | g_toMove) << 4], 8 - g_toMove);
1852    }
1853
1854    g_repMoveStack[g_moveCount - 1] = g_hashKeyLow;
1855    g_move50++;
1856
1857    return true;
1858}
1859
1860function UnmakeMove(move){
1861    g_toMove = 8 - g_toMove;
1862    g_baseEval = -g_baseEval;
1863
1864    g_moveCount--;
1865    g_enPassentSquare = g_moveUndoStack[g_moveCount].ep;
1866    g_castleRights = g_moveUndoStack[g_moveCount].castleRights;
1867    g_inCheck = g_moveUndoStack[g_moveCount].inCheck;
1868    g_baseEval = g_moveUndoStack[g_moveCount].baseEval;
1869    g_hashKeyLow = g_moveUndoStack[g_moveCount].hashKeyLow;
1870    g_hashKeyHigh = g_moveUndoStack[g_moveCount].hashKeyHigh;
1871    g_move50 = g_moveUndoStack[g_moveCount].move50;
1872
1873    var otherColor = 8 - g_toMove;
1874    var me = g_toMove >> 3;
1875    var them = otherColor >> 3;
1876
1877    var flags = move & 0xFF0000;
1878    var captured = g_moveUndoStack[g_moveCount].captured;
1879    var to = (move >> 8) & 0xFF;
1880    var from = move & 0xFF;
1881
1882    var piece = g_board[to];
1883
1884    if (flags) {
1885        if (flags & moveflagCastleKing) {
1886            var rook = g_board[to - 1];
1887            g_board[to + 1] = rook;
1888            g_board[to - 1] = pieceEmpty;
1889
1890            var rookIndex = g_pieceIndex[to - 1];
1891            g_pieceIndex[to + 1] = rookIndex;
1892            g_pieceList[((rook & 0xF) << 4) | rookIndex] = to + 1;
1893        }
1894        else if (flags & moveflagCastleQueen) {
1895            var rook = g_board[to + 1];
1896            g_board[to - 2] = rook;
1897            g_board[to + 1] = pieceEmpty;
1898
1899            var rookIndex = g_pieceIndex[to + 1];
1900            g_pieceIndex[to - 2] = rookIndex;
1901            g_pieceList[((rook & 0xF) << 4) | rookIndex] = to - 2;
1902        }
1903    }
1904
1905    if (flags & moveflagPromotion) {
1906        piece = (g_board[to] & (~0x7)) | piecePawn;
1907        g_board[from] = piece;
1908
1909        var pawnType = g_board[from] & 0xF;
1910        var promoteType = g_board[to] & 0xF;
1911
1912        g_pieceCount[promoteType]--;
1913
1914        var lastPromoteSquare = g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]];
1915        g_pieceIndex[lastPromoteSquare] = g_pieceIndex[to];
1916        g_pieceList[(promoteType << 4) | g_pieceIndex[lastPromoteSquare]] = lastPromoteSquare;
1917        g_pieceList[(promoteType << 4) | g_pieceCount[promoteType]] = 0;
1918        g_pieceIndex[to] = g_pieceCount[pawnType];
1919        g_pieceList[(pawnType << 4) | g_pieceIndex[to]] = to;
1920        g_pieceCount[pawnType]++;
1921    }
1922    else {
1923        g_board[from] = g_board[to];
1924    }
1925
1926    var epcEnd = to;
1927    if (flags & moveflagEPC) {
1928        if (g_toMove == colorWhite)
1929            epcEnd = to + 0x10;
1930        else
1931            epcEnd = to - 0x10;
1932        g_board[to] = pieceEmpty;
1933    }
1934
1935    g_board[epcEnd] = captured;
1936
1937	// Move our piece in the piece list
1938    g_pieceIndex[from] = g_pieceIndex[to];
1939    g_pieceList[((piece & 0xF) << 4) | g_pieceIndex[from]] = from;
1940
1941    if (captured) {
1942		// Restore our piece to the piece list
1943        var captureType = captured & 0xF;
1944        g_pieceIndex[epcEnd] = g_pieceCount[captureType];
1945        g_pieceList[(captureType << 4) | g_pieceCount[captureType]] = epcEnd;
1946        g_pieceCount[captureType]++;
1947    }
1948}
1949
1950function ExposesCheck(from, kingPos){
1951    var index = kingPos - from + 128;
1952    // If a queen can't reach it, nobody can!
1953    if ((g_vectorDelta[index].pieceMask[0] & (1 << (pieceQueen))) != 0) {
1954        var delta = g_vectorDelta[index].delta;
1955        var pos = kingPos + delta;
1956        while (g_board[pos] == 0) pos += delta;
1957
1958        var piece = g_board[pos];
1959        if (((piece & (g_board[kingPos] ^ 0x18)) & 0x18) == 0)
1960            return false;
1961
1962        // Now see if the piece can actually attack the king
1963        var backwardIndex = pos - kingPos + 128;
1964        return (g_vectorDelta[backwardIndex].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) != 0;
1965    }
1966    return false;
1967}
1968
1969function IsSquareOnPieceLine(target, from) {
1970    var index = from - target + 128;
1971    var piece = g_board[from];
1972    return (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) ? true : false;
1973}
1974
1975function IsSquareAttackableFrom(target, from){
1976    var index = from - target + 128;
1977    var piece = g_board[from];
1978    if (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & (1 << (piece & 0x7))) {
1979        // Yes, this square is pseudo-attackable.  Now, check for real attack
1980		var inc = g_vectorDelta[index].delta;
1981        do {
1982			from += inc;
1983			if (from == target)
1984				return true;
1985		} while (g_board[from] == 0);
1986    }
1987
1988    return false;
1989}
1990
1991function IsSquareAttackable(target, color) {
1992	// Attackable by pawns?
1993	var inc = color ? -16 : 16;
1994	var pawn = (color ? colorWhite : colorBlack) | 1;
1995	if (g_board[target - (inc - 1)] == pawn)
1996		return true;
1997	if (g_board[target - (inc + 1)] == pawn)
1998		return true;
1999
2000	// Attackable by pieces?
2001	for (var i = 2; i <= 6; i++) {
2002        var index = (color | i) << 4;
2003        var square = g_pieceList[index];
2004		while (square != 0) {
2005			if (IsSquareAttackableFrom(target, square))
2006				return true;
2007			square = g_pieceList[++index];
2008		}
2009    }
2010    return false;
2011}
2012
2013function GenerateMove(from, to) {
2014    return from | (to << 8);
2015}
2016
2017function GenerateMove(from, to, flags){
2018    return from | (to << 8) | flags;
2019}
2020
2021function GenerateValidMoves() {
2022    var moveList = new Array();
2023    var allMoves = new Array();
2024    GenerateCaptureMoves(allMoves, null);
2025    GenerateAllMoves(allMoves);
2026
2027    for (var i = allMoves.length - 1; i >= 0; i--) {
2028        if (MakeMove(allMoves[i])) {
2029            moveList[moveList.length] = allMoves[i];
2030            UnmakeMove(allMoves[i]);
2031        }
2032    }
2033
2034    return moveList;
2035}
2036
2037function GenerateAllMoves(moveStack) {
2038    var from, to, piece, pieceIdx;
2039
2040	// Pawn quiet moves
2041    pieceIdx = (g_toMove | 1) << 4;
2042    from = g_pieceList[pieceIdx++];
2043    while (from != 0) {
2044        GeneratePawnMoves(moveStack, from);
2045        from = g_pieceList[pieceIdx++];
2046    }
2047
2048    // Knight quiet moves
2049	pieceIdx = (g_toMove | 2) << 4;
2050	from = g_pieceList[pieceIdx++];
2051	while (from != 0) {
2052		to = from + 31; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2053		to = from + 33; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2054		to = from + 14; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2055		to = from - 14; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2056		to = from - 31; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2057		to = from - 33; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2058		to = from + 18; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2059		to = from - 18; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2060		from = g_pieceList[pieceIdx++];
2061	}
2062
2063	// Bishop quiet moves
2064	pieceIdx = (g_toMove | 3) << 4;
2065	from = g_pieceList[pieceIdx++];
2066	while (from != 0) {
2067		to = from - 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; }
2068		to = from - 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; }
2069		to = from + 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; }
2070		to = from + 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; }
2071		from = g_pieceList[pieceIdx++];
2072	}
2073
2074	// Rook quiet moves
2075	pieceIdx = (g_toMove | 4) << 4;
2076	from = g_pieceList[pieceIdx++];
2077	while (from != 0) {
2078		to = from - 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; }
2079		to = from + 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; }
2080		to = from + 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; }
2081		to = from - 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; }
2082		from = g_pieceList[pieceIdx++];
2083	}
2084
2085	// Queen quiet moves
2086	pieceIdx = (g_toMove | 5) << 4;
2087	from = g_pieceList[pieceIdx++];
2088	while (from != 0) {
2089		to = from - 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 15; }
2090		to = from - 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 17; }
2091		to = from + 15; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 15; }
2092		to = from + 17; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 17; }
2093		to = from - 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to--; }
2094		to = from + 1; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to++; }
2095		to = from + 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to += 16; }
2096		to = from - 16; while (g_board[to] == 0) { moveStack[moveStack.length] = GenerateMove(from, to); to -= 16; }
2097		from = g_pieceList[pieceIdx++];
2098	}
2099
2100	// King quiet moves
2101	{
2102		pieceIdx = (g_toMove | 6) << 4;
2103		from = g_pieceList[pieceIdx];
2104		to = from - 15; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2105		to = from - 17; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2106		to = from + 15; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2107		to = from + 17; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2108		to = from - 1; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2109		to = from + 1; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2110		to = from - 16; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2111		to = from + 16; if (g_board[to] == 0) moveStack[moveStack.length] = GenerateMove(from, to);
2112
2113        if (!g_inCheck) {
2114            var castleRights = g_castleRights;
2115            if (!g_toMove)
2116                castleRights >>= 2;
2117            if (castleRights & 1) {
2118                // Kingside castle
2119                if (g_board[from + 1] == pieceEmpty && g_board[from + 2] == pieceEmpty) {
2120                    moveStack[moveStack.length] = GenerateMove(from, from + 0x02, moveflagCastleKing);
2121                }
2122            }
2123            if (castleRights & 2) {
2124                // Queenside castle
2125                if (g_board[from - 1] == pieceEmpty && g_board[from - 2] == pieceEmpty && g_board[from - 3] == pieceEmpty) {
2126                    moveStack[moveStack.length] = GenerateMove(from, from - 0x02, moveflagCastleQueen);
2127                }
2128            }
2129        }
2130	}
2131}
2132
2133function GenerateCaptureMoves(moveStack, moveScores) {
2134    var from, to, piece, pieceIdx;
2135    var inc = (g_toMove == 8) ? -16 : 16;
2136    var enemy = g_toMove == 8 ? 0x10 : 0x8;
2137
2138    // Pawn captures
2139    pieceIdx = (g_toMove | 1) << 4;
2140    from = g_pieceList[pieceIdx++];
2141    while (from != 0) {
2142        to = from + inc - 1;
2143        if (g_board[to] & enemy) {
2144            MovePawnTo(moveStack, from, to);
2145        }
2146
2147        to = from + inc + 1;
2148        if (g_board[to] & enemy) {
2149            MovePawnTo(moveStack, from, to);
2150        }
2151
2152        from = g_pieceList[pieceIdx++];
2153    }
2154
2155    if (g_enPassentSquare != -1) {
2156        var inc = (g_toMove == colorWhite) ? -16 : 16;
2157        var pawn = g_toMove | piecePawn;
2158
2159        var from = g_enPassentSquare - (inc + 1);
2160        if ((g_board[from] & 0xF) == pawn) {
2161            moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC);
2162        }
2163
2164        from = g_enPassentSquare - (inc - 1);
2165        if ((g_board[from] & 0xF) == pawn) {
2166            moveStack[moveStack.length] = GenerateMove(from, g_enPassentSquare, moveflagEPC);
2167        }
2168    }
2169
2170    // Knight captures
2171	pieceIdx = (g_toMove | 2) << 4;
2172	from = g_pieceList[pieceIdx++];
2173	while (from != 0) {
2174		to = from + 31; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2175		to = from + 33; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2176		to = from + 14; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2177		to = from - 14; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2178		to = from - 31; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2179		to = from - 33; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2180		to = from + 18; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2181		to = from - 18; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2182		from = g_pieceList[pieceIdx++];
2183	}
2184
2185	// Bishop captures
2186	pieceIdx = (g_toMove | 3) << 4;
2187	from = g_pieceList[pieceIdx++];
2188	while (from != 0) {
2189		to = from; do { to -= 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2190		to = from; do { to -= 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2191		to = from; do { to += 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2192		to = from; do { to += 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2193		from = g_pieceList[pieceIdx++];
2194	}
2195
2196	// Rook captures
2197	pieceIdx = (g_toMove | 4) << 4;
2198	from = g_pieceList[pieceIdx++];
2199	while (from != 0) {
2200		to = from; do { to--; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2201		to = from; do { to++; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2202		to = from; do { to -= 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2203		to = from; do { to += 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2204		from = g_pieceList[pieceIdx++];
2205	}
2206
2207	// Queen captures
2208	pieceIdx = (g_toMove | 5) << 4;
2209	from = g_pieceList[pieceIdx++];
2210	while (from != 0) {
2211		to = from; do { to -= 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2212		to = from; do { to -= 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2213		to = from; do { to += 15; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2214		to = from; do { to += 17; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2215		to = from; do { to--; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2216		to = from; do { to++; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2217		to = from; do { to -= 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2218		to = from; do { to += 16; } while (g_board[to] == 0); if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2219		from = g_pieceList[pieceIdx++];
2220	}
2221
2222	// King captures
2223	{
2224		pieceIdx = (g_toMove | 6) << 4;
2225		from = g_pieceList[pieceIdx];
2226		to = from - 15; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2227		to = from - 17; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2228		to = from + 15; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2229		to = from + 17; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2230		to = from - 1; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2231		to = from + 1; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2232		to = from - 16; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2233		to = from + 16; if (g_board[to] & enemy) moveStack[moveStack.length] = GenerateMove(from, to);
2234	}
2235}
2236
2237function MovePawnTo(moveStack, start, square) {
2238	var row = square & 0xF0;
2239    if ((row == 0x90) || (row == 0x20)) {
2240        moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteQueen);
2241        moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteKnight);
2242        moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion | moveflagPromoteBishop);
2243        moveStack[moveStack.length] = GenerateMove(start, square, moveflagPromotion);
2244    }
2245    else {
2246        moveStack[moveStack.length] = GenerateMove(start, square, 0);
2247    }
2248}
2249
2250function GeneratePawnMoves(moveStack, from) {
2251    var piece = g_board[from];
2252    var color = piece & colorWhite;
2253    var inc = (color == colorWhite) ? -16 : 16;
2254
2255	// Quiet pawn moves
2256	var to = from + inc;
2257	if (g_board[to] == 0) {
2258		MovePawnTo(moveStack, from, to, pieceEmpty);
2259
2260		// Check if we can do a 2 square jump
2261		if ((((from & 0xF0) == 0x30) && color != colorWhite) ||
2262		    (((from & 0xF0) == 0x80) && color == colorWhite)) {
2263			to += inc;
2264			if (g_board[to] == 0) {
2265				moveStack[moveStack.length] = GenerateMove(from, to);
2266			}
2267		}
2268	}
2269}
2270
2271function UndoHistory(ep, castleRights, inCheck, baseEval, hashKeyLow, hashKeyHigh, move50, captured) {
2272    this.ep = ep;
2273    this.castleRights = castleRights;
2274    this.inCheck = inCheck;
2275    this.baseEval = baseEval;
2276    this.hashKeyLow = hashKeyLow;
2277    this.hashKeyHigh = hashKeyHigh;
2278    this.move50 = move50;
2279    this.captured = captured;
2280}
2281
2282var g_seeValues = [0, 1, 3, 3, 5, 9, 900, 0,
2283                    0, 1, 3, 3, 5, 9, 900, 0];
2284
2285function See(move) {
2286    var from = move & 0xFF;
2287    var to = (move >> 8) & 0xFF;
2288
2289    var fromPiece = g_board[from];
2290
2291    var fromValue = g_seeValues[fromPiece & 0xF];
2292    var toValue = g_seeValues[g_board[to] & 0xF];
2293
2294    if (fromValue <= toValue) {
2295        return true;
2296    }
2297
2298    if (move >> 16) {
2299        // Castles, promotion, ep are always good
2300        return true;
2301    }
2302
2303    var us = (fromPiece & colorWhite) ? colorWhite : 0;
2304    var them = 8 - us;
2305
2306    // Pawn attacks
2307    // If any opponent pawns can capture back, this capture is probably not worthwhile (as we must be using knight or above).
2308    var inc = (fromPiece & colorWhite) ? -16 : 16; // Note: this is capture direction from to, so reversed from normal move direction
2309    if (((g_board[to + inc + 1] & 0xF) == (piecePawn | them)) ||
2310        ((g_board[to + inc - 1] & 0xF) == (piecePawn | them))) {
2311        return false;
2312    }
2313
2314    var themAttacks = new Array();
2315
2316    // Knight attacks
2317    // If any opponent knights can capture back, and the deficit we have to make up is greater than the knights value,
2318    // it's not worth it.  We can capture on this square again, and the opponent doesn't have to capture back.
2319    var captureDeficit = fromValue - toValue;
2320    SeeAddKnightAttacks(to, them, themAttacks);
2321    if (themAttacks.length != 0 && captureDeficit > g_seeValues[pieceKnight]) {
2322        return false;
2323    }
2324
2325    // Slider attacks
2326    g_board[from] = 0;
2327    for (var pieceType = pieceBishop; pieceType <= pieceQueen; pieceType++) {
2328        if (SeeAddSliderAttacks(to, them, themAttacks, pieceType)) {
2329            if (captureDeficit > g_seeValues[pieceType]) {
2330                g_board[from] = fromPiece;
2331                return false;
2332            }
2333        }
2334    }
2335
2336    // Pawn defenses
2337    // At this point, we are sure we are making a "losing" capture.  The opponent can not capture back with a
2338    // pawn.  They cannot capture back with a minor/major and stand pat either.  So, if we can capture with
2339    // a pawn, it's got to be a winning or equal capture.
2340    if (((g_board[to - inc + 1] & 0xF) == (piecePawn | us)) ||
2341        ((g_board[to - inc - 1] & 0xF) == (piecePawn | us))) {
2342        g_board[from] = fromPiece;
2343        return true;
2344    }
2345
2346    // King attacks
2347    SeeAddSliderAttacks(to, them, themAttacks, pieceKing);
2348
2349    // Our attacks
2350    var usAttacks = new Array();
2351    SeeAddKnightAttacks(to, us, usAttacks);
2352    for (var pieceType = pieceBishop; pieceType <= pieceKing; pieceType++) {
2353        SeeAddSliderAttacks(to, us, usAttacks, pieceType);
2354    }
2355
2356    g_board[from] = fromPiece;
2357
2358    // We are currently winning the amount of material of the captured piece, time to see if the opponent
2359    // can get it back somehow.  We assume the opponent can capture our current piece in this score, which
2360    // simplifies the later code considerably.
2361    var seeValue = toValue - fromValue;
2362
2363    for (; ; ) {
2364        var capturingPieceValue = 1000;
2365        var capturingPieceIndex = -1;
2366
2367        // Find the least valuable piece of the opponent that can attack the square
2368        for (var i = 0; i < themAttacks.length; i++) {
2369            if (themAttacks[i] != 0) {
2370                var pieceValue = g_seeValues[g_board[themAttacks[i]] & 0x7];
2371                if (pieceValue < capturingPieceValue) {
2372                    capturingPieceValue = pieceValue;
2373                    capturingPieceIndex = i;
2374                }
2375            }
2376        }
2377
2378        if (capturingPieceIndex == -1) {
2379            // Opponent can't capture back, we win
2380            return true;
2381        }
2382
2383        // Now, if seeValue < 0, the opponent is winning.  If even after we take their piece,
2384        // we can't bring it back to 0, then we have lost this battle.
2385        seeValue += capturingPieceValue;
2386        if (seeValue < 0) {
2387            return false;
2388        }
2389
2390        var capturingPieceSquare = themAttacks[capturingPieceIndex];
2391        themAttacks[capturingPieceIndex] = 0;
2392
2393        // Add any x-ray attackers
2394        SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks);
2395
2396        // Our turn to capture
2397        capturingPieceValue = 1000;
2398        capturingPieceIndex = -1;
2399
2400        // Find our least valuable piece that can attack the square
2401        for (var i = 0; i < usAttacks.length; i++) {
2402            if (usAttacks[i] != 0) {
2403                var pieceValue = g_seeValues[g_board[usAttacks[i]] & 0x7];
2404                if (pieceValue < capturingPieceValue) {
2405                    capturingPieceValue = pieceValue;
2406                    capturingPieceIndex = i;
2407                }
2408            }
2409        }
2410
2411        if (capturingPieceIndex == -1) {
2412            // We can't capture back, we lose :(
2413            return false;
2414        }
2415
2416        // Assume our opponent can capture us back, and if we are still winning, we can stand-pat
2417        // here, and assume we've won.
2418        seeValue -= capturingPieceValue;
2419        if (seeValue >= 0) {
2420            return true;
2421        }
2422
2423        capturingPieceSquare = usAttacks[capturingPieceIndex];
2424        usAttacks[capturingPieceIndex] = 0;
2425
2426        // Add any x-ray attackers
2427        SeeAddXrayAttack(to, capturingPieceSquare, us, usAttacks, themAttacks);
2428    }
2429}
2430
2431function SeeAddXrayAttack(target, square, us, usAttacks, themAttacks) {
2432    var index = square - target + 128;
2433    var delta = -g_vectorDelta[index].delta;
2434    if (delta == 0)
2435        return;
2436    square += delta;
2437    while (g_board[square] == 0) {
2438        square += delta;
2439    }
2440
2441    if ((g_board[square] & 0x18) && IsSquareOnPieceLine(target, square)) {
2442        if ((g_board[square] & 8) == us) {
2443            usAttacks[usAttacks.length] = square;
2444        } else {
2445            themAttacks[themAttacks.length] = square;
2446        }
2447    }
2448}
2449
2450// target = attacking square, us = color of knights to look for, attacks = array to add squares to
2451function SeeAddKnightAttacks(target, us, attacks) {
2452    var pieceIdx = (us | pieceKnight) << 4;
2453    var attackerSq = g_pieceList[pieceIdx++];
2454
2455    while (attackerSq != 0) {
2456        if (IsSquareOnPieceLine(target, attackerSq)) {
2457            attacks[attacks.length] = attackerSq;
2458        }
2459        attackerSq = g_pieceList[pieceIdx++];
2460    }
2461}
2462
2463function SeeAddSliderAttacks(target, us, attacks, pieceType) {
2464    var pieceIdx = (us | pieceType) << 4;
2465    var attackerSq = g_pieceList[pieceIdx++];
2466    var hit = false;
2467
2468    while (attackerSq != 0) {
2469        if (IsSquareAttackableFrom(target, attackerSq)) {
2470            attacks[attacks.length] = attackerSq;
2471            hit = true;
2472        }
2473        attackerSq = g_pieceList[pieceIdx++];
2474    }
2475
2476    return hit;
2477}
2478
2479function BuildPVMessage(bestMove, value, timeTaken, ply) {
2480    var totalNodes = g_nodeCount + g_qNodeCount;
2481    return "Ply:" + ply + " Score:" + value + " Nodes:" + totalNodes + " NPS:" + ((totalNodes / (timeTaken / 1000)) | 0) + " " + PVFromHash(bestMove, 15);
2482}
2483
2484//////////////////////////////////////////////////
2485// Test Harness
2486//////////////////////////////////////////////////
2487function FinishPlyCallback(bestMove, value, timeTaken, ply) {
2488    postMessage("pv " + BuildPVMessage(bestMove, value, timeTaken, ply));
2489}
2490
2491function FinishMoveLocalTesting(bestMove, value, timeTaken, ply) {
2492    if (bestMove != null) {
2493        MakeMove(bestMove);
2494        postMessage(FormatMove(bestMove));
2495    }
2496}
2497
2498var needsReset = true;
2499self.onmessage = function (e) {
2500    if (e.data == "go" || needsReset) {
2501        ResetGame();
2502        needsReset = false;
2503        if (e.data == "go") return;
2504    }
2505    if (e.data.match("^position") == "position") {
2506        ResetGame();
2507        var result = InitializeFromFen(e.data.substr(9, e.data.length - 9));
2508        if (result.length != 0) {
2509            postMessage("message " + result);
2510        }
2511    } else if (e.data.match("^search") == "search") {
2512        g_timeout = parseInt(e.data.substr(7, e.data.length - 7), 10);
2513        Search(FinishMoveLocalTesting, 99, FinishPlyCallback);
2514    } else if (e.data == "analyze") {
2515        g_timeout = 99999999999;
2516        Search(null, 99, FinishPlyCallback);
2517    } else {
2518        MakeMove(GetMoveFromString(e.data));
2519    }
2520}
2521