What programming paradigm do you think would work best for the AI aspect of a chess engine?

Question

I wish to write a chess AI which simulates the way I think over the board, using C++. My focus is on writing the algorithms for choosing moves (decision making), not defining the board and pieces. To my knowledge, most chess programs written to date are focused on taking advantage of the computer's calculating powers (aka brute force method). My program will be different in that the focus is going to be on emulating human thinking (in this case my own way of thinking which is actually highly organized).

I am relatively new to programming. Any advice you could give me on what topics to read, what programming paradigm(s) to use, any potential pitfalls I need to be aware of beforehand, or anything else you think I should know would be useful to me.

My gut feeling is that the coding will, for the most part, not benefit from OOP paradigm . Concepts such as positional evaluation, pattern recognition, weighing out pros and cons of various moves, knowing when to stop the search(pruning), defining goals and finding means to reach them, don't naturally resemble objects...or do they? My guess is that procedural programming (simply providing the computer with a set of instructions, an algorithm for picking moves), or perhaps functional programming (FP) would be more relevant in this case? Let me know what you think, thank you.

I should add that I am looking to make the program as strong as possible, another reason why I suspect OOP may not be the best approach.

Another question that concerns me: Considering how the focus of the program is to replicate human thought process, will I have to start from scratch, or is it worth taking another program as basis?

Answer 1

I wish to write a chess AI which simulates the way I think over the board, using C++.

Awesome!

My focus is on writing the algorithms for choosing moves (decision making), not defining the board and pieces.

Er, huh?

To my knowledge, most chess programs written to date are focused on taking advantage of the computer's calculating powers

Well yes, though some are also focused on cutesy animations.

(aka brute force method).

Erm no, brute force would mean the computer would force you to sit down and play every possible game with it until the sun consumed the earth.

My program will be different in that the focus is going to be on emulating human thinking (in this case my own way of thinking which is actually highly organized).

Every piece of software written by humans ends up emulating human thinking. It's the hardware that can't keep up.

I am relatively new to programming. Any advice you could give me on what topics to read, what programming paradigm(s) to use, any potential pitfalls I need to be aware of beforehand, or anything else you think I should know would be useful to me.

Read everything. Learn everything. Most of the pitfalls come from your own blind spots. I'm relatively old to programming (read as decades) and I'm still buying books to read.

My gut feeling is that the coding will, for the most part, not benefit from OOP paradigm. Concepts such as positional evaluation, pattern recognition, weighing out pros and cons of various moves, knowing when to stop the search(pruning), defining goals and finding means to reach them, don't naturally resemble objects...or do they?

Objects model more than real world things. They are ideas. Some objects are collections of strings. What real world thing does a hashset model? I know some still teach this way but an object can model more than things you can see and touch.

My guess is that procedural programming (simply providing the computer with a set of instructions, an algorithm for picking moves), or perhaps functional programming (FP) would be more relevant in this case? Let me know what you think, thank you.

Procedural programming is straightforward. Start at the beginning, proceed through the middle, when you get to the end, stop. A nice simple pattern. Unfortunately it's far easier to write than to read and even harder to change. But if you're writing something small it's a big bang for the buck.

Functional programming is about many things but mostly it's about being formal about assignments. It's not big on side effects either but mostly it hates it when you use = carelessly.

I won a chess tournament using functional OOP (yes both together) against an entire class. We were free to use any paradigm we liked. Some of the smarter students went for ultra optimized using bit boards and opening books. I didn't use any of that.

My program won but not mostly because of my paradigm. I won because I tested the hell out of it. Most of my opponents lost making illegal moves. Others couldn't help going over time. The one other program that even stood a chance against mine had made the same fateful choice I made. I was conservative with my depth.

We had 4 agonizingly long seconds to make a move. Most couldn't fully explore beyond 4 moves. Those that could couldn't do it reliably and would make silly moves because they just stopped looking when time was up.

I pruned my depth search back to where there was no possible board position that would make me stop mid search. People laughed when they saw how fast my AI made moves. They stopped laughing when I started winning.

Why was this so important? Well it wasn't because the 3.5 seconds I didn't use couldn't have been useful. It could have. But it would have gotten in the way of the best thing I did. I tested. A LOT.

Despite the fact that we only submitted dll's, I wrote my own GUI that looped through showing me every possible move for any piece in any position. Even positions off the board. I learned to allow for that in testing the hard way. My one loss was when a pawn I was about to promote to queen got confused on the 7th rank and thought it could move two steps. I lost when it moved right off the board. Didn't see that in testing. Needed a better GUI.

