Advice on optimizing my move generation

[algerbrex]

Code: Select all

Total nodes: 4085603

real    1m53.013s
user    1m18.742s
sys     0m15.138s

Any idea why real is so much longer (about 20 seconds) than the cpu-time for user and system combined?
Also: 15 seconds for system? Is your program causing swapping? Or is it emitting a lot of text to the terminal?

Well, my program is using a kind of perft divide function, so it prints out all the moves and their node counts at the depth it's run at. And no, I'm not entirely sure about the discrepancy between real and cpu-time. I'll have to do some digging.

[JVMerlino]

As others have said, getting a decent engine doesn't require a super-fast move generator. Once you have a strong search and reasonably complex evaluation, the move generation will only take a small percentage of overall search time. So spending a lot of time optimizing it will only result in a very small increase in strength.

So don't be disappointed about your current performance. I just ran Myrddin on the kiwipete position, perft 6, WITH bulk counting (but no hash), and it took 3 minutes.

[algerbrex]

As others have said, getting a decent engine doesn't require a super-fast move generator. Once you have a strong search and reasonably complex evaluation, the move generation will only take a small percentage of overall search time. So spending a lot of time optimizing it will only result in a very small increase in strength.

So don't be disappointed about your current performance. I just ran Myrddin on the kiwipete position, perft 6, WITH bulk counting (but no hash), and it took 3 minutes.

Yeah, that's what I've seen a couple of other people say , so that's quite encouring. My goal ELO would be anywhere between 2000-1500 ELO, so if my move generator will get me there, I can work with that!

[maksimKorzh]

How you deal with attacks (king in check detection)?
On the fly generation or lookup?
In my experience attacks detection is the biggest time eater,
some other potential slowdowns might occur because of data structures being used during move generations
like putting moves onto stack or similar.

Hi and yes, that's also where I suspect I'm being very inefficient. Right now, I'm detecting if the king is left in check by making a movie using a isSquareAttacked method which does the usual approach of sitting a super-piece on the king square, radiating out rays, and seeing if they hit any enemy pieces. Here is the code:

Code: Select all

func squareIsAttacked(board *Board, square int, whiteToMove bool) bool {
	enemyColor := White
	pawnAttackLeftDelta := SouthWestDelta
	pawnAtttackRightDelta := SouthEastDelta
	if whiteToMove {
		enemyColor = Black
		pawnAttackLeftDelta = NorthWestDelta
		pawnAtttackRightDelta = NorthEastDelta
	}

	// Send out rays from the square position. If any of the rays intersect
	// with an enemy rook, bishop, or queen, then the square is attacked.
	for _, delta := range QueenDeltas {
		to := Mailbox120[Mailbox64[square]+delta]
		for to != -1 && board.Pieces[to] == NoPiece {
			to = Mailbox120[Mailbox64[to]+delta]
		}
		if delta == NorthDelta || delta == SouthDelta || delta == EastDelta || delta == WestDelta {
			if to != -1 && board.Colors[to] == enemyColor && (board.Pieces[to] == Rook || board.Pieces[to] == Queen) {
				return true
			}
		} else if delta == NorthEastDelta || delta == SouthEastDelta || delta == NorthWestDelta || delta == SouthWestDelta {
			if to != -1 && board.Colors[to] == enemyColor && (board.Pieces[to] == Bishop || board.Pieces[to] == Queen) {
				return true
			}
		}
	}
	// Send out knight rays from the square position, if they intersect with an enemy knight,
	// the square is attacked.
	for _, delta := range KnightDeltas {
		to := Mailbox120[Mailbox64[square]+delta]
		if to != -1 && board.Colors[to] == enemyColor && board.Pieces[to] == Knight {
			return true
		}
	}
	// Lastly, check if the square is attacked by a pawn or a king.
	for _, delta := range KingDeltas {
		to := Mailbox120[Mailbox64[square]+delta]
		if to != -1 && board.Colors[to] == enemyColor && board.Pieces[to] == King {
			return true
		} else if delta == pawnAttackLeftDelta || delta == pawnAtttackRightDelta {
			if to != -1 && board.Colors[to] == enemyColor && board.Pieces[to] == Pawn {
				return true
			}
		}
	}
	// If we've made it to here without returing early, the square is not attacked and safe.
	return false
}

