Since I first saw Micromax by Harm Geert Muller (after 10 years I still can't thank him enough for his code and website with explanations)
I had this idea drilling my brain - how to perft test Micromax? Because of the king capture nature of the engine perft testing isn't trivial
and I never succeeded properly counting nodes within Micromax ( probably I'm just stupid))) ). What I loved about the engine - is it's
compactness, what I didn't like - it was like an exhibition piece which looks super cool (and works super cool) but can't be controlled
the way I used to. I had many unsuccessful attempts, but finally reached the point where I can say that I have finally mastered the
move generation techniques introduced by Micromax.
Below is Micromax style move generator that is however controlled by a conventional perft count.
I changed some things, compared to classical micromax:
- piece encoding is slightly different (yet the idea is the same)
- most of the conditions are explicit and self-explanatory
- relies on external ep and castle, no complicated virgin king/rook bits
- includes underpromotions (not yet in ui unless you manually change prom variable in DevTools)
- minimalist UI from scratch where board is rendered via JS
Save below code to chess.html and open in the browser:
Code: Select all
<script>
var board = new Array(128), side = 8, ep = -1, castle = 15;
var prom = 6;
var nodes = 0;
/*
Initial
0 1 0 0 0 0 0 0 0 0
1 20 0 0 0 0 0 0 0 0
2 400 0 0 0 0 0 0 0 0
3 8,902 34 0 0 0 12 0 0 0
4 197,281 1576 0 0 0 469 0 0 8
5 4,865,609 82,719 258 0 0 27,351 6 0 347
6 119,060,324 2,812,008 5248 0 0 809,099 329 46 10,828
Kiwipete
1 48 8 0 2 0 0 0 0 0
2 2039 351 1 91 0 3 0 0 0
3 97862 17102 45 3162 0 993 0 0 1
4 4085603 757163 1929 128013 15172 25523 42 6 43
5 193690690 35043416 73365 4993637 8392 3309887 19883 2637 30171
*/
// Rules
function movegen(uSrc, uDst, uProm) {
var moves = [];
let src = -1; while (++src < 120) {
let pce = board[src];
if (!(pce & side) || (src & 0x88)) continue;
let pceType = pce & 7;
let offsets = [[0], [-16, -1, 16, 1, -17, -15, 17, 15], [15, 16, 17],
[-33, -31, 33, 31, -18, -14, 18, 14], [-17, -15, 17, 15],
[-16, -1, 16, 1], [-16, -1, 16, 1, -17, -15, 17, 15]]
for (let dir of offsets[pceType]) {
if (pce == 10) dir *= -1;
let dst = src + dir;
while (!(dst & 0x88)) {
let capSq = dst;
if (pceType == 2 && dst == ep) capSq ^= 16;
let capPce = board[capSq];
if (capPce & side) break;
if (ep > 0 && board[ep] && ((dst-ep)<2) && ((ep-dst)<2)) return[];
if (pceType == 2) {
if (!((dst-src) & 7) && capPce) break;
if (((dst-src) & 7) && !capPce && capSq != ep) break;
} if ((capPce & 7) == 1) return []; //moves.push([src, dst]);
board[capSq] = 0; board[src] = 0; board[dst] = pce;
if (pceType == 1 && ((src == 116) || (src == 4))) {
switch(dst) {
case 118: board[117] = 13; board[119] = 0; break;
case 114: board[115] = 13; board[112] = 0; break;
case 6: board[5] = 21; board[7] = 0; break;
case 2: board[3] = 21; board[0] = 0; break;
}
} let oldCastle = castle;
castle &= board[src + 8]; castle &= board[dst + 8];
if (pceType == 2) {
if ((dst >> 4) == (side == 8 ? 0 : 7)) {
board[dst] = ((uProm > 0) ? uProm : 6) | side;
for (let p = 6; p > 2; p--)
moves.push([src, dst, p]);
} else moves.push([src, dst]);
} else moves.push([src, dst]);
if (src == uSrc && dst == uDst) {
ep = -1; if (pceType == 2) {
if (((src >> 4) == ((side == 8) ? 6 : 1)) &&
((dst >> 4) == ((side == 8) ? 4 : 3))) ep = dst ^ 16;
} else if (pceType == 1) {
if (src == 116) {
if (dst == 118) ep = 117;
if (dst == 114) ep = 115;
} else if (src == 4) {
if (dst == 6) ep = 5;
if (dst == 2) ep = 3;
}
} side = 24 - side; return 'make';
} board[dst] = 0; board[src] = pce; board[capSq] = capPce;
if (pceType == 1 && ((src == 116) || (src == 4))) {
switch(dst) {
case 118: board[119] = 13; board[117] = 0; break;
case 114: board[112] = 13; board[115] = 0; break;
case 6: board[7] = 21; board[5] = 0; break;
case 2: board[0] = 21; board[3] = 0; break;
}
} castle = oldCastle;
if (pceType == 2) {
if ((src >> 4) != ((side == 8) ? 6 : 1)) break;
if ((dst >> 4) != ((side == 8) ? 5 : 2)) break;
} else if (pceType == 1) {
if ((dir != 1) && (dir != -1)) break;
if (dir == 1) {
if (board[src + 2]) break;
if (side == 8 && !(castle & 1)) break;
if (side == 16 && !(castle & 4)) break;
} if (dir == -1) {
if (board[src - 2]) break;
if (board[src - 3]) break;
if (side == 8 && !(castle & 2)) break;
if (side == 16 && !(castle & 8)) break;
} if (src != ((side == 8) ? 116: 4)) break;
if (Math.abs(src-dst) > 1) break;
} if (capPce & (24 - side)) break;
if (!(pceType & 4) && pceType != 2 && pceType != 1) break;
dst += dir;
}
}
} return moves;
}
// GUI
function ui(dst) {
if (document.getElementById("board") == null) {
let size = (Math.floor(Math.min(window.innerWidth, window.innerHeight) / 8)) - 2;
let ui = ""; for (let i = 0; i < 120; i++)
ui += i & 8 && (i += 7) ? `<tr>` :`<th id="${i}"
onclick="let i = 2; while(i--) ui(parseInt(this.id));" style="
background-color: #${(((i%16+i/16|0)%2)?"777777":"dddddd")};
width: ${size}px;
height: ${size}px;
">`; document.write(`
<meta name="viewport" content="user-scalable=no">
<style>
.highlight { box-shadow: inset 0px 0px 3px 3px #ffbb00; }
.mate { box-shadow: inset 0px 0px 5px 5px red; }
</style>
<table id="board" style="
font-size: ${size-40}px;
cursor:default;
border-spacing: 0px;
display: grid;
place-items: center;
user-select: none;
border: 1px solid #777777;"
unselectable="on"
onselectstart="return false;"
onmousedown="return false;
">${ui}</table>`); board.fill(15);
let i = 8; while (i--) {
board[i] = (board[i+112] = [13, 11, 12, 14, 9, 12, 11, 13][i])+8;
board[i+16] = 18; board[i+32] = 0; board[i+48] = 0; board[i+64] = 0;
board[i+80] = 0; board[i+96] = 10;
} board[8] = 7; board[12] = 3; board[15] = 11;
board[120] = 13; board[124] = 12; board[127] = 14;
} let lock = 0; for (let sq in board) {
if (sq & 0x88) continue;
if (document.getElementById(sq).classList[0] == "highlight") lock = 1;
s=document.getElementById(sq);
s.classList.remove('highlight');
s.innerHTML = " \u265a\u265f\u265e\u265d\u265c\u265b--\u2654\u2659\u2658\u2657\u2656\u2655"[board[sq]&15];
} for (let move of movegen(-1, -1, -1)) {
let oldBoard = JSON.stringify(board), oldSide = side, oldEp = ep, oldCastle = castle;
movegen(move[0], move[1], (move.length == 3 ? move[2] : -1)); let isLegal = 1;
if (!movegen(-1, -1, -1).length) isLegal = 0; board = JSON.parse(oldBoard);
side = oldSide, ep = oldEp, castle = oldCastle;
if (!isLegal) continue; if (dst == move[0]) {
let s = -1; while (++s < 2) document.getElementById(move[s]).classList.add('highlight');
src = dst; lock = 1;
}
} if (lock) {
let oldBoard = JSON.stringify(board), oldSide = side, oldEp = ep, oldCastle = castle;
movegen(src, dst, prom); if (!movegen(-1, -1, -1).length)
board = JSON.parse(oldBoard), side = oldSide, ep = oldEp, castle = oldCastle;
}
} ui();
// DEBUG r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
/*board = [
21, 0, 0, 0, 17, 0, 0, 21, 7, 15, 15, 15, 3, 15, 15, 11,
18, 0, 18, 18, 22, 18, 20, 0, 15, 15, 15, 15, 15, 15, 15, 15,
20, 19, 0, 0, 18, 19, 18, 0, 15, 15, 15, 15, 15, 15, 15, 15,
0, 0, 0, 10, 11, 0, 0, 0, 15, 15, 15, 15, 15, 15, 15, 15,
0, 18, 0, 0, 10, 0, 0, 0, 15, 15, 15, 15, 15, 15, 15, 15,
0, 0, 11, 0, 0, 14, 0, 18, 15, 15, 15, 15, 15, 15, 15, 15,
10, 10, 10, 12, 12, 10, 10, 10, 15, 15, 15, 15, 15, 15, 15, 15,
13, 0, 0, 0, 9, 0, 0, 13, 13, 15, 15, 15, 12, 15, 15, 14
]; ui();*/
function print() {
let b = "";
for (let r = 0; r < 8; r++) {
for (let c = 0; c < 8; c++) {
let sq = r*16+c;
if (sq & 0x88) continue;
b += ".kpnbrq--KPNBRQ"[board[sq]&15];
} b += "\n";
} console.log(b, nodes);
}
nodes = 0; function perftDriver(depth, ply) {
if (!depth) { nodes++; return; }
for (let move of movegen(-1, -1, -1)) {
let oldBoard = []; let oldSide = side, oldEp = ep, oldCastle = castle;
for (let sq = 0; sq < 128; sq++) oldBoard[sq] = board[sq];
movegen(move[0], move[1], (move.length == 3 ? move[2] : -1));
if (!movegen(-1, -1, -1).length) {
for (let sq = 0; sq < 128; sq++) board[sq] = oldBoard[sq];
side = oldSide, ep = oldEp, castle = oldCastle;
continue;
} perftDriver(depth - 1, ply+1);
for (let sq = 0; sq < 128; sq++) board[sq] = oldBoard[sq];
side = oldSide, ep = oldEp, castle = oldCastle;
}
}
function perftTest(depth) {
nodes = 0;
console.log(' Performance test:\n');
resultString = '';
let startTime = Date.now();
let count = 0;
for (let move of movegen(-1, -1, -1)) {
let oldBoard = JSON.stringify(board), oldSide = side, oldEp = ep, oldCastle = castle;
movegen(move[0], move[1], (move.length == 3 ? move[2] : -1));
if (!movegen(-1, -1, -1).length) {
board = JSON.parse(oldBoard), side = oldSide, ep = oldEp, castle = oldCastle;
continue;
} let cumNodes = nodes;
perftDriver(depth - 1, 0);
board = JSON.parse(oldBoard), side = oldSide, ep = oldEp, castle = oldCastle;
let oldNodes = nodes - cumNodes; count++;
console.log(
' move' +
' ' + (count) + ((count < 9) ? ': ' : ': ') + String.fromCharCode(97 + (move[0] & 7)) +
(8 - (move[0] >> 4)) + String.fromCharCode(97 + (move[1] & 7)) + (8 - (move[1] >> 4)) +
' nodes: ' + oldNodes
);
}
resultString += '\n Depth: ' + depth;
resultString += '\n Nodes: ' + nodes;
resultString += '\n Time: ' + (Date.now() - startTime) + ' ms\n';
console.log(resultString);
} //perftTest(4); ui();
</script>
EDIT: I forgot to mention the most important benefit - current arch bypasses the main MicroMax search bottleneck - move ordering,
since moves are available as a list after move generation a conventional search might be applied. The downside is that obviously this
movegen is quite slow.