So when you say you want to focus on the human mind I'm with you. I just want to advise you this: Test. Because the computer doesn't care what you think. It just does what you tell it to.

I could tell you more but I'll just link you to my previous chess rantings:

Immutability & chess

Answer 2

To my knowledge, most chess programs written to date are focused on taking advantage of the computer's calculating powers (aka brute force method). My program will be different in that the focus is going to be on emulating human thinking (in this case my own way of thinking which is actually highly organized).

There are quite a lot of possible chess games (10^120 - the universe has only around 10^80 atoms) so it is quite unpractical to try all solutions (this is what backtracking means).

Instead, most of the solutions are inspired human thinking. A quite common algorithm is known as Minimax. I am just a casual chess player, but for many games, it seems like humans consider multiple possible moves and try to forecast in their minds what would be the reaction of the opponent on such move (basically continuing the game for a few moves in their head). Minimax does the same thing: analyses the possible moves, picks one such that the best move of the opponent creates the smallest advantage for him. The only difference is that while humans are quite limited in the number of moves they can consider (arguably, they are more clever in picking which ones to consider), the computers can analyse almost every move and consider what the adversary can do.

For chess, this is still quite complicated and there are ways (such as alpha beta pruning) to skip some moves.

Deep blue beat Kasparov, considered at the time to be the best chess player. There are plenty of resources over the web on how it works, but a Minimax algorithm is at the core, along with a lot of clever optimizations and leverage of computational power.

As for which paradigm to choose, this is more a choice of how to get to the destination rather than picking the actual destination. Algorithms are (usually) paradigm agnostic. Different paradigms exist because programmers can leverage them in order to be able to develop and maintain easier the software. All paradigms have, by the Church-Turing thesis, the same computational capabilities.

Answer 3

Paradigms are made for people, not for problems - problems don't care (and computers care even less). Compilation and execution strips your program of objects, functions, variables, modules, classes etc. - leaving only electrons moving on a slice of silicon.

If you say things like "knowing when to stop search" and "defining goals" - and if you don't have much experience with programming, pick a traditional, boring OO / imperative / multipurpose language: Python or Java (depending whether you like code completion or not).

With an idea like yours - it is almost certain that in the next couple of years you will fail many times and probably rewrite in another language anyway.

Answer 4

Consider Reinforcement Learning Techniques, such as TD(lambda) or Monte Carlo to find an optimal move (action) based on the current board setup (state).

RL is a branch of machine learning, attempting to imitate human thinking, using punishments/rewards of previous decisions as a driver for making future decisions. Where an agent would keep track of what is called value functions, to predict the expected punishment/reward of a certain state, given a certain action.

I wouldn't start with C++ in this case, because of the need for lots of linear algebra and multi-variate calculus

Try prototyping a solution in python, R, Matlab or Octave, then port it to C++ aided by some linear algebra libraries such as Eigen3 to implement the mathematics of any of the identified algorithms

Answer 5

To simplify chess AI into its basic form, you evaluate all the possible moves you have in this turn to determine if that particular move leaves you in better or worse shape. You then take the move that is best.

The trick is in quantifying the "goodness" or "badness" of the move. IBM's site on Deep Blue provides some insight into their evaluation function: https://www.research.ibm.com/deepblue/meet/html/d.3.2.html

(FYI -- I am getting an SSL warning right now when visiting that site)

According to that site, they quantifiy the moves based on material, position, King safety and tempo.

Next it turns into a task of applying this evaluation over and over. Say you have 10 moves possible, for each of those moves you evaluate how that leaves you and then evaluate all the moves your opponent will have once you make that move. You are looking for the move that you can make that will leave you in the best position whilst leaving the opponent in the worst.

Next it turns into doing that not just for the next move, but for the move after that, and after that, for as deep as your compute resources can go within the amount of time you are allowed.

I don't think there is any programming paradigm that suits this any better or worse than any other. You obviously need efficiency, and whether c++ provides that any better than any other modern programming language is more of a religious debate.

Back to the AI methodology, chess is typically divided into opening, middle, and endgame. I personally think the chess AI should know wherein the game lifecycle it is and the logic should differ. People have studied chess opening for centuries so in the opening game just use the openings. Likewise with the end game.

It would be interesting to take a modern approach and try to build a distributed system that collaborates churning on the analysis.

It should be noted that this is really not true AI, and is just a decision-making algorithm. True AI would be the program running with the evaluation algorithm as a starting point, and as it plays game after game it is able to tweak its own algorithm. If the computer loses when its own algorithm showed its move choices should have been superior, then analyzing where it went wrong and modifying itself.

https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/