How do chess engines work? An intro to AI.

academics artificial intelligence chess computer science
By Amnon

Before we consider how computers play chess, let’s talk about how humans do it. 

How humans play chess

The classic image most of us have of chess grandmasters is that they are calculating deep sequences of possibilities; “if I do this, and they do that, and then I play here, …”. In reality this image is not entirely precise.

by Bill Amend

There is no doubt that good players can calculate many moves in advance, but they can do so only because they have an incredible intuitive understanding of positions. Great players can take one look at a board and accurately determine who is winning and why, where often the first move that comes to mind is the best one. 

This observation about human intelligence (with respect to chess) will guide how we think of Artificial Intelligence (AI) in general. You’ve probably heard before that “the number of chess positions is larger than the number of atoms in the universe”. We cannot hope to consider so many possibilities, and therefore to create a chess playing computer we will provide it with “intuition” that can reduce the set of positions it considers in the first place.

Intuition in decision making

There are many ways we can define intuition, but for our purposes it is a quick estimate of the value of a state. In AI, we call this concept a heuristic

You use heuristics every day. Rounding provides an estimate which makes future arithmetic easier at a small cost to accuracy. When deciding what computer to buy you don’t consider all possible choices, but rather simplify the decision by picking some key attributes you care about, such as battery life. When we decide on accepting candidates for a job we use quick judgements based on limited information that hopefully captures their quality.

Let’s now return to chess. Pretend that every time you see a position a little voice in your head screams “Terrible”, “Bad”, “Ok”, “Good”, or “Amazing”, which for convenience we can refer to as (-2, -1, 0, 1, 2). One should clearly always trust the voices in their head, so how would you use it to play chess better? 

One option would be to branch and bound. Consider every move from the current position, and only keep the ones which lead to positions the voice is most positive about. Do this again for every possible move from those next positions. Keep doing this as many times as your memory can handle, and then choose the first move as the one which leads to the most positive final position.

Screen Shot 2023-01-30 at 11.18.21 AM

Each step we branch from the current set of positions, then bound (or prune) the heuristic values and only keep the higher ones. This procedure allows us to calculate what move to play by only considering a smaller set of possible sequences. 

It’s important to keep in mind that heuristics can be wrong, for example the yellow state in the image is at first evaluated as “1” even though later we see it leads to a better state which is evaluated as “2”. If we had pruned away states valued at “1” we would never have found this sequence.

Encoding heuristics for chess

Now that we know how to use a heuristic to make decisions, let’s describe some heuristics for chess.

Screen Shot 2023-01-30 at 11.11.46 AM

Who is winning in the position to the right, white or black? Even if you don’t know much about chess you can likely guess that white is winning because they have so many more pieces. It may seem stupid but it’s the first and most powerful heuristic in chess - whoever has more and stronger pieces is probably (but not always!) winning.

Most chess coaches start teaching with the same set of mantras: “control the center”, “develop your pieces”, “castle early”, “a knight in the corner is a mourner”, and so on. These are just heuristics! None of them are necessarily always true, but if you follow these basic rules your first games will go significantly better.

With a large set of heuristics you can add or average their separate “opinions” about a position to get a better estimate for whether it’s worth considering.

Generalizing beyond chess

That’s it! The best chess engines in the world are, at their core, nothing more than a large set of handwritten heuristics combined with a “branch and bound” like algorithm for making decisions. While humans are still significantly better at evaluating individual positions than these computers, the engine makes up for it by calculating and remembering much deeper sequences of moves than humans.

The ideas we considered here are not just applicable to chess, but to all of AI. Artificial Intelligence is the study of large or complicated search problems, in which we cannot hope to search through all possibilities and instead must use tricks and heuristics to narrow the scope. 

Incorporating machine learning

Machine Learning (ML) is not Artificial Intelligence. In AI we solve search problems. In ML we try to approximate a function from examples of inputs and outputs to that function. Linear regression (finding the line of best fit) is the simplest example of such a thing.

Screen Shot 2023-01-30 at 11.13.02 AM

We can think of a heuristic as just a function, whose input is the current position and whose output is a numerical evaluation of its goodness. Truly modern chess engines no longer use a large set of handwritten heuristics, but rather an ML model (in the form of a Neural Network) which learns good heuristics using billions of games as examples. We’ll leave the discussion for how this is done for another day, but the key to remember is that the underlying algorithm is exactly the same!

 

Amnon is a PhD in Computational Robotics and Reinforcement Learning at The University of Illinois at Urbana-Champaign. He has been recognized as an Outstanding Teaching Assistant by his university for teaching Artificial Intelligence and Machine Perception.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions strategy writing LSAT GMAT GRE physics chemistry math biology graduate admissions academic advice ACT interview prep law school admissions test anxiety language learning premed MBA admissions career advice personal statements homework help AP exams creative writing MD study schedules test prep computer science Common Application summer activities history mathematics philosophy organic chemistry secondary applications economics supplements research 1L PSAT admissions coaching grammar law psychology statistics & probability legal studies ESL CARS SSAT covid-19 dental admissions logic games reading comprehension engineering USMLE calculus PhD admissions Spanish mentorship parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity chinese letters of recommendation Anki DO Social Advocacy admissions advice algebra art history artificial intelligence astrophysics business cell biology classics diversity statement gap year genetics geometry kinematics linear algebra mechanical engineering mental health presentations quantitative reasoning study abroad technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills careers cold emails data science dental school finance first generation student functions graphing information sessions international students internships logic networking poetry resume revising science social sciences software engineering tech industry trigonometry writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system neurology neuroscience object-oriented programming office hours operating systems

Related Content