1<?php
2/* vim: set expandtab tabstop=4 shiftwidth=4: */
3// +----------------------------------------------------------------------+
4// | PHP version 4                                                        |
5// +----------------------------------------------------------------------+
6// | Copyright (c) 2003 The PHP Group                                     |
7// +----------------------------------------------------------------------+
8// | This source file is subject to version 3.0 of the PHP license,       |
9// | that is bundled with this package in the file LICENSE, and is        |
10// | available through the world-wide-web at                              |
11// | http://www.php.net/license/3_0.txt.                                  |
12// | If you did not receive a copy of the PHP license and are unable to   |
13// | obtain it through the world-wide-web, please send a note to          |
14// | license@php.net so we can mail you a copy immediately.               |
15// +----------------------------------------------------------------------+
16// | Authors: Gregory Beaver <cellog@php.net>                             |
17// +----------------------------------------------------------------------+
18//
19// $Id: Chess.php,v 1.21 2007/06/17 05:46:43 cellog Exp $
20/**
21 * The Games_Chess Package
22 *
23 * The logic of handling a chessboard and parsing standard
24 * FEN (Forsyth-Edwards Notation) for describing a position as well as SAN
25 * (Standard Algebraic Notation) for describing individual moves is handled.  This
26 * class can be used as a backend driver for playing chess, or for validating
27 * and/or creating PGN files using the File_ChessPGN package.
28rn *
29 * Although this package is alpha, it is fully unit-tested.  The code works, but
30 * the API is fluid, and may change dramatically as it is put into use and better
31 * ways are found to use it.  When the API stabilizes, the stability will increase.
32 *
33 * To learn how to play chess, there are many sites online, try searching for
34 * "chess."  To play online, I use the Internet Chess Club at
35 * {@link http://www.chessclub.com} as CelloJi, look me up sometime :).  Don't
36 * worry, I'm not very good.
37 * @todo implement special class Games_Chess_Chess960 for Fischer Random Chess
38 * @todo implement special class Games_Chess_Wild23 for ICC Wild variant 23
39 * @author Gregory Beaver <cellog@php.net>
40 * @copyright 2003
41 * @license http://www.php.net/license/3_0.txt PHP License 3.0
42 * @version @VER@
43 */
44/**#@+
45 * Move constants
46 */
47/**
48 * Castling move (O-O or O-O-O)
49 */
50define('GAMES_CHESS_CASTLE', 1);
51/**
52 * Pawn move (e4, e8=Q, exd5)
53 */
54define('GAMES_CHESS_PAWNMOVE', 2);
55/**
56 * Piece move (Qa4, Nfe6, Bxe5, Re2xe6)
57 */
58define('GAMES_CHESS_PIECEMOVE', 3);
59/**
60 * Special move type used in Wild23 like P@a4 (place a pawn at a4)
61 */
62define('GAMES_CHESS_PIECEPLACEMENT', 4);
63/**#@-*/
64
65/**#@+
66 * Error Constants
67 */
68/**
69 * Invalid Standard Algebraic Notation was used
70 */
71define('GAMES_CHESS_ERROR_INVALID_SAN', 1);
72/**
73 * The number of space-separated fields in a FEN passed to {@internal
74 * {@link _parseFen()} through }} {@link resetGame()} was incorrect, should be 6
75 */
76define('GAMES_CHESS_ERROR_FEN_COUNT', 2);
77/**
78 * A FEN containing multiple spaces in a row was parsed {@internal by
79 * {@link _parseFen()}}}
80 */
81define('GAMES_CHESS_ERROR_EMPTY_FEN', 3);
82/**
83 * Too many pieces were passed in for the chessboard to fit them in a FEN
84 * {@internal passed to {@link _parseFen()}}}
85 */
86define('GAMES_CHESS_ERROR_FEN_TOOMUCH', 4);
87/**
88 * The indicator of which side to move in a FEN was neither "w" nor "b"
89 */
90define('GAMES_CHESS_ERROR_FEN_TOMOVEWRONG', 5);
91/**
92 * The list of castling indicators was too long (longest is KQkq) of a FEN
93 */
94define('GAMES_CHESS_ERROR_FEN_CASTLETOOLONG', 6);
95/**
96 * Something other than K, Q, k or q was in the castling indicators of a FEN
97 */
98define('GAMES_CHESS_ERROR_FEN_CASTLEWRONG', 7);
99/**
100 * The en passant square was neither "-" nor an algebraic square in a FEN
101 */
102define('GAMES_CHESS_ERROR_FEN_INVALID_EP', 8);
103/**
104 * The ply count (number of half-moves) was not a number in a FEN
105 */
106define('GAMES_CHESS_ERROR_FEN_INVALID_PLY', 9);
107/**
108 * The move count (pairs of white/black moves) was not a number in a FEN
109 */
110define('GAMES_CHESS_ERROR_FEN_INVALID_MOVENUMBER', 10);
111/**
112 * An illegal move was attempted, the king is in check
113 */
114define('GAMES_CHESS_ERROR_IN_CHECK', 11);
115/**
116 * Can't castle kingside, either king or rook has moved
117 */
118define('GAMES_CHESS_ERROR_CANT_CK', 12);
119/**
120 * Can't castle kingside, pieces are in the way on the f and/or g files
121 */
122define('GAMES_CHESS_ERROR_CK_PIECES_IN_WAY', 13);
123/**
124 * Can't castle kingside, either king or rook has moved
125 */
126define('GAMES_CHESS_ERROR_CANT_CQ', 14);
127/**
128 * Can't castle queenside, pieces are in the way on the d, c and/or b files
129 */
130define('GAMES_CHESS_ERROR_CQ_PIECES_IN_WAY', 15);
131/**
132 * Castling would place the king in check, which is illegal
133 */
134define('GAMES_CHESS_ERROR_CASTLE_WOULD_CHECK', 16);
135/**
136 * Performing a requested move would place the king in check
137 */
138define('GAMES_CHESS_ERROR_MOVE_WOULD_CHECK', 17);
139/**
140 * The requested move does not remove a check on the king
141 */
142define('GAMES_CHESS_ERROR_STILL_IN_CHECK', 18);
143/**
144 * An attempt (however misguided) was made to capture one's own piece, illegal
145 */
146define('GAMES_CHESS_ERROR_CANT_CAPTURE_OWN', 19);
147/**
148 * An attempt was made to capture a piece on a square that does not contain a piece
149 */
150define('GAMES_CHESS_ERROR_NO_PIECE', 20);
151/**
152 * A attempt to move an opponent's piece was made, illegal
153 */
154define('GAMES_CHESS_ERROR_WRONG_COLOR', 21);
155/**
156 * A request was made to move a piece from one square to another, but it can't
157 * move to that square legally
158 */
159define('GAMES_CHESS_ERROR_CANT_MOVE_THAT_WAY', 22);
160/**
161 * An attempt was made to add a piece to the chessboard, but there are too many
162 * pieces of that type already on the chessboard
163 */
164define('GAMES_CHESS_ERROR_MULTIPIECE', 23);
165/**
166 * An attempt was made to add a piece to the chessboard through the parsing of
167 * a FEN, but there are too many pieces of that type already on the chessboard
168 */
169define('GAMES_CHESS_ERROR_FEN_MULTIPIECE', 24);
170/**
171 * An attempt was made to add a piece to the chessboard on top of an existing piece
172 */
173define('GAMES_CHESS_ERROR_DUPESQUARE', 25);
174/**
175 * An invalid piece indicator was used in a FEN
176 */
177define('GAMES_CHESS_ERROR_FEN_INVALIDPIECE', 26);
178/**
179 * Not enough piece data was passed into the FEN to explain every square on the board
180 */
181define('GAMES_CHESS_ERROR_FEN_TOOLITTLE', 27);
182/**
183 * Something other than "W" or "B" was passed to a method needing a color
184 */
185define('GAMES_CHESS_ERROR_INVALID_COLOR', 28);
186/**
187 * Something that isn't SAN ([a-h][1-8]) was passed to a function requiring a
188 * square location
189 */
190define('GAMES_CHESS_ERROR_INVALID_SQUARE', 29);
191/**
192 * Something other than "P", "Q", "R", "B", "N" or "K" was passed to a method
193 * needing a piece type
194 */
195define('GAMES_CHESS_ERROR_INVALID_PIECE', 30);
196/**
197 * Something other than "Q", "R", "B", or "N" was passed to a method
198 * needing a piece type for pawn promotion
199 */
200define('GAMES_CHESS_ERROR_INVALID_PROMOTE', 31);
201/**
202 * SAN was passed in that is too ambiguous - multiple pieces could execute
203 * the move, and no disambiguation (like Naf3 or Bf3xe4) was used
204 */
205define('GAMES_CHESS_ERROR_TOO_AMBIGUOUS', 32);
206/**
207 * No piece of the current color can execute the SAN (as in, if Na3 is passed
208 * in, but there are no knights that can reach a3
209 */
210define('GAMES_CHESS_ERROR_NOPIECE_CANDOTHAT', 33);
211/**
212 * In loser's chess, and the current move does not capture a piece although
213 * capture is possible.
214 */
215define('GAMES_CHESS_ERROR_MOVE_MUST_CAPTURE', 34);
216/**
217 * When piece placement is attempted, but no pieces exist to be placed
218 */
219define('GAMES_CHESS_ERROR_NOPIECES_TOPLACE', 35);
220/**
221 * When piece placement is attempted, but there is a piece on the desired square already
222 */
223define('GAMES_CHESS_ERROR_PIECEINTHEWAY', 36);
224/**
225 * When a pawn placement on the first or back rank is attempted
226 */
227define('GAMES_CHESS_ERROR_CANT_PLACE_18', 37);
228/**
229 * ABSTRACT parent class - use {@link Games_Chess_Standard} for a typical
230 * chess game
231 *
232 * This class contains a few public methods that are the only thing most
233 * users of the package will ever need.  Protected methods are available
234 * for usage by child classes, and it is expected that all child classes
235 * will implement certain protected methods used by the utility methods in
236 * this class.
237 *
238 * Public API methods used are:
239 *
240 * Game-related methods
241 *
242 * - {@link resetGame()}: in order to start a new game (pass a FEN for a starting
243 *   position)
244 * - {@link blankBoard()}: in order to start with an empty chessboard
245 * - {@link addPiece()}: Use to add pieces one at a time to the board
246 * - {@link moveSAN()}: Use to move pieces based on their SAN (Qa3, exd5, etc.)
247 * - {@link moveSquare()}: Use to move pieces based on their square (a2 -> a3
248 *   for Qa3, e4 -> d5 for exd5, etc.)
249 *
250 * Game state methods:
251 *
252 * - {@link inCheck()}: Use to determine the presence of check
253 * - {@link inCheckMate()}: Use to determine a won game
254 * - {@link inStaleMate()}: Use to determine presence of stalemate draw
255 * - {@link in50MoveDraw()}: Use to determine presence of 50-move rule draw
256 * - {@link inRepetitionDraw()}: Use to determine presence of a draw by repetition
257 * - {@link inStaleMate()}: Use to determine presence of stalemate draw
258 * - {@link inDraw()}: Use to determine if any forced draw condition exists
259 *
260 * Game data methods:
261 *
262 * - {@link renderFen()}: Use to retrieve a FEN representation of the
263 *   current chessboard position, in order to transfer to another chess program
264 * - {@link toArray()}: Use to retrieve a literal representation of the
265 *   current chessboard position, in order to display as HTML or some other
266 *   format for the user
267 * - {@link getMoveList()}: Use to retrieve the list of SAN moves for this game
268 * @package Games_Chess
269 */
270class Games_Chess {
271    /**
272     * Used for transactions
273     * @var array
274     * @access private
275     */
276    var $_saveState = array();
277    /**
278     * @var array
279     * @access private
280     */
281    var $_board;
282    /**
283     * @var string
284     * @access private
285     */
286    var $_move = 'W';
287    /**
288     * @var integer
289     * @access private
290     */
291    var $_moveNumber = 1;
292    /**
293     * Half-moves since last pawn move or capture
294     * @var integer
295     * @access private
296     */
297    var $_halfMoves = 1;
298    /**
299     * Square that an en passant can happen, or "-"
300     * @var string
301     * @access private
302     */
303    var $_enPassantSquare = '-';
304    /**
305     * Moves in SAN format for easy write-out to a PGN file
306     *
307     * The format is:
308     * <pre>
309     * array(
310     *  movenumber => array(White move, Black move),
311     *  movenumber => array(White move, Black move),
312     * )
313     * </pre>
314     * @var array
315     * @access private
316     */
317    var $_moves = array();
318    /**
319     * Moves in SAN format for easy write-out to a PGN file, with check/checkmate annotations appended
320     *
321     * The format is:
322     * <pre>
323     * array(
324     *  movenumber => array(White move, Black move),
325     *  movenumber => array(White move, Black move),
326     * )
327     * </pre>
328     * @var array
329     * @access private
330     */
331    var $_movesWithCheck = array();
332    /**
333     * Store every position from the game, used to determine draw by repetition
334     *
335     * If the exact same position is encountered three times, then it is a draw
336     * @var array
337     * @access private
338     */
339    var $_allFENs = array();
340    /**#@+
341     * Castling rights
342     * @var boolean
343     * @access private
344     */
345    var $_WCastleQ = true;
346    var $_WCastleK = false;
347    var $_BCastleQ = true;
348    var $_BCastleK = false;
349    /**#@-*/
350    /**
351     * Contents of the last move returned from {@link _parseMove()}, used to
352     * process en passant.
353     * @var false|array
354     * @access private
355     */
356    var $_lastMove = false;
357
358    function &factory($type = 'Standard')
359    {
360        if (!class_exists("Games_Chess_$type")) {
361            @include_once 'Games/Chess/' . ucfirst(strtolower($type)) . '.php';
362        }
363        if (class_exists("Games_Chess_$type")) {
364            $type = "Games_Chess_$type";
365            $a = new $type;
366            return $a;
367        } else {
368            $a = false;
369            return $a;
370        }
371    }
372
373    /**
374     * Create a blank chessboard with no pieces on it
375     */
376    function blankBoard()
377    {
378        $this->_board = array();
379        for ($j = 8; $j >= 1; $j--) {
380            for ($i = ord('a'); $i <= ord('h'); $i++) {
381                $this->_board[chr($i) . $j] = chr($i) . $j;
382            }
383        }
384    }
385
386    /**
387     * Create a new game with the starting position, or from the position
388     * specified by $fen
389     *
390     * @param false|string
391     * @return PEAR_Error|true returns any errors thrown by {@link _parseFen()}
392     */
393    function resetGame($fen = false)
394    {
395        $this->_saveState = array();
396        if (!$fen) {
397            $this->_setupStartingPosition();
398        } else {
399            return $this->_parseFen($fen);
400        }
401        return true;
402    }
403
404    /**
405     * Make a move from a Standard Algebraic Notation (SAN) format
406     *
407     * SAN is just a normal chess move like Na4, instead of the English Notation,
408     * like NR4
409     * @param string
410     * @return true|PEAR_Error
411     */
412    function moveSAN($move)
413    {
414        if (!is_array($this->_board)) {
415            $this->resetGame();
416        }
417        if (!$this->isError($parsedMove = $this->_parseMove($move))) {
418            if (!$this->isError($err = $this->_validMove($parsedMove))) {
419                list($key, $parsedMove) = each($parsedMove);
420                $this->_moves[$this->_moveNumber][($this->_move == 'W') ? 0 : 1] = $move;
421                $oldMoveNumber = $this->_moveNumber;
422                $this->_moveNumber += ($this->_move == 'W') ? 0 : 1;
423                $this->_halfMoves++;
424                if ($key == GAMES_CHESS_CASTLE) {
425                    $a = ($parsedMove == 'Q') ? 'K' : 'Q';
426                    // clear castling rights
427                    $this->{'_' . $this->_move . 'Castle' . $parsedMove} = false;
428                    $this->{'_' . $this->_move . 'Castle' . $a} = false;
429                    $row = ($this->_move == 'W') ? 1 : 8;
430                    switch ($parsedMove) {
431                        case 'K' :
432                            $this->_moveAlgebraic("e$row", "g$row");
433                            $this->_moveAlgebraic("h$row", "f$row");
434                        break;
435                        case 'Q' :
436                            $this->_moveAlgebraic("e$row", "c$row");
437                            $this->_moveAlgebraic("a$row", "d$row");
438                        break;
439                    }
440                    $this->_enPassantSquare = '-';
441                } else {
442                    $movedfrom = $this->_getSquareFromParsedMove($parsedMove);
443                    $promote = isset($parsedMove['promote']) ?
444                        $parsedMove['promote'] : '';
445                    $this->_moveAlgebraic($movedfrom, $parsedMove['square'], $promote);
446                    if ($parsedMove['takes']) {
447                        $this->_halfMoves = 1;
448                    }
449                    if ($parsedMove['piece'] == 'P') {
450                        $this->_halfMoves = 1;
451                        $this->_enPassantSquare = '-';
452                        if (in_array($movedfrom{1} - $parsedMove['square']{1},
453                              array(2, -2))) {
454                            $direction = ($this->_move == 'W' ? 1 : -1);
455                            $this->_enPassantSquare = $parsedMove['square']{0} .
456                                ($parsedMove['square']{1} - $direction);
457                        }
458                    } else {
459                        $this->_enPassantSquare = '-';
460                    }
461                    if ($parsedMove['piece'] == 'K') {
462                        $this->{'_' . $this->_move . 'CastleQ'} = false;
463                        $this->{'_' . $this->_move . 'CastleK'} = false;
464                    }
465                    if ($parsedMove['piece'] == 'R') {
466                        if ($movedfrom{0} == 'a') {
467                        $this->{'_' . $this->_move . 'CastleQ'} = false;
468                        }
469                        if ($movedfrom{0} == 'h') {
470                        $this->{'_' . $this->_move . 'CastleK'} = false;
471                        }
472                    }
473                }
474                $moveWithCheck = $move;
475                if ($this->inCheckMate(($this->_move == 'W') ? 'B' : 'W')) {
476                    $moveWithCheck .= '#';
477                } elseif ($this->inCheck(($this->_move == 'W') ? 'B' : 'W')) {
478                    $moveWithCheck .= '+';
479                }
480                $this->_movesWithCheck[$oldMoveNumber][($this->_move == 'W') ? 0 : 1] = $moveWithCheck;
481                $this->_move = ($this->_move == 'W' ? 'B' : 'W');
482
483                // increment the position counter for this position
484                $x = $this->renderFen(false);
485                if (!isset($this->_allFENs[$x])) {
486                    $this->_allFENs[$x] = 0;
487                }
488                $this->_allFENs[$x]++;
489                return true;
490            } else {
491                return $err;
492            }
493        } else {
494            return $parsedMove;
495        }
496    }
497
498    /**
499     * Move a piece from one square to another, and mark the old square as empty
500     *
501     * @param string [a-h][1-8] square to move from
502     * @param string [a-h][1-8] square to move to
503     * @param string piece to promote to, if this is a promotion move
504     * @return true|PEAR_Error
505     */
506    function moveSquare($from, $to, $promote = '')
507    {
508        $move = $this->_convertSquareToSAN($from, $to, $promote);
509        if ($this->isError($move)) {
510            return $move;
511        } else {
512            return $this->moveSAN($move);
513        }
514    }
515
516    /**
517     * Get the list of moves in Standard Algebraic Notation
518     *
519     * Can be used to populate a PGN file.
520     * @param boolean If true, then moves that check will be postfixed with "+" and checkmate with "#"
521     *                as in Nf3+ or Qxg7#
522     * @return array
523     */
524    function getMoveList($withChecks = false)
525    {
526        if ($withChecks) {
527            return $this->_movesWithCheck;
528        }
529        return $this->_moves;
530    }
531
532    /**
533     * @return W|B|D|false winner of game, or draw, or false if still going
534     */
535    function gameOver()
536    {
537        $opposite = $this->_move == 'W' ? 'B' : 'W';
538        if ($this->inCheckmate()) {
539            return $opposite;
540        }
541        if ($this->inDraw()) {
542            return 'D';
543        }
544        return false;
545    }
546
547    /**
548     * Determine whether a side is in checkmate
549     * @param W|B color of side to check, defaults to the current side
550     * @return boolean
551     * @throws GAMES_CHESS_ERROR_INVALID_COLOR
552     */
553    function inCheckMate($color = null)
554    {
555        if (is_null($color)) {
556            $color = $this->_move;
557        }
558        $color = strtoupper($color);
559        if (!in_array($color, array('W', 'B'))) {
560            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
561                array('color' => $color));
562        }
563        if (!($checking = $this->inCheck($color))) {
564            return false;
565        }
566        $moves = $this->getPossibleKingMoves($king = $this->_getKing($color), $color);
567        foreach ($moves as $escape) {
568            $this->startTransaction();
569            $this->_move = $color;
570            if (!class_exists('PEAR')) {
571                require_once 'PEAR.php';
572            }
573            PEAR::pushErrorHandling(PEAR_ERROR_RETURN);
574            $this->moveSquare($king, $escape);
575            PEAR::popErrorHandling();
576            $this->_move = $color;
577            $stillchecked = $this->inCheck($color);
578            $this->rollbackTransaction();
579            if (!$stillchecked) {
580                return false;
581            }
582        }
583        // if we're in double check, and the king can't move, that's checkmate
584        if (is_array($checking) && count($checking) > 1) {
585            return true;
586        }
587        $squares = $this->_getPathToKing($checking, $king);
588        if ($this->_interposeOrCapture($squares, $color)) {
589            return false;
590        }
591        return true;
592    }
593
594    /**
595     * Determine whether a side is in stalemate
596     * @param W|B color of the side to look at, defaults to the current side
597     * @return boolean
598     * @throws GAMES_CHESS_ERROR_INVALID_COLOR
599     */
600    function inStaleMate($color = null)
601    {
602        if (is_null($color)) {
603            $color = $this->_move;
604        }
605        $color = strtoupper($color);
606        if (!in_array($color, array('W', 'B'))) {
607            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
608                array('color' => $color));
609        }
610        if ($this->inCheck($color)) {
611            return false;
612        }
613        $moves = $this->_getPossibleChecks($color);
614        foreach($moves as $name => $canmove) {
615            if (count($canmove)) {
616                $a = $this->_getPiece($name);
617                foreach($canmove as $move) {
618                    $this->startTransaction();
619                    $this->_move = $color;
620                    if (!class_exists('PEAR')) {
621                        require_once 'PEAR.php';
622                    }
623                    PEAR::pushErrorHandling(PEAR_ERROR_RETURN);
624                    $err = $this->moveSquare($a, $move);
625                    PEAR::popErrorHandling();
626                    $this->rollbackTransaction();
627                    if (!is_object($err)) {
628                        return false;
629                    }
630                }
631            }
632        }
633        return true;
634    }
635
636    /**
637     * Determines the presence of a forced draw
638     * @param W|B
639     * @return boolean
640     */
641    function inDraw($color = null)
642    {
643        return $this->inStaleMate($color) ||
644               $this->inRepetitionDraw() ||
645               $this->in50MoveDraw() ||
646               $this->inBasicDraw();
647    }
648
649    /**
650     * Determine whether draw by repetition has happened
651     *
652     * From FIDE rules:
653     * <pre>
654     * 10.10
655     *
656     * The game is drawn, upon a claim by the player having the move, when the
657     * same position, for the third time:
658     * (a) is about to appear, if he first writes the move on his
659     *     scoresheet and declares to the arbiter his intention of making
660     *     this move; or
661     * (b) has just appeared, the same player having the move each time.
662     *
663     * The position is considered the same if pieces of the same kind and
664     * colour occupy the same squares, and if all the possible moves of
665     * all the pieces are the same, including the rights to castle [at
666     * some future time] or to capture a pawn "en passant".
667     * </pre>
668     *
669     * This class determines draw by comparing FENs rendered after every move
670     * @return boolean
671     */
672    function inRepetitionDraw()
673    {
674        $fen = $this->renderFen(false);
675        if (isset($this->_allFENs[$fen]) && $this->_allFENs[$fen] == 3) {
676            return true;
677        }
678        return false;
679    }
680
681    /**
682     * Determine whether any pawn move or capture has occurred in the past 50 moves
683     * @return boolean
684     */
685    function in50MoveDraw()
686    {
687        return $this->_halfMoves >= 50;
688    }
689
690    /**
691     * Determine the presence of a basic draw as defined by FIDE rules
692     *
693     * The rule states:
694     * <pre>
695     * 10.4
696     *
697     * The game is drawn when one of the following endings arises:
698     * (a) king against king;
699     * (b) king against king with only bishop or knight;
700     * (c) king and bishop against king and bishop, with both bishops
701     *     on diagonals of the same colour.
702     * </pre>
703     * @return boolean
704     */
705    function inBasicDraw()
706    {
707        $pieces = $this->_getPieceTypes();
708        $blackpieces = array_keys($pieces['B']);
709        $whitepieces = array_keys($pieces['W']);
710        if (count($blackpieces) > 2 || count($whitepieces) > 2) {
711            return false;
712        }
713        if (count($blackpieces) == 1) {
714            if (count($whitepieces) == 1) {
715                return true;
716            }
717            if ($whitepieces[0] == 'K') {
718                if (in_array($whitepieces[1], array('N', 'B'))) {
719                    return true;
720                } else {
721                    return false;
722                }
723            } else {
724                if (in_array($whitepieces[0], array('N', 'B'))) {
725                    return true;
726                } else {
727                    return false;
728                }
729            }
730        }
731
732        if (count($whitepieces) == 1) {
733            if (count($blackpieces) == 1) {
734                return true;
735            }
736            if ($blackpieces[0] == 'K') {
737                if (in_array($blackpieces[1], array('N', 'B'))) {
738                    return true;
739                } else {
740                    return false;
741                }
742            } else {
743                if (in_array($blackpieces[0], array('N', 'B'))) {
744                    return true;
745                } else {
746                    return false;
747                }
748            }
749        }
750        $wpindex = ($whitepieces[0] == 'K') ? 1 : 0;
751        $bpindex = ($blackpieces[0] == 'K') ? 1 : 0;
752        if ($whitepieces[$wpindex] == 'B' && $blackpieces[$bpindex] == 'B') {
753            // bishops of same color?
754            if ($pieces['B']['B'][0] == $pieces['W']['B'][0]) {
755                return true;
756            }
757        }
758        return false;
759    }
760
761    /**
762     * render the FEN notation for the current board
763     * @param boolean private parameter, used to determine whether to include
764     *                move number/ply count - this is used to keep track of
765     *                positions for draw detection
766     * @return string
767     */
768    function renderFen($include_moves = true)
769    {
770        $fen = $this->_renderFen() . ' ';
771
772        // render who's to move
773        $fen .= strtolower($this->_move) . ' ';
774
775        // render castling rights
776        if (!$this->_WCastleQ && !$this->_WCastleK && !$this->_BCastleQ
777              && !$this->_BCastleK) {
778            $fen .= '- ';
779        } else {
780            if ($this->_WCastleK) {
781                $fen .= 'K';
782            }
783            if ($this->_WCastleQ) {
784                $fen .= 'Q';
785            }
786            if ($this->_BCastleK) {
787                $fen .= 'k';
788            }
789            if ($this->_BCastleQ) {
790                $fen .= 'q';
791            }
792            $fen .= ' ';
793        }
794
795        // render en passant square
796        $fen .= $this->_enPassantSquare;
797
798        if (!$include_moves) {
799            return $fen;
800        }
801
802        // render half moves since last pawn move or capture
803        $fen .=  ' ' . $this->_halfMoves . ' ';
804
805        // render move number
806        $fen .= $this->_moveNumber;
807        return $fen;
808    }
809
810    /**
811     * Add a piece to the chessboard
812     *
813     * Must be overridden in child classes
814     * @abstract
815     * @param W|B Color of piece
816     * @param P|N|K|Q|R|B Piece type
817     * @param string algebraic location of piece
818     */
819    function addPiece($color, $type, $square)
820    {
821        trigger_error("Error: do not use abstract Games_Chess class", E_USER_ERROR);
822    }
823
824    /**
825     * Generate a representation of the chess board and pieces for use as a
826     * direct translation to a visual chess board
827     *
828     * Must be overridden in child classes
829     * @return array
830     * @abstract
831     */
832    function toArray()
833    {
834        trigger_error("Error: do not use abstract Games_Chess class", E_USER_ERROR);
835    }
836
837    /**
838     * Determine whether moving a piece from one square to another requires
839     * a pawn promotion
840     * @param string [a-h][1-8] location of the piece to move
841     * @param string [a-h][1-8] place to move the piece to
842     * @return boolean true if the move represented by moving from $from to $to
843     *                 is a pawn promotion move
844     */
845    function isPromoteMove($from, $to)
846    {
847        $test = $this->_convertSquareToSAN($from, $to);
848        if ($this->isError($test)) {
849            return false;
850        }
851        if (strpos($test, '=Q') !== false) {
852            return true;
853        }
854        return false;
855    }
856
857    /**
858     * @return W|B return the color of the side to move (white or black)
859     */
860    function toMove()
861    {
862        return $this->_move;
863    }
864
865    /**
866     * Determine legality of kingside castling
867     * @return boolean
868     */
869    function canCastleKingside()
870    {
871        return $this->{'_' . $this->_move . 'CastleK'};
872    }
873
874
875    /**
876     * Determine legality of queenside castling
877     * @return boolean
878     */
879    function canCastleQueenside()
880    {
881        return $this->{'_' . $this->_move . 'CastleQ'};
882    }
883
884    /**
885     * Move a piece from one square to another, and mark the old square as empty
886     *
887     * NO validation is performed, use {@link moveSquare()} for validation.
888     *
889     * @param string [a-h][1-8] square to move from
890     * @param string [a-h][1-8] square to move to
891     * @param string piece to promote to, if this is a promotion move
892     * @access protected
893     */
894    function _moveAlgebraic($from, $to, $promote = '')
895    {
896        if ($to == $this->_enPassantSquare && $this->isPawn($this->_board[$from])) {
897            $rank = ($to{1} == '3') ? '4' : '5';
898            // this piece was just taken
899            $this->_takePiece($to{0} . $rank);
900            $this->_board[$to{0} . $rank] = $to{0} . $rank;
901        }
902        if ($this->_board[$to] != $to) {
903            // this piece was just taken
904            $this->_takePiece($to);
905        }
906        // mark the piece as moved
907        $this->_movePiece($from, $to, $promote);
908        $this->_board[$to] = $this->_board[$from];
909        $this->_board[$from] = $from;
910    }
911
912    /**
913     * Parse out the segments of a move (minus any annotations)
914     * @param string
915     * @return array
916     * @access protected
917     */
918    function _parseMove($move)
919    {
920        if ($move == 'O-O') {
921            return array(GAMES_CHESS_CASTLE => 'K');
922        }
923        if ($move == 'O-O-O') {
924            return array(GAMES_CHESS_CASTLE => 'Q');
925        }
926        // pawn moves
927        if (preg_match('/^P?(([a-h])([1-8])?(x))?([a-h][1-8])(=?([QRNB]))?$/', $move, $match)) {
928            if ($match[2]) {
929                $takesfrom = $match[2]{0};
930            } else {
931                $takesfrom = '';
932            }
933            $res = array(
934                'takesfrom' => $takesfrom,
935                'takes' => $match[4],
936                'disambiguate' => '',
937                'square' => $match[5],
938                'promote' => '',
939                'piece' => 'P',
940            );
941            if (isset($match[7])) {
942                $res['promote'] = $match[7];
943            }
944            return array(GAMES_CHESS_PAWNMOVE => $res);
945        // piece moves
946        } elseif (preg_match('/^(K)(x)?([a-h][1-8])$/', $move, $match)) {
947            $res = array(
948                'takesfrom' => false,
949                'piece' => $match[1],
950                'disambiguate' => '',
951                'takes' => $match[2],
952                'square' => $match[3],
953            );
954            return array(GAMES_CHESS_PIECEMOVE => $res);
955        } elseif (preg_match('/^([QRBN])([a-h]|[1-8]|[a-h][1-8])?(x)?([a-h][1-8])$/', $move, $match)) {
956            $res = array(
957                'takesfrom' => false,
958                'piece' => $match[1],
959                'disambiguate' => $match[2],
960                'takes' => $match[3],
961                'square' => $match[4],
962            );
963            return array(GAMES_CHESS_PIECEMOVE => $res);
964        } elseif (preg_match('/^([QRBN])@([a-h][1-8])$/', $move, $match)) {
965            $res = array(
966                'piece' => $match[1],
967                'square' => $match[2],
968            );
969            return array(GAMES_CHESS_PIECEPLACEMENT => $res);
970        // error
971        } elseif (preg_match('/^([P])@([a-h][2-7])$/', $move, $match)) {
972            $res = array(
973                'piece' => $match[1],
974                'square' => $match[2],
975            );
976            return array(GAMES_CHESS_PIECEPLACEMENT => $res);
977        // error
978        } elseif (preg_match('/^([P])@([a-h][18])$/', $move, $match)) {
979            return $this->raiseError(GAMES_CHESS_ERROR_CANT_PLACE_18, array('san' => $move));
980        // error
981        } else {
982            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SAN,
983                array('pgn' => $move));
984        }
985    }
986
987
988    /**
989     * Set up the board with the starting position
990     *
991     * Must be overridden in child classes
992     * @abstract
993     * @access protected
994     */
995    function _setupStartingPosition()
996    {
997        trigger_error("Error: do not use abstract Games_Chess class", E_USER_ERROR);
998    }
999
1000    /**
1001     * Parse a Forsyth-Edwards Notation (FEN) chessboard position string, and
1002     * set up the chessboard with this position
1003     * @param string
1004     * @access private
1005     */
1006    function _parseFen($fen)
1007    {
1008        $splitfen = explode(' ', $fen);
1009        if (count($splitfen) != 6) {
1010            return $this->raiseError(GAMES_CHESS_ERROR_FEN_COUNT,
1011                array('fen' => $fen, 'sections' => count($splitfen)));
1012        }
1013
1014        foreach($splitfen as $index => $test) {
1015            if ($test == '') {
1016                return $this->raiseError(GAMES_CHESS_ERROR_EMPTY_FEN,
1017                    array('fen' => $fen, 'section' => $index));
1018            }
1019        }
1020
1021        $this->blankBoard();
1022        $loc = 'a8';
1023        $idx = 0;
1024        $FEN = $splitfen[0];
1025
1026        // parse position section
1027        while ($idx < strlen($FEN)) {
1028            $c = $FEN{$idx};
1029            switch ($c) {
1030                case "K" :
1031                case "Q" :
1032                case "R" :
1033                case "B" :
1034                case "N" :
1035                case "P" :
1036                    if (!class_exists('PEAR')) {
1037                        require_once 'PEAR.php';
1038                    }
1039                    PEAR::pushErrorHandling(PEAR_ERROR_RETURN);
1040                    $err = $this->addPiece('W', $c, $loc);
1041                    PEAR::popErrorHandling();
1042                    if ($this->isError($err)) {
1043                        if ($err->getCode() == GAMES_CHESS_ERROR_MULTIPIECE) {
1044                            return $this->raiseError(GAMES_CHESS_ERROR_FEN_MULTIPIECE,
1045                            array('fen' => $fen, 'color' => 'W', 'piece' => $c));
1046                        } else {
1047                            return $err;
1048                        }
1049                    }
1050                break;
1051                case "k" :
1052                case "q" :
1053                case "r" :
1054                case "b" :
1055                case "n" :
1056                case "p" :
1057                    if (!class_exists('PEAR')) {
1058                        require_once 'PEAR.php';
1059                    }
1060                    PEAR::pushErrorHandling(PEAR_ERROR_RETURN);
1061                    $err = $this->addPiece('B', strtoupper($c), $loc);
1062                    PEAR::popErrorHandling();
1063                    if ($this->isError($err)) {
1064                        if ($err->getCode() == GAMES_CHESS_ERROR_MULTIPIECE) {
1065                            return $this->raiseError(GAMES_CHESS_ERROR_FEN_MULTIPIECE,
1066                            array('fen' => $fen, 'color' => 'B', 'piece' => $c));
1067                        } else {
1068                            return $err;
1069                        }
1070                    }
1071                break;
1072
1073                case "1" :
1074                case "2" :
1075                case "3" :
1076                case "4" :
1077                case "5" :
1078                case "6" :
1079                case "7" :
1080                case "8" :
1081                    $loc{0} = chr(ord($loc{0}) + ($c - 1));
1082                break;
1083                case "/" :
1084                    $loc{1} = $loc{1} - 1;
1085                    $loc{0} = 'a';
1086                    $idx++;
1087                    continue 2;
1088                break;
1089                default :
1090                    return $this->raiseError(GAMES_CHESS_ERROR_FEN_INVALIDPIECE,
1091                        array('fen' => $fen, 'fenchar' => $c));
1092                break;
1093            }
1094            $idx++;
1095            $loc{0} = chr(ord($loc{0}) + 1);
1096            if (ord($loc{0}) > ord('h')) {
1097                if (strlen($FEN) > $idx && $FEN{$idx} != '/') {
1098                    return $this->raiseError(GAMES_CHESS_ERROR_FEN_TOOMUCH,
1099                        array('fen' => $fen));
1100                }
1101            }
1102        }
1103        if ($loc != 'i1') {
1104            return $this->raiseError(GAMES_CHESS_ERROR_FEN_TOOLITTLE,
1105                array('fen' => $fen));
1106        }
1107
1108        // parse who's to move
1109        if (!in_array($splitfen[1], array('w', 'b', 'W', 'B'))) {
1110            return $this->raiseError(GAMES_CHESS_ERROR_FEN_TOMOVEWRONG,
1111                array('fen' => $fen, 'tomove' => $splitfen[1]));
1112        }
1113        $this->_move = strtoupper($splitfen[1]);
1114
1115        // parse castling rights
1116        if (strlen($splitfen[2]) > 4) {
1117            return $this->raiseError(GAMES_CHESS_ERROR_FEN_CASTLETOOLONG,
1118                array('fen' => $fen, 'castle' => $splitfen[2]));
1119        }
1120        $this->_WCastleQ = false;
1121        $this->_WCastleK = false;
1122        $this->_BCastleQ = false;
1123        $this->_BCastleK = false;
1124        if ($splitfen[2] != '-') {
1125            for ($i = 0; $i < 4; $i++) {
1126                if ($i >= strlen($splitfen[2])) {
1127                    continue;
1128                }
1129                switch ($splitfen[2]{$i}) {
1130                    case 'K' :
1131                        $this->_WCastleK = true;
1132                    break;
1133                    case 'Q' :
1134                        $this->_WCastleQ = true;
1135                    break;
1136                    case 'k' :
1137                        $this->_BCastleK = true;
1138                    break;
1139                    case 'q' :
1140                        $this->_BCastleQ = true;
1141                    break;
1142                    default:
1143                        return $this->raiseError(GAMES_CHESS_ERROR_FEN_CASTLEWRONG,
1144                            array('fen' => $fen, 'castle' => $splitfen[2]{$i}));
1145                    break;
1146                }
1147            }
1148        }
1149
1150        // parse en passant square
1151        $this->_enPassantSquare = '-';
1152        if ($splitfen[3] != '-') {
1153            if (!preg_match('/^[a-h][36]$/', $splitfen[3])) {
1154                return $this->raiseError(GAMES_CHESS_ERROR_FEN_INVALID_EP,
1155                    array('fen' => $fen, 'enpassant' => $splitfen[3]));
1156            }
1157            $this->_enPassantSquare = $splitfen[3];
1158        }
1159
1160        // parse half moves since last pawn move or capture
1161        if (!is_numeric($splitfen[4])) {
1162            return $this->raiseError(GAMES_CHESS_ERROR_FEN_INVALID_PLY,
1163                array('fen' => $fen, 'ply' => $splitfen[4]));
1164        }
1165        $this->_halfMoves = $splitfen[4];
1166
1167        // parse move number
1168        if (!is_numeric($splitfen[5])) {
1169            return $this->raiseError(GAMES_CHESS_ERROR_FEN_INVALID_MOVENUMBER,
1170                array('fen' => $fen, 'movenumber' => $splitfen[5]));
1171        }
1172        $this->_moveNumber = $splitfen[5];
1173        return true;
1174    }
1175
1176    /**
1177     * Validate a move
1178     * @param array parsed move array from {@link _parsedMove()}
1179     * @return true|PEAR_Error
1180     * @throws GAMES_CHESS_ERROR_IN_CHECK
1181     * @throws GAMES_CHESS_ERROR_CANT_CK
1182     * @throws GAMES_CHESS_ERROR_CK_PIECES_IN_WAY
1183     * @throws GAMES_CHESS_ERROR_CANT_CQ
1184     * @throws GAMES_CHESS_ERROR_CQ_PIECES_IN_WAY
1185     * @throws GAMES_CHESS_ERROR_CASTLE_WOULD_CHECK
1186     * @throws GAMES_CHESS_ERROR_CANT_CAPTURE_OWN
1187     * @throws GAMES_CHESS_ERROR_STILL_IN_CHECK
1188     * @throws GAMES_CHESS_ERROR_MOVE_WOULD_CHECK
1189     * @access protected
1190     */
1191    function _validMove($move)
1192    {
1193        list($type, $info) = each($move);
1194        $this->startTransaction();
1195        $valid = false;
1196        switch ($type) {
1197            case GAMES_CHESS_CASTLE :
1198                if ($this->inCheck($this->_move)) {
1199                    $this->rollbackTransaction();
1200                    return $this->raiseError(GAMES_CHESS_ERROR_IN_CHECK);
1201                }
1202                if ($info == 'K') {
1203                    if ($this->_move == 'W') {
1204                        if (!$this->_WCastleK) {
1205                            $this->rollbackTransaction();
1206                            return $this->raiseError(GAMES_CHESS_ERROR_CANT_CK);
1207                        }
1208                        if ($this->_board['f1'] != 'f1' || $this->_board['g1'] != 'g1') {
1209                            $this->rollbackTransaction();
1210                            return $this->raiseError(GAMES_CHESS_ERROR_CK_PIECES_IN_WAY);
1211                        }
1212                        $kingsquares = array('f1', 'g1');
1213                        $on = 'e1';
1214                    } else {
1215                        if (!$this->_BCastleK) {
1216                            $this->rollbackTransaction();
1217                            return $this->raiseError(GAMES_CHESS_ERROR_CANT_CK);
1218                        }
1219                        if ($this->_board['f8'] != 'f8' || $this->_board['g8'] != 'g8') {
1220                            $this->rollbackTransaction();
1221                            return $this->raiseError(GAMES_CHESS_ERROR_CK_PIECES_IN_WAY);
1222                        }
1223                        $kingsquares = array('f8', 'g8');
1224                        $on = 'e8';
1225                    }
1226                } else {
1227                    if ($this->_move == 'W') {
1228                        if (!$this->_WCastleQ) {
1229                            $this->rollbackTransaction();
1230                            return $this->raiseError(GAMES_CHESS_ERROR_CANT_CQ);
1231                        }
1232                        if ($this->_board['d1'] != 'd1' ||
1233                              $this->_board['c1'] != 'c1' ||
1234                              $this->_board['b1'] != 'b1') {
1235                            $this->rollbackTransaction();
1236                            return $this->raiseError(GAMES_CHESS_ERROR_CQ_PIECES_IN_WAY);
1237                        }
1238                        $kingsquares = array('d1', 'c1');
1239                        $on = 'e1';
1240                    } else {
1241                        if (!$this->_BCastleQ) {
1242                            $this->rollbackTransaction();
1243                            return $this->raiseError(GAMES_CHESS_ERROR_CANT_CQ);
1244                        }
1245                        if ($this->_board['d8'] != 'd8' ||
1246                              $this->_board['c8'] != 'c8' ||
1247                              $this->_board['b8'] != 'b8') {
1248                            $this->rollbackTransaction();
1249                            return $this->raiseError(GAMES_CHESS_ERROR_CQ_PIECES_IN_WAY);
1250                        }
1251                        $kingsquares = array('d8', 'c8');
1252                        $on = 'e8';
1253                    }
1254                }
1255
1256                // check every square the king could move to and make sure
1257                // we wouldn't be in check
1258                foreach ($kingsquares as $square) {
1259                    $this->_moveAlgebraic($on, $square);
1260                    if ($this->inCheck($this->_move)) {
1261                        $this->rollbackTransaction();
1262                        return $this->raiseError(GAMES_CHESS_ERROR_CASTLE_WOULD_CHECK);
1263                    }
1264                    $on = $square;
1265                }
1266                $valid = true;
1267            break;
1268            case GAMES_CHESS_PIECEMOVE :
1269            case GAMES_CHESS_PAWNMOVE :
1270                if (!$this->isError($piecesq = $this->_getSquareFromParsedMove($info))) {
1271                    $wasinCheck = $this->inCheck($this->_move);
1272                    $piece = $this->_board[$info['square']];
1273                    if ($info['takes'] && $this->_board[$info['square']] ==
1274                          $info['square']) {
1275                        if (!($info['square'] == $this->_enPassantSquare &&
1276                              $info['piece'] == 'P')) {
1277                            return $this->raiseError(GAMES_CHESS_ERROR_NO_PIECE,
1278                                array('square' => $info['square']));
1279                        }
1280                    }
1281                    $this->_moveAlgebraic($piecesq, $info['square']);
1282                    $valid = !$this->inCheck($this->_move);
1283                    if ($wasinCheck && !$valid) {
1284                        $this->rollbackTransaction();
1285                        return $this->raiseError(GAMES_CHESS_ERROR_STILL_IN_CHECK);
1286                    } elseif (!$valid) {
1287                        $this->rollbackTransaction();
1288                        return $this->raiseError(GAMES_CHESS_ERROR_MOVE_WOULD_CHECK);
1289                    }
1290                } else {
1291                    $this->rollbackTransaction();
1292                    return $piecesq;
1293                }
1294            break;
1295        }
1296        $this->rollbackTransaction();
1297        return $valid;
1298    }
1299
1300    /**
1301     * Convert a starting and ending algebraic square into SAN
1302     * @access protected
1303     * @param string [a-h][1-8] square piece is on
1304     * @param string [a-h][1-8] square piece moves to
1305     * @param string Q|R|B|N
1306     * @return string|PEAR_Error
1307     * @throws GAMES_CHESS_ERROR_INVALID_PROMOTE
1308     * @throws GAMES_CHESS_ERROR_INVALID_SQUARE
1309     * @throws GAMES_CHESS_ERROR_NO_PIECE
1310     * @throws GAMES_CHESS_ERROR_WRONG_COLOR
1311     * @throws GAMES_CHESS_ERROR_CANT_MOVE_THAT_WAY
1312     */
1313    function _convertSquareToSAN($from, $to, $promote = '')
1314    {
1315        if ($promote == '') {
1316            $promote = 'Q';
1317        }
1318        $promote = strtoupper($promote);
1319        if (!in_array($promote, array('Q', 'B', 'N', 'R'))) {
1320            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_PROMOTE,
1321                array('piece' => $promote));
1322        }
1323        $SAN = '';
1324        if (!preg_match('/^[a-h][1-8]$/', $from)) {
1325            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1326                array('square' => $from));
1327        }
1328        if (!preg_match('/^[a-h][1-8]$/', $to)) {
1329            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1330                array('square' => $to));
1331        }
1332        $piece = $this->_squareToPiece($from);
1333        if (!$piece) {
1334            return $this->raiseError(GAMES_CHESS_ERROR_NO_PIECE,
1335                array('square' => $from));
1336        }
1337        if ($piece['color'] != $this->_move) {
1338            return $this->raiseError(GAMES_CHESS_ERROR_WRONG_COLOR,
1339                array('square' => $from));
1340        }
1341        $moves = $this->getPossibleMoves($piece['piece'], $from, $piece['color']);
1342        if (!in_array($to, $moves)) {
1343            return $this->raiseError(GAMES_CHESS_ERROR_CANT_MOVE_THAT_WAY,
1344                array('from' => $from, 'to' => $to));
1345        }
1346        if ($piece['piece'] == 'K' && !in_array($to, $this->_getKingSquares($from))) {
1347            // this is a castling attempt
1348            if ($to{0} == 'g') {
1349                return 'O-O';
1350            } else {
1351                return 'O-O-O';
1352            }
1353        }
1354        $others = array();
1355        if ($piece['piece'] != 'K' && $piece['piece'] != 'P') {
1356            $others = $this->_getAllPieceSquares($piece['piece'],
1357                                                 $piece['color'], $from);
1358        }
1359        $disambiguate = '';
1360        $ambiguous = array();
1361        if (count($others)) {
1362            foreach ($others as $square) {
1363                if (in_array($to, $this->getPossibleMoves($piece['piece'], $square,
1364                                                          $piece['color']))) {
1365                    // other pieces can move to this square - need to disambiguate
1366                    $ambiguous[] = $square;
1367                }
1368            }
1369        }
1370        if (count($ambiguous) == 1) {
1371            if ($ambiguous[0]{0} != $from{0}) {
1372                $disambiguate = $from{0};
1373            } elseif ($ambiguous[0]{1} != $from{1}) {
1374                $disambiguate = $from{1};
1375            } else {
1376                $disambiguate = $from;
1377            }
1378        } elseif (count($ambiguous)) {
1379            $disambiguate = $from;
1380        }
1381        if ($piece['piece'] == 'P') {
1382            if ($from{0} != $to{0}) {
1383                $SAN = $from{0};
1384            }
1385        } else {
1386            $SAN = $piece['piece'];
1387        }
1388        $SAN .= $disambiguate;
1389        if ($this->_board[$to] != $to) {
1390            $SAN .= 'x';
1391        } else {
1392            if ($piece['piece'] == 'P' && $to == $this->_enPassantSquare) {
1393                $SAN .= 'x';
1394            }
1395        }
1396        $SAN .= $to;
1397        if ($piece['piece'] == 'P' && ($to{1} == '1' || $to{1} == '8')) {
1398            $SAN .= '=' . $promote;
1399        }
1400        return $SAN;
1401    }
1402
1403    /**
1404     * Get a list of all possible theoretical squares a piece of this nature
1405     * and color could move to with the current board and game setup.
1406     *
1407     * This method will return all valid moves without determining the presence
1408     * of check
1409     * @param K|P|Q|R|B|N Piece name
1410     * @param string [a-h][1-8] algebraic location of the piece
1411     * @param B|W color of the piece
1412     * @param boolean Whether to return shortcut king moves for castling
1413     * @return array|PEAR_Error
1414     * @throws GAMES_CHESS_ERROR_INVALID_COLOR
1415     * @throws GAMES_CHESS_ERROR_INVALID_SQUARE
1416     * @throws GAMES_CHESS_ERROR_INVALID_PIECE
1417     */
1418    function getPossibleMoves($piece, $square, $color = null, $returnCastleMoves = true)
1419    {
1420        if (is_null($color)) {
1421            $color = $this->_move;
1422        }
1423        $color = strtoupper($color);
1424        if (!in_array($color, array('W', 'B'))) {
1425            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1426                array('color' => $color));
1427        }
1428        if (!preg_match('/^[a-h][1-8]$/', $square)) {
1429            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1430                array('square' => $square));
1431        }
1432        $piece = strtoupper($piece);
1433        if (!in_array($piece, array('K', 'Q', 'B', 'N', 'R', 'P'))) {
1434            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_PIECE,
1435                array('piece' => $piece));
1436        }
1437        switch ($piece) {
1438            case 'K' :
1439                return $this->getPossibleKingMoves($square, $color, $returnCastleMoves);
1440            break;
1441            case 'Q' :
1442                return $this->getPossibleQueenMoves($square, $color);
1443            break;
1444            case 'B' :
1445                return $this->getPossibleBishopMoves($square, $color);
1446            break;
1447            case 'N' :
1448                return $this->getPossibleKnightMoves($square, $color);
1449            break;
1450            case 'R' :
1451                return $this->getPossibleRookMoves($square, $color);
1452            break;
1453            case 'P' :
1454                return $this->getPossiblePawnMoves($square, $color);
1455            break;
1456        }
1457    }
1458
1459    /**
1460     * Get the set of squares that are diagonals from this square on an empty board.
1461     *
1462     * WARNING: assumes valid input
1463     * @param string [a-h][1-8]
1464     * @param boolean if true, simply returns an array of all squares
1465     * @return array Format:
1466     *
1467     * <pre>
1468     * array(
1469     *   'NE' => array(square, square),
1470     *   'NW' => array(square, square),
1471     *   'SE' => array(square, square),
1472     *   'SW' => array(square, square)
1473     * )
1474     * </pre>
1475     *
1476     * Think of the diagonal directions as on a map.  squares are listed with
1477     * closer squares first
1478     */
1479    function _getDiagonals($square, $returnFlatArray = false)
1480    {
1481        $nw = ($square{0} != 'a') && ($square{1} != '8');
1482        $ne = ($square{0} != 'h') && ($square{1} != '8');
1483        $sw = ($square{0} != 'a') && ($square{1} != '1');
1484        $se = ($square{0} != 'h') && ($square{1} != '1');
1485        if ($nw) {
1486            $nw = array();
1487            $i = $square;
1488            while(ord($i{0}) > ord('a') && ord($i{1}) < ord('8')) {
1489                $i{0} = chr(ord($i{0}) - 1);
1490                $i{1} = chr(ord($i{1}) + 1);
1491                $nw[] = $i;
1492            }
1493        }
1494        if ($ne) {
1495            $ne = array();
1496            $i = $square;
1497            while(ord($i{0}) < ord('h') && ord($i{1}) < ord('8')) {
1498                $i{0} = chr(ord($i{0}) + 1);
1499                $i{1} = chr(ord($i{1}) + 1);
1500                $ne[] = $i;
1501            }
1502        }
1503        if ($sw) {
1504            $sw = array();
1505            $i = $square;
1506            while(ord($i{0}) > ord('a') && ord($i{1}) > ord('1')) {
1507                $i{0} = chr(ord($i{0}) - 1);
1508                $i{1} = chr(ord($i{1}) - 1);
1509                $sw[] = $i;
1510            }
1511        }
1512        if ($se) {
1513            $se = array();
1514            $i = $square;
1515            while(ord($i{0}) < ord('h') && ord($i{1}) > ord('1')) {
1516                $i{0} = chr(ord($i{0}) + 1);
1517                $i{1} = chr(ord($i{1}) - 1);
1518                $se[] = $i;
1519            }
1520        }
1521        if ($returnFlatArray) {
1522            if (!$nw) {
1523                $nw = array();
1524            }
1525            if (!$sw) {
1526                $sw = array();
1527            }
1528            if (!$ne) {
1529                $ne = array();
1530            }
1531            if (!$se) {
1532                $se = array();
1533            }
1534            return array_merge($ne, array_merge($nw, array_merge($se, $sw)));
1535        }
1536        return array('NE' => $ne, 'NW' => $nw, 'SE' => $se, 'SW' => $sw);
1537    }
1538
1539    /**
1540     * Get the set of squares that are diagonals from this square on an empty board.
1541     *
1542     * WARNING: assumes valid input
1543     * @param string [a-h][1-8]
1544     * @param boolean if true, simply returns an array of all squares
1545     * @return array Format:
1546     *
1547     * <pre>
1548     * array(
1549     *   'N' => array(square, square),
1550     *   'E' => array(square, square),
1551     *   'S' => array(square, square),
1552     *   'W' => array(square, square)
1553     * )
1554     * </pre>
1555     *
1556     * Think of the horizontal directions as on a map.  squares are listed with
1557     * closer squares first
1558     * @access protected
1559     */
1560    function _getRookSquares($square, $returnFlatArray = false)
1561    {
1562        $n = ($square{1} != '8');
1563        $e = ($square{0} != 'h');
1564        $s = ($square{1} != '1');
1565        $w = ($square{0} != 'a');
1566        if ($n) {
1567            $n = array();
1568            $i = $square;
1569            while(ord($i{1}) < ord('8')) {
1570                $i{1} = chr(ord($i{1}) + 1);
1571                $n[] = $i;
1572            }
1573        }
1574        if ($e) {
1575            $e = array();
1576            $i = $square;
1577            while(ord($i{0}) < ord('h')) {
1578                $i{0} = chr(ord($i{0}) + 1);
1579                $e[] = $i;
1580            }
1581        }
1582        if ($s) {
1583            $s = array();
1584            $i = $square;
1585            while(ord($i{1}) > ord('1')) {
1586                $i{1} = chr(ord($i{1}) - 1);
1587                $s[] = $i;
1588            }
1589        }
1590        if ($w) {
1591            $w = array();
1592            $i = $square;
1593            while(ord($i{0}) > ord('a')) {
1594                $i{0} = chr(ord($i{0}) - 1);
1595                $w[] = $i;
1596            }
1597        }
1598        if ($returnFlatArray) {
1599            if (!$n) {
1600                $n = array();
1601            }
1602            if (!$s) {
1603                $s = array();
1604            }
1605            if (!$e) {
1606                $e = array();
1607            }
1608            if (!$w) {
1609                $w = array();
1610            }
1611            return array_merge($n, array_merge($s, array_merge($e, $w)));
1612        }
1613        return array('N' => $n, 'E' => $e, 'S' => $s, 'W' => $w);
1614    }
1615
1616    /**
1617     * Get all the squares a queen could go to on a blank board
1618     *
1619     * WARNING: assumes valid input
1620     * @return array combines contents of {@link _getRookSquares()} and
1621     *               {@link _getDiagonals()}
1622     * @param string [a-h][1-8]
1623     * @param boolean if true, simply returns an array of all squares
1624     * @access protected
1625     */
1626    function _getQueenSquares($square, $returnFlatArray = false)
1627    {
1628        return array_merge($this->_getRookSquares($square, $returnFlatArray),
1629                           $this->_getDiagonals($square, $returnFlatArray));
1630    }
1631
1632    /**
1633     * Get all the squares a knight could move to on an empty board
1634     *
1635     * WARNING: assumes valid input
1636     * @param string [a-h][1-8]
1637     * @param boolean if true, simply returns an array of all squares
1638     * @return array Returns an array of all the squares organized by compass
1639     *               point, that a knight can go to.  These squares may be indexed
1640     *               by any of WNW, NNW, NNE, ENE, ESE, SSE, SSW or WSW, unless
1641     *               $returnFlatArray is true, in which case an array of squares
1642     *               is returned
1643     * @access protected
1644     */
1645    function _getKnightSquares($square, $returnFlatArray = false)
1646    {
1647        $squares = array();
1648        // west-northwest square
1649        if (ord($square{0}) > ord('b') && $square{1} < 8) {
1650            $squares['WNW'] = chr(ord($square{0}) - 2) . ($square{1} + 1);
1651        }
1652        // north-northwest square
1653        if (ord($square{0}) > ord('a') && $square{1} < 7) {
1654            $squares['NNW'] = chr(ord($square{0}) - 1) . ($square{1} + 2);
1655        }
1656        // north-northeast square
1657        if (ord($square{0}) < ord('h') && $square{1} < 7) {
1658            $squares['NNE'] = chr(ord($square{0}) + 1) . ($square{1} + 2);
1659        }
1660        // east-northeast square
1661        if (ord($square{0}) < ord('g') && $square{1} < 8) {
1662            $squares['ENE'] = chr(ord($square{0}) + 2) . ($square{1} + 1);
1663        }
1664        // east-southeast square
1665        if (ord($square{0}) < ord('g') && $square{1} > 1) {
1666            $squares['ESE'] = chr(ord($square{0}) + 2) . ($square{1} - 1);
1667        }
1668        // south-southeast square
1669        if (ord($square{0}) < ord('h') && $square{1} > 2) {
1670            $squares['SSE'] = chr(ord($square{0}) + 1) . ($square{1} - 2);
1671        }
1672        // south-southwest square
1673        if (ord($square{0}) > ord('a') && $square{1} > 2) {
1674            $squares['SSW'] = chr(ord($square{0}) - 1) . ($square{1} - 2);
1675        }
1676        // west-southwest square
1677        if (ord($square{0}) > ord('b') && $square{1} > 1) {
1678            $squares['WSW'] = chr(ord($square{0}) - 2) . ($square{1} - 1);
1679        }
1680        if ($returnFlatArray) {
1681            return array_values($squares);
1682        }
1683        return $squares;
1684    }
1685
1686    /**
1687     * Get a list of all the squares a king could castle to on an empty board
1688     *
1689     * WARNING: assumes valid input
1690     * @param string [a-h][1-8]
1691     * @return array
1692     * @access protected
1693     * @since 0.7alpha
1694     */
1695    function _getCastleSquares($square)
1696    {
1697        $ret = array();
1698        if ($this->_move == 'W') {
1699            if ($square == 'e1' && $this->_WCastleK) {
1700                $ret[] = 'g1';
1701            }
1702            if ($square == 'e1' && $this->_WCastleQ) {
1703                $ret[] = 'c1';
1704            }
1705
1706        } else {
1707            if ($square == 'e8' && $this->_BCastleK) {
1708                $ret[] = 'g8';
1709            }
1710            if ($square == 'e8' && $this->_BCastleQ) {
1711                $ret[] = 'c8';
1712            }
1713        }
1714        return $ret;
1715    }
1716
1717    /**
1718     * Get a list of all the squares a king could move to on an empty board
1719     *
1720     * WARNING: assumes valid input
1721     * @param string [a-h][1-8]
1722     * @return array
1723     * @access protected
1724     */
1725    function _getKingSquares($square)
1726    {
1727        $squares = array();
1728        if (ord($square{0}) - ord('a')) {
1729            $squares[] = chr(ord($square{0}) - 1) . $square{1};
1730            if ($square{1} < 8) {
1731                $squares[] = chr(ord($square{0}) - 1) . ($square{1} + 1);
1732            }
1733            if ($square{1} > 1) {
1734                $squares[] = chr(ord($square{0}) - 1) . ($square{1} - 1);
1735            }
1736        }
1737        if (ord($square{0}) - ord('h')) {
1738            $squares[] = chr(ord($square{0}) + 1) . $square{1};
1739            if ($square{1} < 8) {
1740                $squares[] = chr(ord($square{0}) + 1) . ($square{1} + 1);
1741            }
1742            if ($square{1} > 1) {
1743                $squares[] = chr(ord($square{0}) + 1) . ($square{1} - 1);
1744            }
1745        }
1746        if ($square{1} > 1) {
1747            $squares[] = $square{0} . ($square{1} - 1);
1748        }
1749        if ($square{1} < 8) {
1750            $squares[] = $square{0} . ($square{1} + 1);
1751        }
1752        return $squares;
1753    }
1754
1755    /**
1756     * Get the location of all pieces on the board of a certain color
1757     *
1758     * Default is the color that is about to move
1759     * @param W|B
1760     * @return array|PEAR_Error
1761     * @throws GAMES_CHESS_ERROR_INVALID_COLOR
1762     */
1763    function getPieceLocations($color = null)
1764    {
1765        if (is_null($color)) {
1766            $color = $this->_move;
1767        }
1768        $color = strtoupper($color);
1769        if (!in_array($color, array('W', 'B'))) {
1770            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1771                array('color' => $color));
1772        }
1773        return $this->_getAllPieceLocations($color);
1774    }
1775
1776    /**
1777     * Get the location of every piece on the board of color $color
1778     * @param W|B color of pieces to check
1779     * @return array
1780     * @abstract
1781     * @access protected
1782     */
1783    function _getAllPieceLocations($color)
1784    {
1785        trigger_error('Error: do not use abstract Games_Chess class', E_USER_ERROR);
1786    }
1787
1788    /**
1789     * Get all legal Knight moves (checking of the king is not taken into account)
1790     * @param string [a-h][1-8] Location of piece
1791     * @param W|B color of piece, or null to use current piece to move
1792     * @return array
1793     */
1794    function getPossibleKnightMoves($square, $color = null)
1795    {
1796        if (is_null($color)) {
1797            $color = $this->_move;
1798        }
1799        $color = strtoupper($color);
1800        if (!in_array($color, array('W', 'B'))) {
1801            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1802                array('color' => $color));
1803        }
1804        if (!preg_match('/^[a-h][1-8]$/', $square)) {
1805            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1806                array('square' => $square));
1807        }
1808        $allmoves = $this->_getKnightSquares($square);
1809        $mypieces = $this->getPieceLocations($color);
1810        return array_values(array_diff($allmoves, $mypieces));
1811    }
1812
1813    /**
1814     * Get all legal Bishop moves (checking of the king is not taken into account)
1815     * @param string [a-h][1-8] Location of piece
1816     * @param W|B color of piece, or null to use current piece to move
1817     * @return array
1818     */
1819    function getPossibleBishopMoves($square, $color = null)
1820    {
1821        if (is_null($color)) {
1822            $color = $this->_move;
1823        }
1824        $color = strtoupper($color);
1825        if (!in_array($color, array('W', 'B'))) {
1826            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1827                array('color' => $color));
1828        }
1829        if (!preg_match('/^[a-h][1-8]$/', $square)) {
1830            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1831                array('square' => $square));
1832        }
1833        $allmoves = $this->_getDiagonals($square);
1834        $mypieces = $this->getPieceLocations($color);
1835        foreach($mypieces as $loc) {
1836            // go through the diagonals, and remove squares behind our own pieces
1837            // and also remove the piece's square
1838            // as bishops cannot pass through any pieces.
1839            if (is_array($allmoves['NW']) && in_array($loc, $allmoves['NW'])) {
1840                $pos = array_search($loc, $allmoves['NW']);
1841                $allmoves['NW'] = array_slice($allmoves['NW'], 0, $pos);
1842            }
1843            if (is_array($allmoves['NE']) && in_array($loc, $allmoves['NE'])) {
1844                $pos = array_search($loc, $allmoves['NE']);
1845                $allmoves['NE'] = array_slice($allmoves['NE'], 0, $pos);
1846            }
1847            if (is_array($allmoves['SE']) && in_array($loc, $allmoves['SE'])) {
1848                $pos = array_search($loc, $allmoves['SE']);
1849                $allmoves['SE'] = array_slice($allmoves['SE'], 0, $pos);
1850            }
1851            if (is_array($allmoves['SW']) && in_array($loc, $allmoves['SW'])) {
1852                $pos = array_search($loc, $allmoves['SW']);
1853                $allmoves['SW'] = array_slice($allmoves['SW'], 0, $pos);
1854            }
1855        }
1856        $enemypieces = $this->getPieceLocations($color == 'W' ? 'B' : 'W');
1857        foreach($enemypieces as $loc) {
1858            // go through the diagonals, and remove squares behind enemy pieces
1859            // and include the piece's square, since we can capture it
1860            // but bishops cannot pass through any pieces.
1861            if (is_array($allmoves['NW']) && in_array($loc, $allmoves['NW'])) {
1862                $pos = array_search($loc, $allmoves['NW']);
1863                $allmoves['NW'] = array_slice($allmoves['NW'], 0, $pos + 1);
1864            }
1865            if (is_array($allmoves['NE']) && in_array($loc, $allmoves['NE'])) {
1866                $pos = array_search($loc, $allmoves['NE']);
1867                $allmoves['NE'] = array_slice($allmoves['NE'], 0, $pos + 1);
1868            }
1869            if (is_array($allmoves['SE']) && in_array($loc, $allmoves['SE'])) {
1870                $pos = array_search($loc, $allmoves['SE']);
1871                $allmoves['SE'] = array_slice($allmoves['SE'], 0, $pos + 1);
1872            }
1873            if (is_array($allmoves['SW']) && in_array($loc, $allmoves['SW'])) {
1874                $pos = array_search($loc, $allmoves['SW']);
1875                $allmoves['SW'] = array_slice($allmoves['SW'], 0, $pos + 1);
1876            }
1877        }
1878        $newmoves = array();
1879        foreach($allmoves as $key => $value) {
1880            if (!$value) {
1881                continue;
1882            }
1883            $newmoves = array_merge($newmoves, $value);
1884        }
1885        return array_values(array_diff($newmoves, $mypieces));
1886    }
1887
1888    /**
1889     * Get all legal Rook moves (checking of the king is not taken into account)
1890     * @param string [a-h][1-8] Location of piece
1891     * @param W|B color of piece, or null to use current piece to move
1892     * @return array
1893     */
1894    function getPossibleRookMoves($square, $color = null)
1895    {
1896        if (is_null($color)) {
1897            $color = $this->_move;
1898        }
1899        $color = strtoupper($color);
1900        if (!in_array($color, array('W', 'B'))) {
1901            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1902                array('color' => $color));
1903        }
1904        if (!preg_match('/^[a-h][1-8]$/', $square)) {
1905            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
1906                array('square' => $square));
1907        }
1908        $allmoves = $this->_getRookSquares($square);
1909        $mypieces = $this->getPieceLocations($color);
1910        foreach($mypieces as $loc) {
1911            // go through the rook squares, and remove squares behind our own pieces
1912            // and also remove the piece's square
1913            // as rooks cannot pass through any pieces.
1914            if (is_array($allmoves['N']) && in_array($loc, $allmoves['N'])) {
1915                $pos = array_search($loc, $allmoves['N']);
1916                $allmoves['N'] = array_slice($allmoves['N'], 0, $pos);
1917            }
1918            if (is_array($allmoves['E']) && in_array($loc, $allmoves['E'])) {
1919                $pos = array_search($loc, $allmoves['E']);
1920                $allmoves['E'] = array_slice($allmoves['E'], 0, $pos);
1921            }
1922            if (is_array($allmoves['S']) && in_array($loc, $allmoves['S'])) {
1923                $pos = array_search($loc, $allmoves['S']);
1924                $allmoves['S'] = array_slice($allmoves['S'], 0, $pos);
1925            }
1926            if (is_array($allmoves['W']) && in_array($loc, $allmoves['W'])) {
1927                $pos = array_search($loc, $allmoves['W']);
1928                $allmoves['W'] = array_slice($allmoves['W'], 0, $pos);
1929            }
1930        }
1931        $enemypieces = $this->getPieceLocations($color == 'W' ? 'B' : 'W');
1932        foreach($enemypieces as $loc) {
1933            // go through the rook squares, and remove squares behind enemy pieces
1934            // and include the piece's square, since we can capture it
1935            // but rooks cannot pass through any pieces.
1936            if (is_array($allmoves['N']) && in_array($loc, $allmoves['N'])) {
1937                $pos = array_search($loc, $allmoves['N']);
1938                $allmoves['N'] = array_slice($allmoves['N'], 0, $pos + 1);
1939            }
1940            if (is_array($allmoves['E']) && in_array($loc, $allmoves['E'])) {
1941                $pos = array_search($loc, $allmoves['E']);
1942                $allmoves['E'] = array_slice($allmoves['E'], 0, $pos + 1);
1943            }
1944            if (is_array($allmoves['S']) && in_array($loc, $allmoves['S'])) {
1945                $pos = array_search($loc, $allmoves['S']);
1946                $allmoves['S'] = array_slice($allmoves['S'], 0, $pos + 1);
1947            }
1948            if (is_array($allmoves['W']) && in_array($loc, $allmoves['W'])) {
1949                $pos = array_search($loc, $allmoves['W']);
1950                $allmoves['W'] = array_slice($allmoves['W'], 0, $pos + 1);
1951            }
1952        }
1953        $newmoves = array();
1954        foreach($allmoves as $key => $value) {
1955            if (!$value) {
1956                continue;
1957            }
1958            $newmoves = array_merge($newmoves, $value);
1959        }
1960        return array_values(array_diff($newmoves, $mypieces));
1961    }
1962
1963    /**
1964     * Get all legal Queen moves (checking of the king is not taken into account)
1965     * @param string [a-h][1-8] Location of piece
1966     * @param W|B color of piece, or null to use current piece to move
1967     * @return array
1968     */
1969    function getPossibleQueenMoves($square, $color = null)
1970    {
1971        $a = $this->getPossibleRookMoves($square, $color);
1972        if ($this->isError($a)) {
1973            return $a;
1974        }
1975        $b = $this->getPossibleBishopMoves($square, $color);
1976        if ($this->isError($b)) {
1977            return $b;
1978        }
1979        return array_merge($a, $b);
1980    }
1981
1982    /**
1983     * Get all legal Pawn moves (checking of the king is not taken into account)
1984     * @param string [a-h][1-8] Location of piece
1985     * @param W|B color of piece, or null to use current piece to move
1986     * @return array
1987     */
1988    function getPossiblePawnMoves($square, $color = null, $enpassant = null)
1989    {
1990        if (is_null($color)) {
1991            $color = $this->_move;
1992        }
1993        $color = strtoupper($color);
1994        if (!in_array($color, array('W', 'B'))) {
1995            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
1996                array('color' => $color));
1997        }
1998        if (!preg_match('/^[a-h][1-8]$/', $square)) {
1999            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
2000                array('square' => $square));
2001        }
2002        if (is_null($enpassant)) {
2003            $enpassant = $this->_enPassantSquare;
2004        }
2005        $mypieces = $this->getPieceLocations($color);
2006        $enemypieces = $this->getPieceLocations($color == 'W' ? 'B' : 'W');
2007        $allmoves = array();
2008        if ($color == 'W') {
2009            $dbl = '2';
2010            $direction = 1;
2011            // en passant calculation
2012            if ($square{1} == '5' && in_array(ord($enpassant{0}) - ord($square{0}),
2013                                              array(1, -1))) {
2014                if (in_array(chr(ord($square{0}) - 1) . 5,
2015                             $enemypieces)) {
2016                    $allmoves[] = chr(ord($square{0}) - 1) . 6;
2017                }
2018                if (in_array(chr(ord($square{0}) + 1) . 5,
2019                             $enemypieces)) {
2020                    $allmoves[] = chr(ord($square{0}) + 1) . 6;
2021                }
2022            }
2023        } else {
2024            $dbl = '7';
2025            $direction = -1;
2026            // en passant calculation
2027            if ($square{1} == '4' && in_array(ord($enpassant{0}) - ord($square{0}),
2028                                              array(1, -1))) {
2029                if (in_array(chr(ord($square{0}) - 1) . 4,
2030                             $enemypieces)) {
2031                    $allmoves[] = chr(ord($square{0}) - 1) . 3;
2032                }
2033                if (in_array(chr(ord($square{0}) + 1) . 4,
2034                             $enemypieces)) {
2035                    $allmoves[] = chr(ord($square{0}) + 1) . 3;
2036                }
2037            }
2038        }
2039        if (!in_array($square{0} . ($square{1} + $direction), $mypieces) &&
2040            !in_array($square{0} . ($square{1} + $direction), $enemypieces))
2041        {
2042            $allmoves[] = $square{0} . ($square{1} + $direction);
2043        }
2044        if (count($allmoves) && $square{1} == $dbl) {
2045            if (!in_array($square{0} . ($square{1} + 2 * $direction), $mypieces) &&
2046                !in_array($square{0} . ($square{1} + 2 * $direction), $enemypieces))
2047            {
2048                $allmoves[] = $square{0} . ($square{1} + 2 * $direction);
2049            }
2050        }
2051        if (in_array(chr(ord($square{0}) - 1) . ($square{1} + $direction),
2052                     $enemypieces)) {
2053            $allmoves[] = chr(ord($square{0}) - 1) . ($square{1} + $direction);
2054        }
2055        if (in_array(chr(ord($square{0}) + 1) . ($square{1} + $direction),
2056                     $enemypieces)) {
2057            $allmoves[] = chr(ord($square{0}) + 1) . ($square{1} + $direction);
2058        }
2059        return $allmoves;
2060    }
2061
2062    /**
2063     * Get all legal King moves (checking of the king is not taken into account)
2064     * @param string [a-h][1-8] Location of piece
2065     * @param W|B color of piece, or null to use current piece to move
2066     * @return array
2067     * @since 0.7alpha castling is possible by moving the king to the destination square
2068     */
2069    function getPossibleKingMoves($square, $color = null, $returnCastleMoves = true)
2070    {
2071        if (is_null($color)) {
2072            $color = $this->_move;
2073        }
2074        $color = strtoupper($color);
2075        if (!in_array($color, array('W', 'B'))) {
2076            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_COLOR,
2077                array('color' => $color));
2078        }
2079        if (!preg_match('/^[a-h][1-8]$/', $square)) {
2080            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
2081                array('square' => $square));
2082        }
2083        $newret = $castleret = array();
2084        $ret = $this->_getKingSquares($square);
2085        if ($returnCastleMoves) {
2086            $castleret = $this->_getCastleSquares($square);
2087        }
2088        $mypieces = $this->getPieceLocations($color);
2089        foreach ($ret as $square) {
2090            if (!in_array($square, $mypieces)) {
2091                $newret[] = $square;
2092            }
2093        }
2094        return array_merge($newret, $castleret);
2095    }
2096
2097    /**
2098     * Return the color of a square (black or white)
2099     * @param string [a-h][1-8]
2100     * @access protected
2101     * @return B|W
2102     */
2103    function _getDiagonalColor($square)
2104    {
2105        $map = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5, 'f' => 6,
2106            'g' => 7, 'h' => 8);
2107        $rank = $map[$square{0}];
2108        $file = $square{1};
2109        $color = ($rank + $file) % 2;
2110        return $color ? 'W' : 'B';
2111    }
2112
2113    function getDiagonalColor($square)
2114    {
2115        if (!preg_match('/^[a-h][1-8]$/', $square)) {
2116            return $this->raiseError(GAMES_CHESS_ERROR_INVALID_SQUARE,
2117                array('square' => $square));
2118        }
2119        return $this->_getDiagonalColor($square);
2120    }
2121
2122    /**
2123     * Get all the squares between an attacker and the king where another
2124     * piece can interpose, or capture the checking piece
2125     *
2126     * @param string algebraic square of the checking piece
2127     * @param string algebraic square of the king
2128     */
2129    function _getPathToKing($checkee, $king)
2130    {
2131        if ($this->_isKnight($this->_board[$checkee])) {
2132            return array($checkee);
2133        } else {
2134            $path = array();
2135            // get all the paths
2136            $kingpaths = $this->_getQueenSquares($king);
2137            foreach ($kingpaths as $subpath) {
2138                if (!$subpath) {
2139                    continue;
2140                }
2141                if (in_array($checkee, $subpath)) {
2142                    foreach ($subpath as $square) {
2143                        $path[] = $square;
2144                        if ($square == $checkee) {
2145                            return $path;
2146                        }
2147                    }
2148                }
2149            }
2150        }
2151    }
2152
2153    /**
2154     * @param integer error code from {@link Chess.php}
2155     * @param array associative array of additional error message data
2156     * @uses PEAR::raiseError()
2157     * @return PEAR_Error
2158     */
2159    function raiseError($code, $extra = array())
2160    {
2161        require_once 'PEAR.php';
2162        return PEAR::raiseError($this->getMessage($code, $extra), $code,
2163            null, null, $extra);
2164    }
2165
2166    /**
2167     * Get an error message from the code
2168     *
2169     * Future versions of this method will be multi-language
2170     * @return string
2171     * @param integer Error code
2172     * @param array extra information to pass for error message creation
2173     */
2174    function getMessage($code, $extra)
2175    {
2176        $messages = array(
2177            GAMES_CHESS_ERROR_INVALID_SAN =>
2178                '"%pgn%" is not a valid algebraic move',
2179            GAMES_CHESS_ERROR_FEN_COUNT =>
2180                'Invalid FEN - "%fen%" has %sections% fields, 6 is required',
2181            GAMES_CHESS_ERROR_EMPTY_FEN =>
2182                'Invalid FEN - "%fen%" has an empty field at index %section%',
2183            GAMES_CHESS_ERROR_FEN_TOOMUCH =>
2184                'Invalid FEN - "%fen%" has too many pieces for a chessboard',
2185            GAMES_CHESS_ERROR_FEN_TOMOVEWRONG =>
2186                'Invalid FEN - "%fen%" has invalid to-move indicator, must be "w" or "b"',
2187            GAMES_CHESS_ERROR_FEN_CASTLETOOLONG =>
2188                'Invalid FEN - "%fen%" the castling indicator (KQkq) is too long',
2189            GAMES_CHESS_ERROR_FEN_CASTLEWRONG =>
2190                'Invalid FEN - "%fen%" the castling indicator "%castle%" is invalid',
2191            GAMES_CHESS_ERROR_FEN_INVALID_EP =>
2192                'Invalid FEN - "%fen%" the en passant square indicator "%enpassant%" is invalid',
2193            GAMES_CHESS_ERROR_FEN_INVALID_PLY =>
2194                'Invalid FEN - "%fen%" the half-move ply count "%ply%" is not a number',
2195            GAMES_CHESS_ERROR_FEN_INVALID_MOVENUMBER =>
2196                'Invalid FEN - "%fen%" the move number "%movenumber%" is not a number',
2197            GAMES_CHESS_ERROR_IN_CHECK =>
2198                'The king is in check and that move does not prevent check',
2199            GAMES_CHESS_ERROR_CANT_CK =>
2200                'Can\'t castle kingside, either the king or rook has moved',
2201            GAMES_CHESS_ERROR_CK_PIECES_IN_WAY =>
2202                'Can\'t castle kingside, pieces are in the way',
2203            GAMES_CHESS_ERROR_CANT_CQ =>
2204                'Can\'t castle queenside, either the king or rook has moved',
2205            GAMES_CHESS_ERROR_CQ_PIECES_IN_WAY =>
2206                'Can\'t castle queenside, pieces are in the way',
2207            GAMES_CHESS_ERROR_CASTLE_WOULD_CHECK =>
2208                'Can\'t castle, it would put the king in check',
2209            GAMES_CHESS_ERROR_MOVE_WOULD_CHECK =>
2210                'That move would put the king in check',
2211            GAMES_CHESS_ERROR_STILL_IN_CHECK =>
2212                'The move does not remove the check on the king',
2213            GAMES_CHESS_ERROR_CANT_CAPTURE_OWN =>
2214                'Cannot capture your own pieces',
2215            GAMES_CHESS_ERROR_NO_PIECE =>
2216                'There is no piece on square %square%',
2217            GAMES_CHESS_ERROR_WRONG_COLOR =>
2218                'The piece on %square% is not your piece',
2219            GAMES_CHESS_ERROR_CANT_MOVE_THAT_WAY =>
2220                'The piece on %from% cannot move to %to%',
2221            GAMES_CHESS_ERROR_MULTIPIECE =>
2222                'Too many %color% %piece%s',
2223            GAMES_CHESS_ERROR_FEN_MULTIPIECE =>
2224                'Invalid FEN - "%fen%" Too many %color% %piece%s',
2225            GAMES_CHESS_ERROR_DUPESQUARE =>
2226                '%dpiece% already occupies square %square%, cannot be replaced by %piece%',
2227            GAMES_CHESS_ERROR_FEN_INVALIDPIECE =>
2228                'Invalid FEN - "%fen%" the character "%fenchar%" is not a valid piece, separator or number',
2229            GAMES_CHESS_ERROR_FEN_TOOLITTLE =>
2230                'Invalid FEN - "%fen%" has too few pieces for a chessboard',
2231            GAMES_CHESS_ERROR_INVALID_COLOR =>
2232                '"%color%" is not a valid piece color, try W or B',
2233            GAMES_CHESS_ERROR_INVALID_SQUARE =>
2234                '"%square%" is not a valid square, must be between a1 and h8',
2235            GAMES_CHESS_ERROR_INVALID_PIECE =>
2236                '"%piece%" is not a valid piece, must be P, Q, R, N, K or B',
2237            GAMES_CHESS_ERROR_INVALID_PROMOTE =>
2238                '"%piece%" is not a valid promotion piece, must be Q, R, N or B',
2239            GAMES_CHESS_ERROR_TOO_AMBIGUOUS =>
2240                '"%san%" does not resolve ambiguity between %piece%s on %squares%',
2241            GAMES_CHESS_ERROR_NOPIECE_CANDOTHAT =>
2242                'There are no %color% pieces on the board that can do "%san%"',
2243            GAMES_CHESS_ERROR_MOVE_MUST_CAPTURE =>
2244                'Capture is possible, "%san%" does not capture',
2245            GAMES_CHESS_ERROR_NOPIECES_TOPLACE =>
2246                'There are no captured %color% %piece%s available to place',
2247            GAMES_CHESS_ERROR_PIECEINTHEWAY =>
2248                'There is already a piece on %square%, cannot place another there',
2249            GAMES_CHESS_ERROR_CANT_PLACE_18 =>
2250                'Placing a piece on the first or back rank is illegal (%san%)',
2251        );
2252        $message = $messages[$code];
2253        foreach ($extra as $key => $value) {
2254            if (strpos($key, 'piece') !== false) {
2255                switch(strtoupper($value)) {
2256                    case 'R' :
2257                        $value = 'Rook';
2258                    break;
2259                    case 'Q' :
2260                        $value = 'Queen';
2261                    break;
2262                    case 'P' :
2263                        $value = 'Pawn';
2264                    break;
2265                    case 'B' :
2266                        $value = 'Bishop';
2267                    break;
2268                    case 'K' :
2269                        $value = 'King';
2270                    break;
2271                    case 'N' :
2272                        $value = 'Knight';
2273                    break;
2274                }
2275            }
2276            if ($key == 'color') {
2277                switch($value) {
2278                    case 'W' :
2279                        $value = 'White';
2280                    break;
2281                    case 'B' :
2282                        $value = 'Black';
2283                    break;
2284                }
2285            }
2286            $message = str_replace('%'.$key.'%', $value, $message);
2287        }
2288        return $message;
2289    }
2290
2291    /**
2292     * Determines whether the data returned from a method is a PEAR-related
2293     * error class
2294     * @param mixed
2295     * @return boolean
2296     */
2297    function isError($err)
2298    {
2299        return is_a($err, 'PEAR_Error');
2300    }
2301
2302    /**
2303     * Begin a chess piece transaction
2304     *
2305     * Transactions are used to attempt moves that may be revoked later, especially
2306     * in methods like {@link inCheckMate()}
2307     */
2308    function startTransaction()
2309    {
2310        $state = get_object_vars($this);
2311        unset($state['_saveState']);
2312        if (!is_array($this->_saveState)) {
2313            $this->_saveState = array();
2314        }
2315        array_push($this->_saveState, $state);
2316    }
2317
2318    /**
2319     * Set the state of the chess game
2320     *
2321     * WARNING: this resets the state without any validation.
2322     * @param array
2323     */
2324    function setState($state)
2325    {
2326        foreach($state as $name => $value) {
2327            $this->$name = $value;
2328        }
2329    }
2330
2331    /**
2332     * Get the current state of the chess game
2333     *
2334     * Use this in conjunction with setState
2335     * @param array
2336     */
2337    function getState()
2338    {
2339        return get_object_vars($this);
2340    }
2341
2342    /**
2343     * Remove any possibility of undo.
2344     */
2345    function commitTransaction()
2346    {
2347        array_pop($this->_saveState);
2348    }
2349
2350    /**
2351     * Undo any changes to state since {@link startTransaction()} was first used
2352     */
2353    function rollbackTransaction()
2354    {
2355        $vars = array_pop($this->_saveState);
2356        foreach($vars as $name => $value) {
2357            $this->$name = $value;
2358        }
2359    }
2360}
2361?>
2362