Я работал над шахматным движком, но уже несколько недель работаю над той же ошибкой и собираюсь сойти с ума. Каждая шахматная позиция представлена узлом. Каждый возможный ход из позиции связан в связанном списке. Я настроил его так, что у каждого узла есть три указателя: один указывает на свой родительский узел (предыдущую позицию), один указывает прямо на следующий узел в своем связанном списке, а другой указывает на список возможных перемещений. с этой позиции. Например, из начальной позиции после 1.e4 будет узел, указывающий вправо на позицию 1.d3. Другой будет указывать на начальную позицию, а другой - на первый возможный ответ 1.Nf6. Итак, вот в чем проблема: у стартовой позиции у белых есть 20 возможных ходов, поэтому на 1-слойном уровне есть 20 перестановок. У черных 20 возможных ответов, в общей сложности 400 перестановок в 2 слоя. Продолжение:
1-слойный: 20
2-слойный: 400
3-слойный: 8902
4-слойный: 197 281
5-слойная: 4 865 609
Сколько узлов мой двигатель создает на каждой глубине:
1-слойная: 20
2-слойная: 400
3-слойный: 8902
4-слойный: 8885
5-слойный: 8527
Интересно, что двигатель делает это не только из стартовой позиции , У каждой позиции, которую я кормлю, есть одна и та же проблема, даже в ситуациях, когда существует всего несколько сотен возможностей. Я проверил, что он соблюдает все шахматные правила, в том числе en passant, пат, правила 3-х ходов и другие. У меня есть сильное подозрение, что это может быть связано с функцией, которую я использую для создания узлов, или, возможно, с одной из функций incrementNode или dropNodeALevel. К сожалению, для меня слишком много кода, чтобы разделить минимум, чтобы воспроизвести ошибку, но я был бы очень признателен, если бы кто-нибудь здесь мог взглянуть на некоторый основной код и посмотреть, выделяется ли что-нибудь. Я очень программист-любитель, и я надеюсь, что просто допустил простую ошибку, которая должна быть здесь более очевидной для программистов. Основное l oop, которое моя программа использует во время поиска, состоит из двух основных шагов: во-первых, generateMoves принимает узел в качестве входных данных и создает все узлы ниже (по одному для каждого возможного перемещения) и связывает их все с указателями. Во-вторых, defineChildren иvaluNode обновляют переменную оценки в каждом узле. Оценка не должна ни на что повлиять. Я попытался пройти программу с помощью gdb 7.2 и подтвердил, что никакие узлы глубины 3 не отправляются в generateMoves в основном l oop, что является одной из причин, почему я с подозрением отношусь к incrementNode и dropNodeALevel. Каждый узел представлен структурой с именем boardState. Вот основная функция l oop:
depth = 1;
while (depth < goInfo->depth) {
do {
generateMoves(nodePtr);
goInfo->nodeCount = evaluateChildren(nodePtr, goInfo->nodeCount);
evaluateNode(nodePtr);
} while (incrementNode(&nodePtr) == 1); //incrementNode doesn't affect nodePtr if it is at the end of the ply. It returns 0 when it reaches the end of the ply.
depth++;
dropNodeALevel(&nodePtr);
determineBestContinuation(currentBoard, pv);
printf("info depth %d score cp %d pv %s\n", depth, currentBoard->evaluation, pv);
}
printf("Evaluated %ld nodes, %ld bytes\n", goInfo->nodeCount, goInfo->nodeCount * (long) sizeof(boardState));
printf("Took %f seconds, %f nodes per second\n", (float)(getTimeMS() - goInfo->startTime) / 1000, (float)goInfo->nodeCount / ((float)(getTimeMS() - goInfo->startTime) / 1000));
Эта функция используется для создания новых узлов.
//All child nodes to a parent are in a linked list. This function creates a new node at the head of the linked list. The variable parentNode->childPointer is a pointer to the first node. The input boardState is the data to go in the new node.
void createNode(boardState* parentBoard, boardState newBoardStateAfterMove) {
assert(parentBoard != NULL);
//Check move new board state for legality. Important to note is that this function won't create a node if its parent is a finished game.
if (parentBoard->winner == ONGOING) {
if ( (newBoardStateAfterMove.whoseTurn == WHITE && isCheck(newBoardStateAfterMove, BLACK) == FALSE) || (newBoardStateAfterMove.whoseTurn == BLACK && isCheck(newBoardStateAfterMove, WHITE) == FALSE) ) {
//Allocate new node
boardState* newNode = (boardState*) malloc(sizeof(boardState));
if (newNode == NULL) {
fprintf(stderr, "malloc returned NULL during node creation\n");
abort();
}
//Put in the data (but not the side pointer)
*newNode = newBoardStateAfterMove;
newNode->parentNode = parentBoard;
newNode->childNode = NULL;
//Take old head, put in side pointer of new node
newNode->nextNode = parentBoard->childNode;
//Update the head to point to the start of the new node
parentBoard->childNode = newNode;
}
}
}
Следующая функция - incrementNode, которая используется для продвижения указатель узла на следующий узел «вправо» в сгибе. Обычно это просто указатель на следующую ссылку в связанном списке, но если она последняя в списке, то может потребоваться go вверх и вниз или вниз, или что-то более сложное.
//This function increments a node to the next in the ply. Returns 0 if at the end of the ply, else returns 1.
int incrementNode(boardState** nodeToIncrement) {
/*
Going right is like flipping a switch. It starts in up mode
In up mode, if you can't go right, go up.
As soon as you go right, the switch flips to down mode.
In down mode, if you can't go down, go right.
When depth = original, break.
If you can't go down or right, and depth still isn't original, switch back to up mode.
If you are in up mode and reach the current board state, you are at the end of the ply. Return 0.
*/
assert(nodeToIncrement != NULL);
assert(*nodeToIncrement != NULL);
bool mode = 1; //0 for down mode, 1 for up mode
int depth = 0; //used as "height" in this case
boardState* nodePtr = *nodeToIncrement;
do {
if (mode == 1) {
if (nodePtr->nextNode != NULL) {
nodePtr = nodePtr->nextNode;
mode = 0;
}
else if (nodePtr->parentNode != NULL) {
nodePtr = nodePtr->parentNode;
depth++;
}
else {
return 0;
}
}
else if (mode == 0) {
if (nodePtr->childNode != NULL) {
nodePtr = nodePtr->childNode;
depth--;
}
else if (nodePtr->nextNode != NULL) {
nodePtr = nodePtr->nextNode;
}
else {
mode = 1;
}
}
} while (depth > 0);
*nodeToIncrement = nodePtr;
assert(nodeToIncrement != NULL);
return 1;
}
И, наконец, dropNodeALevel. Этот принимает указатель на узел в качестве входных данных и направляет его к крайнему левому узлу следующего слоя вниз.
//This function takes a node of depth x, and puts it at the leftmost node of depth x+1. It returns 0 if there are none, and 1 otherwise.
int dropNodeALevel(boardState** nodeToDrop) {
assert(nodeToDrop != NULL);
assert(*nodeToDrop != NULL);
boardState* nodePtr = *nodeToDrop;
//This guarantees you are at the far left of depth x. If you are not at the currentBoard level, this moves you there. If you are at the currentBoard level, you are already at the far left because there is only one node at that depth.
if (nodePtr->parentNode != NULL) {
nodePtr = nodePtr->parentNode;
nodePtr = nodePtr->childNode;
}
//Increment through each node in the ply, checking each to see if it has a child. If it does, set *nodeToDrop to that child and return 1. If there are none, return 0.
do {
if (nodePtr->childNode != NULL) {
*nodeToDrop = nodePtr->childNode;
return 1;
}
} while (incrementNode(&nodePtr) == 1);
return 0;
}