//
// C++ Interface: aibrain
//
// Description:
//
//
// Author: Hendrik Hochstetter <hochsthk@studi.informatik.uni-stuttgart.de>, (C) 2008
//
// Copyright: See COPYING file that comes with this distribution
//
//
#ifndef _AIBRAIN_H
#define _AIBRAIN_H
#include <transfer.hpp>
#include <cheppcl.h>
#include <QtCore/QThread>
#include <QtCore/QObject>
#include <QtCore/QHash>
#include <QtCore/QMap>
#include <QtCore/QList>
#include <QtCore/QTimer>
#include <QtCore/QPair>
#include <QtCore/QTime>
#include "conversions.h"
#include "globals.h"
//bool operator<(Move m1, Move m2);
inline uint qHash (zug z)
{
return qHash (uint (z.get_erste_k ().get_dim1 () + z.get_erste_k ().get_dim2 () * 8 + z.get_erste_k ().get_dim3 () * 64) + uint ((z.get_zweite_k ().get_dim1 () + z.get_zweite_k ().get_dim2 () * 8 + z.get_zweite_k ().get_dim3 () * 64)*512));
};
inline int qHash (Position pos)
{
int temp = 0;
Field f = pos.key (KING_W);
temp = f;
f = pos.key (KING_B);
temp = temp + f;
temp = (temp<<4);
foreach (Field f, pos.keys (QUEEN_W))
{
temp = temp + f;
}
foreach (Field f, pos.keys (QUEEN_B))
{
temp = temp + f;
}
temp = (temp<<4);
foreach (Field f, pos.keys (ROOK_W))
{
temp = temp + f;
}
foreach (Field f, pos.keys (ROOK_B))
{
temp = temp + f;
}
temp = (temp<<4);
foreach (Field f, pos.keys (KNIGHT_W))
{
temp = temp + f;
}
foreach (Field f, pos.keys (KNIGHT_B))
{
temp = temp + f;
}
temp = (temp<<4);
foreach (Field f, pos.keys (BISHOP_W))
{
temp = temp + f;
}
foreach (Field f, pos.keys (BISHOP_B))
{
temp = temp + f;
}
temp = (temp<<4);
foreach (Field f, pos.keys (PAWN_W))
{
temp = temp + f;
}
foreach (Field f, pos.keys (PAWN_B))
{
temp = temp + f;
}
return qHash (temp);
};
/**
* Datentyp für Darstellung von Schachstellungen als Knoten eines Suchbaums.
**/
struct StateNode;
typedef QHash<Move,StateNode*> FollowStates;
// struct FollowStates
// {
// /** ausgangsstellung wird für sortierung der Züge gebraucht. **/
// Position position;
// Move moves [200];
// StateNode *nodes [200];
//
// void setPosition (Position p)
// {
// position = p;
// }
//
// /** priorität der figurklassen für sortierung der züge für effektiveres pruning **/
// inline int priorityOfPiece (Piece p)
// {
// switch (p)
// {
// case PAWN_W:
// return 12;
// case PAWN_B:
// return 12;
// case BISHOP_W:
// return 6;
// case BISHOP_B:
// return 6;
// case KNIGHT_W:
// return 4;
// case KNIGHT_B:
// return 4;
// case ROOK_W:
// return 2;
// case ROOK_B:
// return 2;
// case QUEEN_W:
// return 0;
// case QUEEN_B:
// return 0;
// case KING_W:
// return 10;
// case KING_B:
// return 10;
// };
// return 0;
// };
//
// /** @brief Sortierfunktion, die die Folgezüge jedesmal sortieren soll bevor alpha-beta-pruning erfolgt.
// * @details Je weiter oben erfolgsversprechende Züge einsortiert werden, desto effektiver arbeitet
// * die alpha-beta-suche.
// **/
// inline bool lessThan (Move m1, Move m2)
// {
// Piece p1 = position.value (m1.from);
// Piece p2 = position.value (m2.from);
//
// // wenn Figur, die zieht bei m1 wertvoller ist als bei m2
// if (priorityOfPiece (p1) < priorityOfPiece (p2))
// {
// return true;
// }
// else if (priorityOfPiece (p1) > priorityOfPiece (p2))
// {
// return false;
// }
//
// Field t1 = move (m1);
// Field t2 = move (m2);
// p1 = position.value (t1);
// p2 = position.value (t2);
//
// // wenn wertvollere Figur geschlagen wird
// if (abs (valueOfPiece (p1)) < abs (valueOfPiece (p2)))
// {
// return true;
// }
// else if (abs (valueOfPiece (p1)) > abs (valueOfPiece (p2)))
// {
// return false;
// }
//
// if (manhattanDistance (m1.by) * m1.scale < manhattanDistance (m2.by) * m2.scale)
// {
// return true;
// }
// return false;
// };
//
//
// FollowStates ()
// {
// moves [0].scale = 0;
// };
//
// inline void clear () {
// moves [0].scale = 0;
// };
//
// void insert (Move m, StateNode* s)
// {
// for (int i = 0; i < 200; i++)
// {
// if (moves [i].scale == 0)
// {
// moves [i] = m;
// moves [i+1].scale = 0;
// nodes [i] = s;
// return;
// }
// else if (moves [i] == m)
// {
// nodes [i] = s;
// return;
// }
// else if (!lessThan (m, moves [i]))
// {
// for (int j = 199; j > i; j--)
// {
// moves [j] = moves [j - 1];
// nodes [j] = nodes [j - 1];
// }
// moves [i] = m;
// nodes [i] = s;
// return;
// }
// }
// };
//
// inline QList<StateNode*> values ()
// {
// QList<StateNode*> sn;
// for (int i = 0; i < 200; i++)
// {
// if (moves [i].scale == 0)
// {
// break;
// }
// sn.append (nodes [i]);
// }
// return sn;
// };
//
// inline StateNode *value (Move m)
// {
// for (int i = 0; i < 200; i++)
// {
// if (moves [i].scale == 0)
// {
// break;
// }
//
// if (m == moves [i])
// {
// return nodes [i];
// }
// }
// return 0;
// };
//
//
// inline int size ()
// {
// int sz = 0;
// for (int i = 0; i < 200; i ++)
// {
// if (moves [i].scale == 0)
// {
// break;
// }
// sz++;
// }
// return sz;
// };
//
//
// inline QList<Move> keys ()
// {
// QList<Move> k;
// for (int i = 0; i < 200; i ++)
// {
// if (moves [i].scale == 0)
// {
// break;
// }
// k.append (moves [i]);
// }
// return k;
// };
//
// inline Move key (StateNode *s)
// {
// for (int i = 0; i < 200; i ++)
// {
// if (moves [i].scale == 0)
// {
// break;
// }
//
// if (nodes [i] == s)
// {
// return moves [i];
// }
// }
// return Move ();
// };
// };
struct StateNode
{
StateNode () : whiteState (0), blackState (0), next (
FollowStates()), position (Position ()), last (-1), depth (0), value (0), whiteKingOnly (false), blackKingOnly (false), check (false)
{
next.reserve (300);
};
~StateNode ()
{
qDeleteAll (next.values ());
next.clear ();
};
/** Map möglicher Folgezüge nach Zeiger auf zugehöriges Suchbaumobjekt **/
FollowStates next;
Position position;
/** wenn der letzte Zug ein Bauerdoppelsprung war steht hier die x-koordinate, ansonsten -1. **/
int last;
/**
* @name zustandskodierung: darf weiß rochieren? darf schwarz?...
**/
/** @{ **/
int whiteState;
int blackState;
bool whiteKingOnly;
bool blackKingOnly;
bool check;
/** @} **/
/** abschätzung der stellungswertes **/
int value;
/** tiefe des knotens im suchbaum **/
int depth;
};
/**
* @brief Das Gehirn der KI: AiBrain
* @details Das eigentliche Gehirn der KI steckt in der Klasse AiBrain.
* hier sind Stellungsbewertung, Berechnung der Zugmöglichkeiten etc.
* implementiert, hier wird der Suchbaum erzeugt und nach dem bestmöglichen Zug
* durchsucht. AiBrain-Objekte werd von AiPlayer erzeugt, wenn die KI in einem
* Spiel am Zug ist. die Funktion calculateMove () berechnet den besten Zug
* und gibt diesem als zug zurück.
**/
//#define BRAINDEBUG
class AiBrain : public
#ifdef BRAINDEBUG
QObject
#else
QThread
#endif
{
Q_OBJECT
public:
AiBrain (
#ifdef BRAINDEBUG
QObject *parent,
#else
QThread *parent,
#endif
Position position, int lastMove, Colour colour, AiSettings aiSettings);
zug calculateMove ();
zug result;
#ifdef BRAINDEBUG
void exit (int i) {};
void start (QThread::Priority) { run (); };
#endif
void run ()
{
qDebug () << this << gamename << "starting calculation.";
result = calculateMove ();
emit moveCalculated ();
qDebug () << this << gamename << "calculation done." << traversedNodes << "nodes traversed.";
};
QString gamename;
QList<zug> movesFromServer;
QTime stopWatch;
private:
QTimer *timer;
int timerInterval;
void lustig ();
int traversedNodes;
int duplicateNodes;
void calculateKingsMoves (StateNode *state, Field f, Colour notToMove);
void calculateUnpinnedPawnsMoves (StateNode *state, Field f, Colour toMove);
void calculatePinnedPawnsMoves (StateNode *state, Field f, MoveVector threatMV, Colour toMove);
void calculateSuccessors (StateNode *state);
void calculateStateAndMoves (StateNode *state);
void calculateMovesOfPinnedAndUnpinned (StateNode *state, Field king, Colour toMove, Field threat, QHash<Field,MoveVector>* pinnMV);
int quiescentCut;
int cutOffDepth;
/** Suchabbruch wegen Zeitüberschreitung? wird in wakeUp überprüft **/
bool timeCutOff;
/** maximale Zeit bis SUchergebnis vorliegen muss **/
int maxTime;
inline bool cutOff (StateNode* state)
{
if (state -> depth & 1)
{
return false;
}
if (state -> depth < cutOffDepth)
{
return false;
}
// in eröffnung wird nicht geschaut ob stellung ruhig.
if (evaluationType == EVAL_OPENING)
{
return true;
}
return quiescent (state);
};
bool quiescent (StateNode *state);
/**
* @name Funktionen für Varianten der MiniMax-Suche je nach Spielstatus
**/
/** @{ **/
int minValueOpening (StateNode *state, int alpha, int beta, int sisters);
int maxValueOpening (StateNode *state, int alpha, int beta, int sisters);
int minValueElse (StateNode *state, int alpha, int beta, int sisters);
int maxValueElse (StateNode *state, int alpha, int beta, int sisters);
typedef int (AiBrain::*MinMaxValue) (StateNode*, int, int, int);
MinMaxValue minValue;
MinMaxValue maxValue;
/** @} **/
void checkTest (StateNode *state);
/**
* @name Evaluierung der Stellung
**/
/** @{ **/
typedef enum {
EVAL_OPENING = 0x01,
EVAL_MIDDLEGAME = 0x02,
EVAL_ENDGAME = 0x04
} EvaluationType;
typedef int (AiBrain::*Evaluation) (StateNode*, int);
Evaluation valueStateNode;
EvaluationType gameState (StateNode *state);
EvaluationType evaluationType;
int valueStateNodeOpening (StateNode *state, int sisters);
int valueStateNodeMiddlegame (StateNode *state, int sisters);
int valueStateNodeEndgame (StateNode *state, int sisters);
QHash<EvaluationType, Evaluation> valueFunctions;
#define NULL_MOVE_PRUNING
#ifdef NULL_MOVE_PRUNING
#endif
/** @} **/
/** Ist das Feld f1 von einer Figur von by bedroht? **/
QList<Move> threatenedBy (StateNode *state, Field f1, Colour by);
bool isThreatened (StateNode *state, Field f1, Colour by);
bool isThreatenedByPawn (StateNode *state, Field f1, Field pawn, Colour ofF1, Colour by);
/** ist feld f2 durch Figur auf f1 bedroht? **/
bool canCapture (StateNode *state, Field f1, Field f2);
bool canQueenPawn (StateNode *state);
// #define DUPLICATEPRUNING
#ifdef DUPLICATEPRUNING
QHash<Position,int> alreadyVisited;
#endif
Colour colour;
StateNode startState;
AiSettings aiSettings;
private slots:
void wakeUp ();
signals:
void moveCalculated ();
void send (const CheppCommand*);
};
#endif