src/hlvariant/chess/movegenerator.h

   1 /*
   2   Copyright (c) 2007 Paolo Capriotti <p.capriotti@gmail.com>
   3             (c) 2007 Maurizio Monge <maurizio.monge@kdemail.net>
   4
   5   This program is free software; you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation; either version 2 of the License, or
   8   (at your option) any later version.
   9 */
  10
  11 #ifndef HLVARIANT__CHESS__MOVEGENERATOR_H
  12 #define HLVARIANT__CHESS__MOVEGENERATOR_H
  13
  14 #include "legalitycheck.h"
  15
  16 namespace HLVariant {
  17 namespace Chess {
  18
  19 template <typename _LegalityCheck>
  20 class MoveGenerator {
  21 public:
  22   typedef _LegalityCheck LegalityCheck;
  23   typedef typename LegalityCheck::GameState GameState;
  24   typedef typename GameState::Move Move;
  25   typedef typename GameState::Board::Piece Piece;
  26
  27   class MoveCallback {
  28   public:
  29     virtual ~MoveCallback() { }
  30     virtual bool operator()(const Move&) = 0;
  31   };
  32 protected:
  33   const GameState& m_state;
  34
  35   class FindMove : public MoveCallback {
  36     bool m_found;
  37   public:
  38     FindMove() : m_found(false) { }
  39     virtual bool operator()(const Move&) { m_found = true; return false; }
  40
  41     bool found() const { return m_found; }
  42   };
  43
  44   virtual bool addMove(const Move& m, MoveCallback&) const;
  45   virtual bool addAllPromotions(const Move& m, MoveCallback&) const;
  46   virtual bool generateSlide(const Point& p, const Point& dir, MoveCallback&) const;
  47 public:
  48   MoveGenerator(const GameState& state);
  49   virtual ~MoveGenerator();
  50
  51   virtual bool check(typename Piece::Color) const;
  52   virtual bool stalled() const;
  53   virtual void generate(MoveCallback&) const;
  54   virtual bool generateFrom(const Point& p, MoveCallback&) const;
  55 };
  56
  57 // IMPLEMENTATION
  58
  59 template <typename LegalityCheck>
  60 MoveGenerator<LegalityCheck>::MoveGenerator(const GameState& state)
  61 : m_state(state) { }
  62
  63 template <typename LegalityCheck>
  64 MoveGenerator<LegalityCheck>::~MoveGenerator() { }
  65
  66 template <typename LegalityCheck>
  67 bool MoveGenerator<LegalityCheck>::check(typename Piece::Color turn) const {
  68   Point kingPosition = m_state.board().find(Piece(turn, Piece::KING));
  69   if (!kingPosition.valid()) {
  70     // a missing king is considered in check
  71     return true;
  72   }
  73   else {
  74     LegalityCheck check(m_state);
  75     return check.attacks(Piece::oppositeColor(turn), kingPosition);
  76   }
  77 }
  78
  79 template <typename LegalityCheck>
  80 bool MoveGenerator<LegalityCheck>::stalled() const {
  81   FindMove findMove;
  82   generate(findMove);
  83   return !findMove.found();
  84 }
  85
  86 template <typename LegalityCheck>
  87 void MoveGenerator<LegalityCheck>::generate(MoveCallback& callback) const {
  88   for (int i = 0; i < m_state.board().size().x; i++) {
  89     for (int j = 0; j < m_state.board().size().y; j++) {
  90       generateFrom(Point(i, j), callback);
  91     }
  92   }
  93 }
  94
  95 template <typename LegalityCheck>
  96 bool MoveGenerator<LegalityCheck>::generateFrom(const Point& p, MoveCallback& callback) const {
  97   Piece piece = m_state.board().get(p);
  98   if (piece.color() == m_state.turn()) {
  99     switch (piece.type()) {
 100     case Piece::PAWN:
 101       {
 102         Point dir = m_state.direction(piece.color());
 103         if ((p + dir).y == m_state.promotionRank(piece.color())) {
 104           return addAllPromotions(Move(p, p + dir), callback) &&
 105           addAllPromotions(Move(p, p + dir + Point(1, 0)), callback) &&
 106           addAllPromotions(Move(p, p + dir + Point(-1, 0)), callback);
 107         }
 108         else {
 109           return addMove(Move(p, p + dir), callback) &&
 110           addMove(Move(p, p + dir * 2), callback) &&
 111           addMove(Move(p, p + dir + Point(1, 0)), callback) &&
 112           addMove(Move(p, p + dir - Point(1, 0)), callback);
 113         }
 114       }
 115     case Piece::KNIGHT:
 116       return addMove(Move(p, p + Point(1, 2)), callback) &&
 117       addMove(Move(p, p + Point(1, -2)), callback) &&
 118       addMove(Move(p, p + Point(-1, 2)), callback) &&
 119       addMove(Move(p, p + Point(-1, -2)), callback) &&
 120       addMove(Move(p, p + Point(2, 1)), callback) &&
 121       addMove(Move(p, p + Point(2, -1)), callback) &&
 122       addMove(Move(p, p + Point(-2, 1)), callback) &&
 123       addMove(Move(p, p + Point(-2, -1)), callback);
 124     case Piece::BISHOP:
 125       return generateSlide(p, Point(1, 1), callback) &&
 126       generateSlide(p, Point(1, -1), callback) &&
 127       generateSlide(p, Point(-1, -1), callback) &&
 128       generateSlide(p, Point(-1, 1), callback);
 129     case Piece::ROOK:
 130       return generateSlide(p, Point(1, 0), callback) &&
 131       generateSlide(p, Point(0, 1), callback) &&
 132       generateSlide(p, Point(-1, 0), callback) &&
 133       generateSlide(p, Point(0, -1), callback);
 134     case Piece::QUEEN:
 135       return generateSlide(p, Point(1, 0), callback) &&
 136       generateSlide(p, Point(0, 1), callback) &&
 137       generateSlide(p, Point(-1, 0), callback) &&
 138       generateSlide(p, Point(0, -1), callback) &&
 139       generateSlide(p, Point(1, 1), callback) &&
 140       generateSlide(p, Point(1, -1), callback) &&
 141       generateSlide(p, Point(-1, -1), callback) &&
 142       generateSlide(p, Point(-1, 1), callback);
 143     case Piece::KING:
 144       return addMove(Move(p, p + Point(1,0)), callback) &&
 145       addMove(Move(p, p + Point(1,1)), callback) &&
 146       addMove(Move(p, p + Point(0,1)), callback) &&
 147       addMove(Move(p, p + Point(-1,1)), callback) &&
 148       addMove(Move(p, p + Point(-1,0)), callback) &&
 149       addMove(Move(p, p + Point(-1,-1)), callback) &&
 150       addMove(Move(p, p + Point(0,-1)), callback) &&
 151       addMove(Move(p, p + Point(1,-1)), callback);
 152     default:
 153       return true;
 154     }
 155   }
 156
 157   return true;
 158 }
 159
 160 template <typename LegalityCheck>
 161 bool MoveGenerator<LegalityCheck>::
 162 generateSlide(const Point& p, const Point& dir, MoveCallback& callback) const {
 163   Point q = p + dir;
 164   while (m_state.board().valid(q)) {
 165     if (!addMove(Move(p, q), callback))
 166       return false;
 167     q += dir;
 168   }
 169
 170   return true;
 171 }
 172
 173
 174 template <typename LegalityCheck>
 175 bool MoveGenerator<LegalityCheck>::addMove(const Move& m, MoveCallback& callback) const {
 176   LegalityCheck check(m_state);
 177   Move move(m);
 178   if (check.legal(move)) {
 179     return callback(move);
 180   }
 181
 182   return true;
 183 }
 184
 185 template <typename LegalityCheck>
 186 bool MoveGenerator<LegalityCheck>::addAllPromotions(const Move& m, MoveCallback& callback) const {
 187   return addMove(Move(m.from(), m.to(), Piece::QUEEN), callback) &&
 188   addMove(Move(m.from(), m.to(), Piece::ROOK), callback) &&
 189   addMove(Move(m.from(), m.to(), Piece::KNIGHT), callback) &&
 190   addMove(Move(m.from(), m.to(), Piece::BISHOP), callback);
 191 }
 192
 193
 194
 195 } // namespace Chess
 196 } // namespace HLVariant
 197
 198 #endif // HLVARIANT__CHESS__MOVEGENERATOR_H
 199