Golang chess engine I'm hacking up
New chess engine - Ra the sun god succeeded Apep the serpent god.
My last chess engine was written in C++ and also available on Github.
Trying a few different things with this one (different language, different board representation) and trying to keep the code cleaner.
Basically for the hash move we can just call into the move generator to validate it and then search it.
This seems like it could be a big savings if the hash move can force an alpha/beta cutoff. Killer move plays into this too.
I need a way to run through a bunch of tactical scenarios similar to apep's tactics module. https://github.com/tildedave/apep-chess-engine/blob/master/src/tactics.cpp
In these situations we should be able to quickly find mate by incentivizing pushing the enemy king to the edge of the board.
(venv) dave@zwingli ra-chess-engine % go build && ./ra-chess-engine --tactics --epd test-suites/basic.epd -tacticsthinkingtime 5000 -epdregex testGuard
........
........
...K.Pk.
........
........
........
........
........
8/8/3K1Pk1/8/8/8/8/8 w - - 0 1
1 0 0 5 Kc5
1 210 0 11 Ke5
2 210 0 27 Ke5 Kg5
3 210 0 113 Ke5 Kf7 Kf5
3 220 0 249 Ke6 Kg5 f7 Kf4
4 230 0 429 Ke6 Kh6 Kf5 Kh5
4 1190 0 517 Ke7 Kg5 f7 Kf4 f8=Q Ke3
5 1190 0 850 Ke7 Kg5 f7 Kf4 f8=Q Ke3
6 1200 0 2105 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3
7 1200 0 4680 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3
8 1200 0 11982 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Kc5 Kc3
9 1200 0 26056 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Kc5 Kc3
10 1200 0 50692 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Kc5 Ke3 Kc4 Ke4
11 1200 0 71128 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Ke5 Kc3 Qc5 Kb2 Qc4
11 1210 0 82226 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Kd6 Kg4 Kc5 Kg3
12 1210 0 107827 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Kd6 Kg4
13 1210 0 310424 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Kd6 Kg4 Kc5 Kg3 Kc4 Kg2
14 1210 6 595411 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Kd6 Kg4 Kc5 Kg3 Kc4 Kg2
15 1230 6 1597498 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Qf3 Kg6 Qg4 Kh6 Qf5 Kg7 Qg5 Kh7 Kd6 Kh8
16 1230 26 2781959 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Qf3 Kh4 Qg2
17 1230 18 4462667 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Qf3 Kh4 Qg2 Kh5 Kd6 Kh4 Kd5 Kh5 Qg1 Kh4
18 1230 56 6600722 Ke6 Kh6 f7 Kg7 Ke7 Kg6 f8=Q Kg5 Qf3 Kh4 Qg2 Kh5 Kd6 Kh4 Kd5
18 Mate8 285 10745165 Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Kd5 Kc3 Qg7 Kb3 Kc5 Ka2 Kc4 Ka3 Qa1#
[testGuard - OK] expected=Ke5 Ke6 Ke7 move=Ke7 result=d6e7 (time=2.859346062s, value=Mate(8), depth=18, stats=[nodes=10745390, leafnodes=3840000, branchnodes=5143101, qbranchnodes=1762289, tthits=13940505, cutoffs=1500760, hash cutoffs=1214966, null cutoffs=2920214, killer cutoffs={1: 148729, 2: 22195}, qcutoffs=32, qcapturesfiltered=0], pv=Ke7 Kg5 f7 Kf4 f8=Q Ke3 Kd6 Kd3 Kd5 Kc3 Qg7 Kb3 Kc5 Ka2 Kc4 Ka3 Qa1#)
Complete. 1/1 positions correct (100.00%)
Final stats [nodes=10745390, leafnodes=3840000, branchnodes=5143101, qbranchnodes=1762289, tthits=13940505, cutoffs=1500760, hash cutoffs=1214966, null cutoffs=2920214, killer cutoffs={1: 148729, 2: 22195}, qcutoffs=32, qcapturesfiltered=0]%
Takes 4 seconds on my macbook now, really this should be findable very quickly.
Okay, engine needs to get better at tactics. Various things I can do (brainstorm):
I'll start with the basic suite in the repo. Failing positions are:
[testWac002 - FAIL] expected=Rxb2 result=c3 (score=-100, nodes=180869499585, depth=12)
[testWcsac002 - FAIL] expected=Re8 result=Qxc4 (score=80, nodes=17816962, depth=6)
[testWac247 - FAIL] expected=Rxb5 result=Qc5 (score=30, nodes=5541963, depth=5)
[testWcsac527 - FAIL] expected=Qxc6 result=hxg4 (score=100, nodes=3226503, depth=6)
[testBwtc39 - FAIL] expected=Qb6 result=Rxb7 (score=-115, nodes=2760507, depth=4)
[Event "Computer Chess Game"]
[Site "zwingli.local"]
[Date "2020.08.19"]
[Round "-"]
[White "ra v0.0.1"]
[Black "Fairy-Max 5.0b"]
[Result "1-0"]
[TimeControl "40/300"]
[Annotator "1. +0.15 1... +0.26"]
1. Nf3 {+0.15/8} Nf6 {+0.26/9 13} 2. e3 {+0.55/7 5} c5 {+0.15/9 12} 3. Be2
{+1.00/7 5} d6 {-0.01/9 4} 4. O-O {+1.00/8 5} Nc6 {+0.03/9 6} 5. d4
{+1.00/7 5} Bf5 {+0.03/9 4} 6. Nc3 {+1.40/7 5} Qa5 {+0.07/9 6} 7. d5
{+1.60/7 5} Nb4 {-0.03/9 6} 8. Bb5+ {+1.50/7 5} Kd8 {+0.03/9 7} 9. Ng5
{+1.60/7 5} Bg6 {+0.26/9 7} 10. Bd3 {+1.85/7 5} Nxd3 {+0.43/10 7} 11. cxd3
{+2.05/7 5} h6 {+0.42/10 9} 12. Nge4 {+2.40/7 5} Nxe4 {+0.43/10 5} 13. dxe4
{+2.00/8 5} Qc7 {+0.34/10 7} 14. f4 {+2.45/6 5} e5 {+0.42/11 8} 15. a3
{+2.45/6 5} exf4 {+0.40/11 9} 16. exf4 {+2.95/7 5} Qb6 {+0.32/10 19} 17.
Rf2 {+3.55/7 5} f6 {+0.26/10 12} 18. Be3 {+3.45/7 5} h5 {+0.46/9 7} 19. f5
{+3.65/7 5} Bf7 {+0.41/9 3} 20. Rd2 {+3.40/7 5} g6 {+0.40/9 4} 21. Qf3
{+3.65/7 5} Bh6 {+0.39/10 9} 22. fxg6 {+3.15/8 5} Bxe3+ {-0.75/11 5} 23.
Qxe3 {+2.30/7 5} Bxg6 {-1.05/11 4} 24. Rf2 {+2.30/6 5} Ke7 {-0.31/9 5} 25.
Qh3 {+2.30/6 5} Bf7 {+0.08/9 3} 26. Qf3 {+3.30/7 5} Rh6 {+0.08/10 9} 27.
Rc1 {+2.60/7 5} Rg6 {+0.18/9 7} 28. Rd1 {+2.25/6 5} Rd8 {+0.28/9 5} 29. Qe2
{+2.75/7 5} a5 {+0.38/9 4} 30. Rd2 {+2.35/6 5} Rg4 {+0.37/9 8} 31. Qf3
{+2.60/6 5} Rg6 {+0.00/12 3} 32. Ne2 {+2.30/6 5} h4 {+0.16/10 5} 33. Qe3
{+2.90/7 5} a4 {+0.36/10 6} 34. Nc3 {+3.15/7 5} Qa7 {+0.34/10 19} 35. Rf5
{+2.60/6 5} b6 {+0.33/8 2.4} 36. Qf4 {+2.75/6 5} h3 {+0.09/10 5} 37. Rf2
{+3.00/7 5} Rdg8 {-0.61/10 4} 38. Rxf6 {+3.35/8 5} Rxg2+ {-1.45/11 3} 39.
Rxg2 {+3.90/8 5} Rxg2+ {-1.88/12 5} 40. Kh1 {+3.95/8 5} Kf8 {-2.90/12 5}
41. Rxd6 {+3.95/7 5} Qe7 {-1.82/10 5} 42. Qh6+ {+3.70/8 5} Rg7 {-1.75/11 5}
43. Rf6 {+3.75/8 5} b5 {-1.24/11 4} 44. Qh8+ {+4.10/8 5} Rg8 {-0.62/11 6}
45. Qh6+ {+4.00/9 5} Rg7 {+0.00/17 6} 46. d6 {+3.95/8 5} Qd7 {-2.74/12 6}
47. Qh8+ {+4.10/8 5} Rg8 {-1.64/11 6} 48. Qh5 {+3.85/9 5} c4 {-1.86/12 13}
49. Nxb5 {+4.40/8 5} c3 {-2.59/12 5} 50. Nxc3 {+5.80/9 5} Rg7 {-2.87/12 12}
51. Qh8+ {+5.95/8 5} Rg8 {-3.37/12 5} 52. Qh6+ {+5.75/8 5} Ke8 {-3.63/12 6}
53. Qh7 {+5.95/8 5} Qa7 {-3.18/12 13} 54. Rf1 {+6.30/8 5} Qd7 {-4.50/11 5}
55. Nb5 {+6.30/8 5} Rf8 {-5.81/13 6} 56. Qh4 {+7.70/8 5} Qd8 {-6.95/13 6}
57. Qxh3 {+8.45/8 5} Qd7 {-7.48/13 6} 58. Rf5 {+8.60/8 5} Kd8 {-7.35/12 7}
59. Qh4+ {+8.60/7 5} Kc8 {-7.35/12 11} 60. Qe7 {+7.85/7 5} Qxe7
{-6.37/14 9} 61. dxe7 {+6.90/10 5} Re8 {-5.60/14 9} 62. Rxf7 {+7.00/10 5}
Kd7 {-5.87/14 5} 63. Nc3 {+7.00/10 5} Rxe7 {-6.16/14 4} 64. Rxe7+
{+7.00/10 5} Kxe7 {-7.49/17 4} 65. Nxa4 {+8.80/13 5} Kd6 {-12.53/16 10} 66.
Nb6 {+13.70/14 5} Kc5 {-11.11/16 8} 67. h4 {+14.00/14 5} Kxb6 {-11.09/19 5}
68. h5 {+16.70/17 5} Kc5 {-17.51/18 4} 69. h6 {+16.70/15 5} Kd4
{-1000.27/17 5} 70. h7 {+16.70/13 5} Kxe4 {-1000.13/17 11} 71. h8=Q
{+18.20/12 5} Kd5 {-1000.09/16 9} 72. a4 {+18.60/12 5} Kd6 {-1000.07/15 8}
73. a5 {+19.30/11 3} Kc5 {-1000.06/15 6} 74. a6 {+18.20/8 0.8} Kb6
{-1000.05/16 7} 75. Qf6+ {+18.20/6 0.1} Kc5 {-1000.04/28 4} 76. a7
{+18.90/6 0.1} Kc4 {-1000.03/28 0.2} 77. a8=Q {+18.65/4 0.1} Kd3
{-1000.02/28 0.1} 78. Qc3+ {+18.65/2 0.1} Ke2 {-1000.01/28 0.1} 79. Qaf3#
{Xboard adjudication: Checkmate} 1-0
Some extra stuff for search:
With evaluation focused on material it is hard for the search to get out of the earlier search phases. More implementation here will help the search prune what a good or bad position is more effectively which means it should be able to search deeper.
Static exchange evaluation is a way to prioritize only "good" captures in quiescent search. I think Apep used SEE for a little while (the code is there but unused) and then switched to MVVLVA (most valuable victim least valuable attacker). MVVLVA makes sense for move ordering.
SEE might be useful for quiescent search so we don't spent time doing things like queen takes defended pawn, pawn takes queen, etc.
https://www.chessprogramming.org/MVV-LVA
https://www.chessprogramming.org/Static_Exchange_Evaluation
Currently it's just sort of aping the regular search by running through QUIESCENT_SEARCH_DEPTH extra positions. This happens to be okay for the positions I've given it but it's a big hindrance for engine play where a better engine will give a long forcing variation while Ra just gave up after QUIESCENT_SEARCH_DEPTH.
What it should be doing is following 'forcing lines' to their conclusion. So it should be seeing chains of 5-6 forced captures to the end and seeing the material balance on the board then. A "forcing line" could be a capture, a check, a pawn being pushed to the 7th rank, etc.
Smart quiescent search is a great differentiator to the engine since it finds winning lines earlier in the search tree and so can prune later positions a lot better.
A mistake I made with Apep was not being smarter about how long these lines go, and I'm pretty sure that following quiescent search lines "too deep" is a big reason that it doesn't get out of certain positions.
Walkthrough of Stockfish evaluation function here: https://hxim.github.io/Stockfish-Evaluation-Guide/
Not sure if this will make a big difference but we actually don't need to order everything, we really just need a reasonable first two or three moves to look at to cutoff other leaves in the tree.
Kind of want to switch back to bitboards now that I've tried the array-based approach out and have some decent infrastructure in place. Probably it would be good to keep some of the existing code around.
The way I'm using the timer isn't correct. It will only output a move after thinkingTimeMs has elapsed without a ThinkingOutput.
for {
select {
case bestResult = <-resultCh:
logger.Println("New result:")
logger.Println(SearchResultToString(bestResult))
thinkingChan <- ThinkingOutput{
ply: bestResult.depth,
score: bestResult.value,
time: bestResult.time,
nodes: bestResult.nodes,
pv: bestResult.pv,
}
if bestResult.flags == CHECKMATE_FLAG || bestResult.flags == STALEMATE_FLAG {
logger.Println("Best result is terminal, time to stop thinking")
break ThinkingLoop
}
case <-time.After(time.Duration(thinkingTimeMs) * time.Millisecond):
logger.Println("Thinking time is up!")
break ThinkingLoop
}
}What I think I can do instead is just use the default case here to check the time elapsed and conditionally break. I also believe the 'best result is terminal time to stop thinking' logic is incorrect and needs to be moved to the iterative search function.
Now that the hash key is functional we can use it to shortcircuit positions that we've already seen.
Would be nice to use some processor instructions for some frequent bit manipulations, notably bits.OnesCount64 and bits.TrailingZeros64. Doing an objdump on the resulting binary indicates OnesCount64 isn't using POPCNT (for example).
https://stackoverflow.com/questions/2951028/is-it-possible-to-include-inline-assembly-in-go-code
Currently the search abort procedure doesn't work, it just keeps going until the position has been completely searched, leading to issues where the transposition table is still being written even after it's made the move. We would ideally be able to keep the transposition table from previous moves for use in future ones.
One way to fix this is to have a pointer on the BoardState that we check periodically in the search algorithm.
[Event "Computer Chess Game"]
[Site "zwingli.local"]
[Date "2018.09.16"]
[Round "-"]
[White "ra v0.0.1"]
[Black "apep 0.1.0"]
[Result "0-1"]
[TimeControl "40/300"]
[Annotator "1. +0.00 1... -0.17"]
1. Nc3 {+0.00/7} d5 {-0.17/8 8} 2. Rb1 {+0.00/7 5} d4 {+0.58/8 8} 3. Ra1
{+0.00/7 5} dxc3 {+2.63/8 8} 4. bxc3 {-3.00/6 5} Qd6 {+2.45/7 8} 5. d4
{-3.00/7 5} Nf6 {+2.61/7 8} 6. Be3 {+2.00/7 5} Nc6 {+2.81/7 8} 7. Qd2
{+2.00/7 5} Qa3 {+3.14/7 9} 8. Qc1 {+2.00/7 5} Qxc3+ {+4.70/8 8} 9. Qd2
{-4.00/7 5} Qxa1+ {+10.18/9 8} 10. Qd1 {-10.00/8 5} Qxa2 {+9.94/8 8} 11. f3
{+7.00/7 5} Nd5 {+10.33/7 8} 12. Qd2 {+9.00/7 5} Qa1+ {+11.04/7 8} 13. Qc1
{+9.00/7 5} Nxe3 {+13.30/9 8} 14. Qxa1 {-13.00/8 5} Nxc2+ {+13.30/9 8} 15.
Kf2 {-14.00/8 5} Nxa1 {+13.34/10 8} 16. Nh3 {-14.00/8 5} Bxh3 {+14.47/8 8}
17. gxh3 {-14.00/8 5} Nxd4 {+14.89/10 8} 18. Bg2 {+14.00/9 5} Ndb3
{+15.30/8 8} 19. Rg1 {+14.00/7 5} O-O-O {+16.40/9 8} 20. Rh1 {+14.00/7 5}
e5 {+17.13/9 8} 21. Rg1 {+14.00/7 5} Bc5+ {+20.83/9 7} 22. e3 {+14.00/7 5}
Rd2+ {+23.95/9 8} 23. Kg3 {-18.00/8 5} Bxe3 {+23.87/9 7} 24. f4
{+15.00/7 5} exf4+ {+25.08/8 7} 25. Kh4 {+14.00/7 5} Bxg1 {+25.34/8 7} 26.
Bf3 {+21.00/7 5} Nd4 {+25.55/8 7} 27. Be2 {+21.00/7 5} Rxe2 {+149.93/5 0.1}
28. Kh5 {-1000.00/6 5} Rg2 {+149.95/6 0.1} 29. h4 {-1000.00/6 5} Nf5
{+149.97/2 0.1} 30. h3 {-1000.00/8 5} g6# {+149.99/2 0.1}
{Xboard adjudication: Checkmate} 0-1
Transposition Table
Switch move generation to bitboards
Perft is pretty slow compared to some people on the internet. Golang is slower than C++ (of course) but I think the main issue is the slices in move generation which roughly is how Apep did it. I'll need to review how often engines do this so we can crunch through more positions per second :)
Can't detect drawn positions without a capture or pawn move without coding this
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.