I have been learning chess (again) and how to program a chess engine (for the first time) over the last month. After skimming some introductory texts, I was convinced that building a simple chess engine one that would put up a fair fight against a casual player would take no more than a few days.
I was wrong.
But I made it there in the end and created a toy chess engine (healeycodes/andoma) that I am proud of. It can play a game of chess and solve simple chess puzzles like mate-in-two or mate-in-three. It has a slim UCI interface which means it can be hooked up to lichess.org via lichess-bot a bridge between the lichess API and chess bots.
The first speed bump in its development was grasping the computational the complexity of chess how fast, and wide, the search tree grows. When a chess game starts, white can open in twenty different ways and black can respond in twenty different ways also. After the first full turn, there are 400 variations possible. After the third full turn, there are over 119 million.
Claude Shannon calculated that there are around 10^120 possible games of chess in his seminal paper Programming a Computer for Playing Chess in 1950. In Rage Against the Machines, Nate Silver quotes Diego Rasskin-Gutman, who said:
There are more possible chess games than the number of atoms in the universe.
Given unlimited resources, it actually doesnt take many lines of code to calculate every legal variation of chess. Here, the Python package python-chess is used for board representation and legal move generation.
This program throws a RecursionError and prints 59691 the number of different positions the search tree contained when it crashed. All we need to fix this, is another universe to run the program in.
Given that there are computational limits to abide by, as well as the time control rules of chess, improvements over a naive brute force search must be made.
In order to search for good positions, it is necessary to understand what makes a good position good. The most simplistic way of describing a positions strength is to compare the total value material of each side.
Tomasz Michniewski, author of the Simplified Evaluation Function, defined some values that are designed specifically to compensate for the lack of any other chess knowledge. This is perfect for me a beginner chess player.
This snippet sums the material on the initial board using Michniewskis piece values.
Michniewski also provides piece-square tables, which alter the value of a piece depending on which square it sits on. For example, its better for pawns to progress up the board and its better for knights to be near the center of the board.
The bonus of a square may be positive, neutral, or negative. The piece-square tables are presented from Whites POV and must be mirrored for Black.
For the king, Michniewski provides two tables one for the middle game and one for the end game. He defines the end game as being either if:
Both sides have no queens or
Every side which has a queen has additionally no other pieces or one minorpiece maximum.
The evaluation of a chess board is one of the things thats kept me interested in chess engines. Evaluation rules are easy to add and take away. I refactored the code from Go to Python to be able to prototype different rules faster.
After piece-square tables, one might look at pawn structure, mobility, center control, connectivity, trapped pieces, king safety, space, tempo, and other patterns (this list is taken from the Chess Programming Wikis Evaluation page).
Minimax is a search algorithm that finds the next optimal move by minimizing the potential loss in a worst case scenario. Chess is a game of perfect information by looking at the board its possible to know exactly what an opponent is capable of. However, this search for moves is limited by the evaluation function and the depth that computing resources are able to reach.
The search space is a tree of legal moves which grows exponentially at every level (the average branching factor is around 35). By the time the tree is explored, the path to many future boards is known as well as which path restricts the opponents possible gains the most.
The leaf nodes of the tree return the evaluation of their current state. Non-leaf nodes inherit their value from a descendant node. Eventually, the recursive function reduces down to a value for the given board.
This function can be used to pick the next best move by calling it on every legal move available in the current turn. A great visual resource for this algorithm is Sebastian Lagues Algorithms Explained minimax and alpha-beta pruning.
My chess engine uses alpha-beta pruning as an improvement over the naive minimax algorithm which does not fare well against the exponential nature of chess. Branches of the search tree can be eliminated when it is clear that another branch shows more promise. This significantly reduces the number of moves required to be generated.
By reducing the depth of branches that will not bear fruit we can search deeper down the better parts of the tree.
The speed of alpha-beta pruning can be increased by applying move ordering. This is where the more promising branches of the search tree are searched first which means less time is spent in the worst branches as they will be cut off early.
Move ordering cannot be 100% accurate but its a powerful optimization.
In my engine, a cheap (but not perfect) move_value function is used to sort the initial legal move nodes from best to worst. The logic of this function is capture in its docstring:
The Universal Chess Interface (UCI) is a open protocol to hook up chess engines to user interfaces. The communication is done through standard input and standard output and messages end with n. The move format is long algebraic notation like e2e4, or e1g1 for white short castling, and an example of a promotion to queen is a7a8q.
There are many configuration commands in the specification and it initially seemed overwhelming. After debugging, I found that not many were required to get a chess engine to the Hello World stage.
In order to hook my chess engine up to lichess via lichess-bot, I implemented the following. These commands are send to the engine from lichess-bot:
I have found a great joy interacting with the chess community over the last month. Lichess is a fantastic resource and endlessly fun to play on. The UI is slick and light and the post-match analysis is revealing and simple to use. Its open source and relies on donations and sponsorships.
I took breaks from writing this article to play chess against Dad on a real board. Were missing a white rook and use a pencil sharpener as a replacement piece. He has been telling me stories about playing chess decades ago before IBMs Deep Blue emerged and beat Garry Kasparov, the reigning world champion, on its second attempt in 1997.
If you are within my social circle, you will have experienced me evangelizing chess and chess engines over the last month now that I have published this, I promise to chill out a little bit
To build healeycodes/andoma, I used the following resources (and recommend all of them).
Thanks to Jez9999 for the Alpha-Beta pruning example image.
The rest is here:
- Businesses offer help as problems remain in Texas from winter storm - Yahoo News - February 20th, 2021
- Wet Start To The Weekend - Yahoo News - February 20th, 2021
- Chess and Artificial Intelligence (2) - Chessbase News - February 17th, 2021
- What is the secret of Wesley So's success? An interview - Chessbase News - February 17th, 2021
- Five Issues Washington Should Consider In Reviewing A Lockheed-Aerojet Merger - Forbes - February 17th, 2021
- Artificial Intelligence And The End Of Work - Forbes - February 17th, 2021
- Why Ricciardo said 'yes' to McLaren the second time they asked RaceFans - RaceFans - February 17th, 2021
- Opera Euro Rapid SF: Carlsen and So reach the final - Chessbase News - February 15th, 2021
- Letters: 'Darlington Borough Council has a terrible record of looking after heritage sites, maybe they shouldn't keep Locomotion No 1' - The Northern... - February 12th, 2021
- Fat Fritz 2.0 - The new number 1 - Chessbase News - February 10th, 2021
- 25 Years Ago, Chess Changed Forever When Deep Blue Beat Garry Kasparov - Slate - February 10th, 2021
- Chess In The COVID Era | Webster Kirkwood Times | timesnewspapers.com - Webster-Kirkwood Times, Inc. - February 10th, 2021
- 10 Things We Want From The Legend Of Zelda's 35th Anniversary - TheGamer - February 7th, 2021
- Travis Kelce is the best tight end in football. Just ask any NFL player. - The Union Leader - February 7th, 2021
- 120 things you probably didn't know were created by Black inventors | Venture - Daily Hive - February 6th, 2021
- Red Sox Truck Day approaches and theres a different feeling in the air - BoSox Injection - February 4th, 2021
- The future is augmented - The Bookseller - February 4th, 2021
- How to Use a Chess Engine? Your Quick & Effective Guide - February 3rd, 2021
- Stockfish+NNUE, Strongest Chess Engine Ever, To Compete In ... - February 3rd, 2021
- Top Chess Engine Championship - Wikipedia - January 30th, 2021
- Stockfish Chess Engine Download - softpedia - January 30th, 2021
- Play Online Chess at Caissa's Web - January 30th, 2021
- Alto AMT Should it be back? - MotorOctane - MotorOctane - January 30th, 2021
- Does the rift in AI matter to marketing? - MarTech Today - January 30th, 2021
- Scientists say dropping acid can help with social anxiety and alcoholism - The Next Web - January 28th, 2021
- Meet Yash Aradhya, a Bengaluru Formula 4 racer and a recipient of the Pradhan Mantri Rashtriya Bal Puraskar - EdexLive - January 25th, 2021
- Dancing, vacuuming, learning: What's next for robots and their creators? - ASU Now - January 23rd, 2021
- Signature Theatre announces cast and dates for 'Simply Sondheim' review - DC Metro Theater Arts - January 23rd, 2021
- SwitchArcade Round-Up: 'Scott Pilgrim vs. The World', 'Shadow Gangs', and Today's Other New Releases and Sales - Touch Arcade - January 15th, 2021
- Their Uniforms Say Ohio State and Alabama. The Players Are From Everywhere. - The Wall Street Journal - January 13th, 2021
- Ziggurat Interactive Releases First Retro First Friday Pack Of 2021 - Bleeding Cool News - January 9th, 2021
- TV tonight: another day in paradise for detective Ralf Little - The Guardian - January 9th, 2021
- The Board Games Global Market is Expected to Grow at a CAGR of 13% Between 2021 to 2026 - Yahoo Finance - January 6th, 2021
- 50 Best TV Shows To Watch In 2021 - Highest Rated Television Series - OtakuKart - OtakuKart - December 29th, 2020
- Red Bull think they have secret weapon to catch Lewis Hamilton and Valtteri Bottas | F1 | Sport - TechnoCodex - December 23rd, 2020
- HBO's Industry creators and Myha'la Herrold break down season 1 finale - Entertainment Weekly - December 22nd, 2020
- Research at Microsoft 2020: Addressing the present while looking to the future - Microsoft - December 22nd, 2020
- Deals of the Week, December 11 to 18 Growth Business roundup - GrowthBusiness.co.uk - December 18th, 2020
- Turns Out Its Pretty Good: Doomscrolling - The Cut - December 18th, 2020
- A Letter to My Kids - The Good Men Project - December 15th, 2020
- Yakuza Remastered Collection On The Way For Xbox & PC - Bleeding Cool News - December 13th, 2020
- Hitman 3 Gets A New Trailer Showing Off The Features - Bleeding Cool News - December 9th, 2020
- Reflections on 40 years: thanks for the memories (we can remember) - NOLA.com - December 9th, 2020
- AMD Ryzen 7 5800X Review: The Pricing Conundrum - Tom's Hardware - December 8th, 2020
- AI has almost solved one of biologys greatest challenges how protein unfolds - ThePrint - December 8th, 2020
- Demis Hassabis interview: the kid from the comp who founded DeepMind and cracked a mighty riddle of science - The Times - December 6th, 2020
- Online Chess and Working from Home - Chessbase News - December 5th, 2020
- Full Fischer film in YouTube - Chessbase News - December 5th, 2020
- New C360 CEO Howard Wright Sees Broadcast Tech Putting Fans on the Field of Play - Sports Video Group - December 5th, 2020
- This is what would happen if a Hind took on a Cobra - We Are The Mighty - December 5th, 2020
- Hyundai Takes The Wraps Off Its E-GMP Electric Car Platform - CleanTechnica - December 3rd, 2020
- Top 9 Reasons to Rent an RV when you traveling - The Dubrovnik Times - December 3rd, 2020
- Akron flashback: Some childhood toys you never forget - Akron Beacon Journal - December 1st, 2020
- 24 Comments on GM is Paying Cadillac Dealers to Ditch the Brand... - The Truth About Cars - November 29th, 2020
- Skilling Open QF2: Day of the Comebacks - chess24 - November 27th, 2020
- Jelurida Announces Bridge Champ, an On-Chain Version of the Famous Card Game - IT News Online - November 27th, 2020
- The 37 Best Black Friday Smart Home and Kitchen Deals (2020) - WIRED - November 27th, 2020
- The Joylessness of Cooking - The New Yorker - November 27th, 2020
- The Big Bang Theory: 10 Hidden Details About Penny That Everyone Missed - Screen Rant - November 26th, 2020
- Hitman 3 Reveals A New Location With Chongqing, China - Bleeding Cool News - November 25th, 2020
- Conte and Zidane remain best of friends ahead of San Siro reunion - MSN UK - November 25th, 2020
- AMD Ryzen 5 5600X Review: The Mainstream Knockout - Tom's Hardware - November 24th, 2020
- What's Next In AI, Chips And Masks - SemiEngineering - November 20th, 2020
- NFL Week 11: Picks and preview - Yardbarker - November 20th, 2020
- 2020 NBA Draft: Sam Vecenie's likes and dislikes - The Athletic - November 20th, 2020
- We have free android games and apps Birmingham Alive - Birmingham Alive - November 18th, 2020
- Remembering When the Memories Are No Longer Our Own - War on the Rocks - November 12th, 2020
- How To Learn Chess By Yourself: Best Apps And More - Goosed.ie - November 10th, 2020
- So Beats Abdusattorov In Speed Chess Match - Chess.com - November 10th, 2020
- Truss the process: How the Ravens turned a strange week into their biggest win of the season - Baltimore Sun - November 10th, 2020
- 2020 European MotoGP Results and News - Cycle News - November 10th, 2020
- Star Renegades Will Be Coming To Consoles Later This Month - Bleeding Cool News - November 10th, 2020
- Why a great teacher can make all the difference - Blogdottv - November 10th, 2020
- How Disney Helped Fans Live Their Star Wars Stories - Theme Park Insider - November 8th, 2020
- Artificial intelligence, the reality behind the runaway - Pledge Times - November 8th, 2020
- 8 Comments on Bugatti Bolide's Claimed Nurburing Time Isn't Real... - The Truth About Cars - October 30th, 2020
- What happened at the Badger Fire? - Times-News - October 30th, 2020
- Red Bull hopes 'Balance of Performance' plan will win rivals over to engine freeze - RaceFans - October 28th, 2020
- Rybka - Wikipedia - October 28th, 2020
- What the hell is reinforcement learning and how does it work? - The Next Web - October 28th, 2020