RomiChess has a learn.dat file that stores a tree of all the games that Romi plays to some depth like 160 ply. Maybe something similar is what you are looking for?Jon12345 wrote: ↑Wed Jun 01, 2022 5:58 pm I want to create a tree of chess moves, but where each node in that tree can also have alternative moves.
e.g. e4 is the first move and so the root node. Next you have move 2, which can have c5, e5, g6 etc. Then each of these alternative moves can have a variety of different moves.
So, after some Googling, I've seen buzzwords like Binary Trees, Game Tree, Rose Tree etc. But I am not sure what data structure would suit and how to create it in Javascript. After looking at bits of code, I sense it might be relatively easy, but I am not sure how to do it.
The purpose of this project is to create my own opening repertoire that stores all the potential replies to my opponents nasty moves!
Anyone here got some pointers or code snippet that might help?
Thanks.
Code: Select all
typedef struct
{
u32 sibling;
u32 child;
s08 fs;
s08 ts;
s08 type;
u08 flags;
s08 depth;
u08 status;
s16 score;
u32 wWins;
u32 bWins;
u32 draws;
} learn;
// learn.c
// Part of the program -- RomiChess
// Copyright 2005 by -- Michael J Sherwin
#if !defined ROMI
#include "Def.h"
#include "Protos.h"
#include "Data.h"
#endif
void SetRecord(learn *lR,
u32 sibling,
u32 child,
s08 fs,
s08 ts,
s08 type,
u08 flags,
s08 depth,
u08 status,
s16 score,
u32 wWins,
u32 bWins,
u32 draws) {
lR->sibling = sibling;
lR->child = child;
lR->fs = fs;
lR->ts = ts;
lR->type = type;
lR->flags = flags;
lR->depth = depth;
lR->status = status;
lR->score = score;
lR->wWins = wWins;
lR->bWins = bWins;
lR->draws = draws;
}
void SaveRecord(u32 record, learn *lR) {
fseek(filePtr, record * sizeof(learn), SEEK_SET);
fwrite((char *)lR, sizeof(char), sizeof(learn), filePtr);
}
void LoadRecord(u32 record, learn *lR) {
fseek(filePtr, record * sizeof(learn), SEEK_SET);
fread((char *)lR, sizeof(char), sizeof(learn), filePtr);
}
void PrintRecord(u32 record) {
LoadRecord(record, &learnRecord);
printf("Record %d sib %d chd %d fs %d ts %d t %d f %d d %d s %d score %d w %d l %d d %d\n",
record,
learnRecord.sibling,
learnRecord.child,
(u32)learnRecord.fs,
(u32)learnRecord.ts,
(u32)learnRecord.type,
(u32)learnRecord.flags,
(u32)learnRecord.depth,
(u32)learnRecord.status,
(s32)learnRecord.score,
(u32)learnRecord.wWins,
(u32)learnRecord.bWins,
(u32)learnRecord.draws);
}
void DisableLearning() {
LoadRecord(0, &learnRecord);
learnRecord.type = 1;
SaveRecord(0, &learnRecord);
learnMode = FALSE;
}
void DisableBook() {
LoadRecord(0, &learnRecord);
learnRecord.flags = 1;
SaveRecord(0, &learnRecord);
bookMode = FALSE;
}
void EnableLearning() {
LoadRecord(0, &learnRecord);
learnRecord.type = 0;
SaveRecord(0, &learnRecord);
learnMode = TRUE;
}
void EnableBook() {
LoadRecord(0, &learnRecord);
learnRecord.flags = 0;
SaveRecord(0, &learnRecord);
bookMode = TRUE;
}
void OpenLearnDat() {
s32 record;
filePtr = fopen("learn.dat", "r+b");
if(!filePtr) {
(s32)filePtr = open("learn.dat", _O_RDWR | _O_CREAT, _S_IREAD | _S_IWRITE);
chsize((s32)filePtr, sizeof(learn) * 10000);
close((s32)filePtr);
filePtr = fopen("learn.dat", "r+b");
SetRecord(&learnRecord, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1);
SaveRecord(0, &learnRecord);
SetRecord(&learnRecord, 0, 0, E2, E4, 0, 0, 0, 0, 0, 0, 0, 0);
SaveRecord(1, &learnRecord);
for(record = 2; record < 9999; record++) {
SetRecord(&learnRecord, record + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
SaveRecord(record, &learnRecord);
}
SetRecord(&learnRecord, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
SaveRecord(9999, &learnRecord);
Pgn2Learn("BaseLine.pgn");
}
LoadRecord(0, &learnRecord);
if(!learnRecord.type) learnMode = 1; else learnMode = 0;
if(!learnRecord.flags) bookMode = 1; else bookMode = 0;
temp = bookMode;
}
u32 ScanSiblings(u32 record, moves *m, u32 *last) {
LoadRecord(record, &learnRecord);
while(learnRecord.fs != m->fs || learnRecord.ts != m->ts) {
if(learnRecord.sibling) {
record = learnRecord.sibling;
LoadRecord(record, &learnRecord);
continue;
}
*last = record;
return 0;
}
return record;
}
u32 GetNextFree() {
u32 free;
u32 record;
learn zeroRecord;
learn nextFree;
LoadRecord(0, &zeroRecord);
free = zeroRecord.sibling;
LoadRecord(free, &nextFree);
if(nextFree.sibling == 0) {
nextFree.sibling = free + 1;
zeroRecord.draws++;
fclose(filePtr);
(s32)filePtr = open("learn.dat", _O_RDWR | _O_CREAT, _S_IREAD | _S_IWRITE);
chsize((s32)filePtr, sizeof(learn) * 10000 * zeroRecord.draws);
close((s32)filePtr);
filePtr = fopen("learn.dat", "r+b");
for(record = free + 1; record < free + 10000; record++) {
SetRecord(&learnRecord, record + 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
SaveRecord(record, &learnRecord);
}
SetRecord(&learnRecord, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
SaveRecord(free + 10000, &learnRecord);
}
zeroRecord.sibling = nextFree.sibling;
zeroRecord.child++;
SaveRecord(0, &zeroRecord);
nextFree.sibling = 0;
SaveRecord(free, &nextFree);
return free;
}
void LearnGame() {
s32 i;
s32 keepGoing;
s16 score;
u32 thread;
u32 child;
u32 sibling;
u32 last;
u32 free;
learn siblingRecord;
child = 1;
for(i = 0; (i < ply && i < 240); i++) {
if(child) thread = child;
else {
free = GetNextFree();
learnRecord.child = free;
SaveRecord(thread, &learnRecord);
thread = free;
SetRecord(&learnRecord, 0, 0, hist[i].fs, hist[i].ts, hist[i].typ,
hist[i].flag, hist[i].depth, 0, hist[i].score, 0, 0, 0);
SaveRecord(thread, &learnRecord);
}
thread = ScanSiblings(thread, (moves *)&hist[i], &last);
if(thread) {
LoadRecord(thread, &learnRecord);
if(hist[i].depth >= learnRecord.depth) {
learnRecord.depth = hist[i].depth;
learnRecord.score = hist[i].score;
}
if(bookMode == 2) {
if(i & 1) {
if(blackWin) learnRecord.status = BOOK;
} else
{
if(whiteWin) learnRecord.status = BOOK;
}
}
learnRecord.wWins += whiteWin;
learnRecord.bWins += blackWin;
learnRecord.draws += drawn;
if(drawn) {
learnRecord.score -= (learnRecord.score / 8);
} else
if(i & 1)
learnRecord.score += ((blackWin - whiteWin) * ((i + 40) / 4));
else
learnRecord.score += ((whiteWin - blackWin) * ((i + 40) / 4));
if(learnRecord.score > 8000) learnRecord.score = 8000;
else
if(learnRecord.score < -8000) learnRecord.score = -8000;
SaveRecord(thread, &learnRecord);
child = learnRecord.child;
} else {
LoadRecord(last, &learnRecord);
free = GetNextFree();
learnRecord.sibling = free;
SaveRecord(last, &learnRecord);
LoadRecord(free, &learnRecord);
thread = free;
SetRecord(&learnRecord, 0, 0, hist[i].fs, hist[i].ts, hist[i].typ,
hist[i].flag, hist[i].depth, 0, hist[i].score, whiteWin, blackWin, drawn);
SaveRecord(thread, &learnRecord);
child = 0;
}
hist[i].thread = thread;
}
if(i & 1) i--;
if(drawn) {
thread = hist[i].thread;
LoadRecord(thread, &learnRecord);
learnRecord.score = 0;
SaveRecord(thread, &learnRecord);
}
keepGoing = TRUE;
while(i-- >= 0 && keepGoing) {
keepGoing = FALSE;
thread = hist[i].thread;
LoadRecord(thread, &learnRecord);
score = learnRecord.score;
sibling = learnRecord.child;
while(sibling) {
LoadRecord(sibling, &siblingRecord);
if(i & 1) {
if(-siblingRecord.score > score) {
if(NumChildren(sibling) > 7) {
score = -siblingRecord.score;
keepGoing = TRUE;
}
}
} else {
if(-siblingRecord.score < score) {
if(NumChildren(sibling) > 7) {
score = -siblingRecord.score;
keepGoing = TRUE;
}
}
}
sibling = siblingRecord.sibling;
}
if(keepGoing) {
learnRecord.score = score;
SaveRecord(thread, &learnRecord);
}
}
}
s32 NumChildren(u32 parent) {
s32 num;
u32 sibling;
learn record;
num = 0;
LoadRecord(parent, &record);
sibling = record.child;
while(sibling) {
num++;
LoadRecord(sibling, &record);
sibling = record.sibling;
}
return num;
}
void SetThread() {
s32 i;
u32 last;
thread = 1;
for(i = 0; i < ply; i++) {
thread = ScanSiblings(thread, (moves *)&hist[i], &last);
if(!thread) return;
LoadRecord(thread, &learnRecord);
thread = learnRecord.child;
if(!thread) return;
}
}
moves Learn2Hash() {
s32 Ply;
moves m;
poshashs *p;
Ply = ply - base;
SetThread();
m.m = 0;
if(!pondering && thread) m = GetBookMove(thread);
if(m.m) return m;
while(Ply > 0 || thread) {
while(Ply < 40 && thread) {
LoadRecord(thread, &learnRecord);
m.fs = learnRecord.fs;
m.ts = learnRecord.ts;
m.typ = learnRecord.type;
m.flag = learnRecord.flags;
if(!VerifyMove(&m)) goto dontmove;
h->thread = thread;
if(learnRecord.depth) {
p = PosLook();
if(!p || learnRecord.depth >= p->depth) {
PosStore(learnRecord.score, learnRecord.depth, EXACT, &noMove);
}
}
MakeMove(&m);
Ply++;
thread = learnRecord.child;
}
TakeBack();
Ply--;
thread = h->thread;
LoadRecord(thread, &learnRecord);
dontmove:
thread = learnRecord.sibling;
}
m.m = 0;
return m;
}
moves GetBookMove(s32 thread) {
s32 wins;
s32 losses;
s32 draws;
u64 total;
s32 points;
s32 percent;
s32 votes;
s32 level;
s32 confidence;
s32 min;
s32 bookMove;
moves move;
min = wtm ? 55 : 45;
move.m = 0;
votes = 0;
confidence = 0;
bookMove = FALSE;
srand(clock());
do {
LoadRecord(thread, &learnRecord);
if(wtm) {
wins = learnRecord.wWins;
losses = learnRecord.bWins;
} else {
wins = learnRecord.bWins;
losses = learnRecord.wWins;
}
draws = learnRecord.draws;
total = wins + losses + draws;
if(total) {
points = wins + (draws / 2);
percent = points * 100 / (u32)total;
level = LastBit(total);
if(level + 3 >= confidence) {
votes = percent + level + rand() % 10;
if(level > confidence)
confidence = level;
}
if((!bookMove && learnRecord.status == BOOK && (bookMove = TRUE))
||((votes > min &&((!bookMove || (bookMove && learnRecord.flags == BOOK)))))) {
min = votes;
move.fs = learnRecord.fs;
move.ts = learnRecord.ts;
move.typ = learnRecord.type;
move.flag = learnRecord.flags;
}
}
thread = learnRecord.sibling;
} while (thread);
return move;
}
void Pgn2Learn(s08 *file) {
FILE *fp;
s08 data[80];
s32 open = FALSE;
s32 resultFound;
s32 game = 0;
s32 learn = TRUE;
moves move;
fp = fopen(file, "r");
if(fp != NULL) {
resultFound = FALSE;
h->t = tree;
MoveGen();
AddAllMoves(tree);
while(!feof(fp)) {
fscanf(fp, "%[^ .\n]%*[ .\n]", data);
if(strchr(data, '['))
open++;
if(!strcmp(data, "[Result")) {
if(resultFound) {
printf("Game = %d", ++game);
printf(" Ply = %d\n", ply);
if(learn) TriggerLearn(resultFound);
else printf("Not learning\n");
resultFound = FALSE;
while(ply) {
TakeBack();
}
}
learn = TRUE;
fscanf(fp, "%[^ .\n]%*[ .\n]", data);
if(!strcmp(data, "\"1-0\"]")) {
resultFound = 1;
} else
if(!strcmp(data, "\"0-1\"]")) {
resultFound = 2;
} else
if(!strcmp(data, "\"1/2-1/2\"]")) {
resultFound = 3;
}
} else
if(!open && learn && resultFound && ply < 60) {
move = IsMove(data);
if(move.m != noMove.m) {
if(VerifyMove(&move)) {
MakeMove(&move);
MoveGen();
AddAllMoves(h->t);
} else {
learn = FALSE;
}
}
}
if(strchr(data, ']'))
open--;
}
if(learn && resultFound) TriggerLearn(resultFound);
fclose(fp);
while(ply) {
TakeBack();
}
}
}
moves IsMove(s08 *c) {
s32 figure;
s32 col;
s32 row;
s32 fs;
s32 ts;
s32 rank = -1;
s32 file = -1;
s32 promote = FALSE;
moves move;
trees * node;
// check for O-O or O-O-O
if(!strcmp(c, "O-O")) {
if(wtm) {
figure = WK;
ts = G1;
} else {
figure = BK;
ts = G8;
}
goto skipparse;
}
if(!strcmp(c, "O-O-O")) {
if(wtm) {
figure = WK;
ts = C1;
} else {
figure = BK;
ts = C8;
}
goto skipparse;
}
// get the figure or exit
if('A' < *c && *c < 'Z')
figure = *c++;
else
if('a' <= *c && *c <= 'h')
figure = 'P';
else
return noMove;
// convert figure to internal value or exit
if(wtm) {
if(figure == 'P') figure = WP; else
if(figure == 'N') figure = WN; else
if(figure == 'B') figure = WB; else
if(figure == 'R') figure = WR; else
if(figure == 'Q') figure = WQ; else
if(figure == 'K') figure = WK; else return noMove;
} else {
if(figure == 'P') figure = BP; else
if(figure == 'N') figure = BN; else
if(figure == 'B') figure = BB; else
if(figure == 'R') figure = BR; else
if(figure == 'Q') figure = BQ; else
if(figure == 'K') figure = BK; else return noMove;
}
// get the rank or file specifier if presant
if('1' <= *c && *c <= '8')
rank = *c++ - '1';
else
if('a' <= *c && *c <= 'h' && 'a' <= *(c+1) && *(c+1) <= 'x')
file = *c++ - 'a';
// get past the capture indicator
if(*c == 'x') c++;
// get the ts colum or exit
if('a' <= *c && *c <= 'h')
col = *c++ - 'a';
else
return noMove;
// get the ts row or exit
if('1' <= *c && *c <= '8')
row = *c++ - '1';
else
return noMove;
// convert row and col to a square number
ts = row * 8 + col;
// if figure is a pawn see if it has promoted
promote = 0;
if(figure == 'P' && *c++ == '=') {
if(*c == 'Q') promote = QUEEN; else
if(*c == 'N') promote = KNIGHT; else
if(*c == 'R') promote = ROOK; else
if(*c == 'B') promote = BISHOP;
}
skipparse:
// now spin thru the moves until the move is found
move = noMove;
for(node = h->t; node < (h+1)->t; node++) {
if(node->ts == ts) {
fs = node->fs;
if(piece[board[fs]].fig == figure) {
if(file >= 0 && file != Col(fs)) continue;
if(rank >= 0 && rank != Row(fs)) continue;
move.fs = fs;
move.ts = ts;
move.typ = node->typ;
move.flag = promote;
break;
}
}
}
return move;
}
void TriggerLearn(s32 result) {
whiteWin = 0;
blackWin = 0;
drawn = 0;
if(result) {
if(result == 1) whiteWin = 1; else
if(result == 2) blackWin = 1; else
if(result == 3) drawn = 1;
LearnGame();
}
}