Hello, thank you for your response, and yeah i know that a proper pruning is the best.algerbrex wrote: ↑Thu Jul 08, 2021 10:43 pmI would agree with what Marcel said. I'm also in the same position as you and very much still a novice when it comes to chess programming. But one important lesson I've learned from talking with more experienced chess programmers on here and from my own research is that move generation speed isn't nearly as important as you might think it is when trying to create a decently strong engine.pedrojdm2021 wrote: ↑Thu Jul 08, 2021 6:52 pm Hello, i have been doing some research into my engine's code, and i have found that one of the main causes of the slowness (that the speed actually is nearly 300.000 nps) caused by the move generation:
Instead, focus on getting a working move generator, and then focus your efforts on creating a solid search and evaluation phase using alpha-beta pruning with good move ordering (e.g. Most-valuable-victim, Least-valuable-attacker), material count, and piece-square tables. You might be surprised at how much quicker your engine seems during the search phase, since, if you have good pruning, your engine has to search only a fraction of the full move tree to get the same quality results as searching the whole tree.
For example, in one of my previous iterations of Blunder (my engine), when I went from pure negamax, to adding alpha-beta pruning and MvvLva move ordering, my engine went from searching ~4M nodes in the Kikipete position to only searching ~4k, a fraction of the move tree. And it still found the best move.
So my advice to you as someone who's in a similar position is to focus right now on getting a working move generator. And really make sure it's working. If you google "perft test positions" or "perft test suite", you'll find different collections of positions to test your engine with. Once you finish your move generator, write a little testing script to go through each position and make sure you get the correct numbers at each depth.
Or if you'd like, I'd also be happy to post the testing suite I've been using. It's an amalgamation of tests I've found myself online and it seemed to work well and rooting out any nasty bugs I had left in the move generator.
I'm currently in the process of re-writing Blunder since I wasn't happy with the code base, and because I realized I needed a better plan for developing Blunder. But anyway, the way I'm detecting and finding pin rays in this version is by having a 64x64 array. The array has a pre-calculated bitboard containing the line between any two squares that are aligned. Here's the relevant code:pedrojdm2021 wrote: ↑Thu Jul 08, 2021 6:52 pm my question is, any of you have implemented the "pin rays" ? if yes how did you do that? i have some ideas but i don't have a very clear solution in mind, thank you all!
And here's how I use it to detect pinned pieces:Code: Select all
func sqOnBoard(sq int) bool { return sq >= 0 && sq <= 63 } func distance(sq1, sq2 int) int { return max(abs(rankOf(sq2)-rankOf(sq1)), abs(fileOf(sq2)-fileOf(sq1))) } func pseduoSlidingAttacks(deltas []int, square int) (attacks Bitboard) { for _, delta := range deltas { for to := square + delta; sqOnBoard(to) && distance(to, to-delta) == 1; to += delta { setBit(&attacks, to) } } return attacks } func lineBetween(deltas []int, sq1, sq2 int) (line Bitboard) { for _, delta := range deltas { for to := sq1 + delta; sqOnBoard(to) && distance(to, to-delta) == 1; to += delta { setBit(&line, to) if to == sq2 { break } } if hasBitSet(line, sq2) { break } else { line = 0 } } return line } var LinesBewteen [64][64]Bitboard var Directions []int = []int{North, South, East, West, NorthEast, SouthEast, NorthWest, SouthWest} func init() { for from := 0; from < 64; from++ { attacks := pseduoSlidingAttacks(Directions, from) for attacks != 0 { to, _ := popLSB(&attacks) LinesBewteen[from][to] = lineBetween(Directions, from, to) } } }
The nice thing about this approach is that both of the arrays used can be pre-computed before the engine starts, so the pin ray doesn't need to be generated on the fly.Code: Select all
func genPinnedPieces(board *Board) (pinnedBB uint64) { enemyBB := board.Sides[board.ColorToMove^1] enemyBishops := board.Pieces[board.ColorToMove^1][Bishop] enemyRooks := board.Pieces[board.ColorToMove^1][Rook] enemyQueens := board.Pieces[board.ColorToMove^1][Queen] usBB := board.Sides[board.ColorToMove] kingBB := board.Pieces[board.ColorToMove][King] pinnersBB := (genIntercardianlMovesBB(kingBB, enemyBB)&(enemyBishops|enemyQueens) | genCardianlMovesBB(kingBB, enemyBB)&(enemyRooks|enemyQueens)) kingPos := getLSBPos(kingBB) for pinnersBB != 0 { pinnerPos, _ := popLSB(&pinnersBB) pinnedBB |= LinesBewteen[kingPos][pinnerPos] & usBB } return pinnedBB }
I can't say this approach is original to me though. I got the idea from reading through the source code of Stockfish and hearing some members on here talk about similar ideas.
Some things that i actually have:
- I did the perft test, they all pointed out correct results.
- i am not using pure negamax with alpha-beta, i am using a negamax version with this set of features:
> Principal variation search
> Quiescense search
> Null Move pruning
> Late move reductions
> Transposition tables
> Futility pruning
the number of nodes searched are between 1 to 2 millons depending on the position, and even with 1millon, the application searches in 3.60 seconds 1.4 millons of positions :/ and it is clearly a slowness of: move generator or search