This is working excellent in terms of being bug free, but I do feel like there are faster ways of check detection. But I couldn't find any good resources for this related to mailbox representations of boards. Everything is related to bitboards, which I've already seen, since I attempted to write my first three engines using those.

Got you, well my engine in Javascript (5x times slower than C because of Javascript itself) runs this position in around 3 seconds:

Code: Select all

Performance test:

wukong.js:881    move 1:  d5d6     nodes: 79551
wukong.js:881    move 2:  d5e6     nodes: 97464
wukong.js:881    move 3:  a2a3     nodes: 94405
wukong.js:881    move 4:  a2a4     nodes: 90978
wukong.js:881    move 5:  b2b3     nodes: 81066
wukong.js:881    move 6:  g2g3     nodes: 77468
wukong.js:881    move 7:  g2g4     nodes: 75677
wukong.js:881    move 8:  g2h3     nodes: 82759
wukong.js:881    move 9:  e5d3     nodes: 77431
wukong.js:881    move 10: e5g4     nodes: 79912
wukong.js:881    move 11: e5c4     nodes: 77752
wukong.js:881    move 12: e5d7     nodes: 93913
wukong.js:881    move 13: e5f7     nodes: 88799
wukong.js:881    move 14: e5c6     nodes: 83885
wukong.js:881    move 15: e5g6     nodes: 83866
wukong.js:881    move 16: c3d1     nodes: 84782
wukong.js:881    move 17: c3b1     nodes: 84773
wukong.js:881    move 18: c3b5     nodes: 81498
wukong.js:881    move 19: c3a4     nodes: 91447
wukong.js:881    move 20: d2c1     nodes: 83037
wukong.js:881    move 21: d2e3     nodes: 90274
wukong.js:881    move 22: d2f4     nodes: 84869
wukong.js:881    move 23: d2g5     nodes: 87951
wukong.js:881    move 24: d2h6     nodes: 82323
wukong.js:881    move 25: e2d1     nodes: 74963
wukong.js:881    move 26: e2f1     nodes: 88728
wukong.js:881    move 27: e2d3     nodes: 85119
wukong.js:881    move 28: e2c4     nodes: 84835
wukong.js:881    move 29: e2b5     nodes: 79739
wukong.js:881    move 30: e2a6     nodes: 69334
wukong.js:881    move 31: a1b1     nodes: 83348
wukong.js:881    move 32: a1c1     nodes: 83263
wukong.js:881    move 33: a1d1     nodes: 79695
wukong.js:881    move 34: h1g1     nodes: 84876
wukong.js:881    move 35: h1f1     nodes: 81563
wukong.js:881    move 36: f3f4     nodes: 90488
wukong.js:881    move 37: f3f5     nodes: 104992
wukong.js:881    move 38: f3f6     nodes: 77838
wukong.js:881    move 39: f3g3     nodes: 94461
wukong.js:881    move 40: f3h3     nodes: 98524
wukong.js:881    move 41: f3e3     nodes: 92505
wukong.js:881    move 42: f3d3     nodes: 83727
wukong.js:881    move 43: f3g4     nodes: 92037
wukong.js:881    move 44: f3h5     nodes: 95034
wukong.js:881    move 45: e1g1     nodes: 86975
wukong.js:881    move 46: e1c1     nodes: 79803
wukong.js:881    move 47: e1f1     nodes: 77887
wukong.js:881    move 48: e1d1     nodes: 79989
wukong.js:893 
   Depth: 4
   Nodes: 4085603
    Time: 2513 ms

You can play around with it live here:
https://maksimkorzh.github.io/wukongJS/wukong.html

to run perft on this position:
1. Click FEN button
2. Open DevTools in the browser (Ctrl-Shift-I or rightclick -> inspect element)
3. Navigate to "Console" tab and type: engine.perft(4) or whatever depth you like
This would run perft in console (I've pasted current output from there)

My engine uses exactly the same is square attacked implementation as yours.
The rest of a movegen is extremely simple and didactic as well (all my engines are didactic))) haha))) )
Here's the source code:
https://github.com/maksimKorzh/wukongJS (Project)
https://github.com/maksimKorzh/wukongJS ... /wukong.js(Source code - 1 file only!)
It can be played as UCI engine as well if hack around a bit.

For this sort of an implementation class this is propbably the fastest implementation available.
I believe that further speedups are tight with redesigning the engine fully or partially (which ruins current "bugfreeness" )

A totally next level many many times faster can be found in HGM's sources:
QPerft (lighting fast perft, around as stockfish or even faster depending on compilation):
https://github.com/maksimKorzh/hgm-mail ... n/qperft.c

The engine from "Mailbox trials thread":
https://github.com/maksimKorzh/hgm-mail ... ailbox7b.c

These to are not recalculating attacks on the fly, see this thread for more details:
http://talkchess.com/forum3/viewtopic.php?f=7&t=76773

Hope it helps!

[emadsen]

I am happy to say that after running my move generator through a perft suite of 30-40 different positions at depth=5, it seems to be working correctly. My issue now is the speed.

Hi Christian. Welcome to the chess programming community. Congrats on writing a correct move generator. That's a big milestone! Are you sure it's correct? Here's a good perft test suite that has many corner cases.

In my opinion, you should focus on perft correctness and and search speed. Perft speed is not important for the primary purposes of chess engines: playing games against other engines and aiding us humans in analyzing games. Perft doesn't do any of the "bookkeeping" necessary for good move ordering, which is critical for engine strength. So fast perft doesn't imply strong engine.

I go further than most, in that I've designed my perft method to execute the same call stack as the search method does. So correct perft counts give me confidence search is examining all the moves it should (exempting pruning).

Others have given good advice in previous comments, especially cautioning against allocating memory during search. That kills performance, especially in a garbage collected language like Go. Allocate all data structures when the engine starts. Use statically-sized arrays, not dynamically sized lists (for the same reason, to avoid alloc and GC). Iterate over arrays using for loops, not foreach (for the same reason, avoiding alloc and GC). In C# enumerators alloc. Not sure about Go. Avoid other language features during search that harm performance: no floating point math (instead calc at engine start and store ints in arrays for lookup during search, eval should be pure int math), no lambda methods (they allocate a delegate, at least in C#), etc.

[Henk]

Even if move generation works perfectly it is not that easy to keep it that way. After some time code changes and being to lazy or just forget to repeat all perft tests.

[mvanthoor]

Even if move generation works perfectly it is not that easy to keep it that way. After some time code changes and being to lazy or just forget to repeat all perft tests.

Why would the move generator chance "after some time" ?

It is a completely independent part of my engine. Apart from some tiny changes (Rust telling me: "This is going to change in version 2021, the syntax is going to be like this now") and some updates in the comments, the move generator hasn't changed for almost 10 months.

Actually, most of the engine never changes. The biggest changes can be found in the search, and later, the evaluation. Many parts probably won't change for years to come, apart from updating them to current Rust standards, and to call new functionality. If you're constantly having to change things throughout your entire engine when you create new functionality, you've probably made some design mistakes.

[Henk]

I always have design mistakes even if I don't. My code always changes even if it doesn't have to.
Code never perfect. Ideas changing all the time.

[niel5946]

My goal ELO would be anywhere between 2000-1500 ELO, so if my move generator will get me there, I can work with that!

An elo below 2000 doesn't require a good move generator at all. I think with a descent evaluation (material and psqt) and a bug-free search, you can definitely get to 1800 with a, relatively, slow move generator.
Additionally, some tricks can be done in search to completely avoid generating some of the moves. Since captures are usually better than quiet moves, you can start by generating the captures and trying them. If they are not good enough, you can then generate the quiets, but if the captures are good enough, you saved time by not generating the rest of the moves. This is called staged move generation. Once you're at 2000, you can look into that and move generator speedup

[JohnWoe]

Perft to me is pointless. Mayhem has no perft and never will. Havoc has it but it's probably going to removed. I can't even remember the time Mayhem had mgen bugs.

How super fast move generator translates to search speed is very important. Especially in Mayhem I want a list of moves ASAP.
If you make your engine faster that is +Elo. No need to run 500k games. It's simple as that.
In Mayhem the more nodes I search the better hashtable it produces. So that's why super fast move generator is important.

UCI has tons of overhead too. You are starting from "tabula rasa" every move and playing a long list of moves to empty board...