3

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?

2
  • 2
    Good luck. Tell us when you got some results.
    – gnasher729
    Jun 11, 2017 at 5:48
  • All of the answers below do far more justice than what i can do, but this is a great question!
    – Rhys Johns
    Aug 21, 2017 at 22:50

5 Answers 5

15

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

13
  • Congrats on your tournament victory! Let me explain myself a bit: My focus is on the AI part of a chess engine, not the GUI and board design. I will borrow that part from others' codes. Also what I meant was that most chess programs don't think about a chess position in the same manner as humans do. For the most part, they rely heavily on the computer's processing powers to calculate variations, while human chess players (the strong ones at least) focus more on positional/strategical aspects of the game, calculating only when necessary. Jun 11, 2017 at 3:02
  • "Every piece of software written by humans ends up emulating human thinking." Does your chess program think about chess in a similar manner to you? Does it, for the most part, come up with the same moves as you and evaluate positions similarly? Do you even know how you think over the board? For the most part it is a subconscious effort. It took me years to figure out how exactly I was thinking over the board. After all, we're trying to simulate the thought process of the human brain here. Jun 11, 2017 at 3:23
  • "My focus is on writing the algorithms for choosing moves (decision making), not defining the board and pieces." what I meant was that I'm not concerned about creating a program that can produce legal moves. I will just copy-paste that from some other code. Jun 11, 2017 at 3:30
  • 2
    Well then have you ever heard of minimax? It's everything you just described. You've making a big thing out of separating concerns like it's a new idea but believe it or not I've heard this one before. Jun 11, 2017 at 4:07
  • Excellent !!! You made my day :-)
    – Christophe
    Jun 11, 2017 at 9:26
5

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.

3
  • "Instead, most of the solutions actually mimic human thinking" I don't know why you would say that. IMO, the complexities of the human thought process extend far beyond minimax and pruning, and have yet to be captured in the form of a chess program. Jun 11, 2017 at 3:41
  • Deep blue used a variant of the alpha beta pruning (minmax with heuristics) designed to take advantage of parallelization (the classical alphabeta is iterative, and parallelization bears the risk of wasting computation on less promising moves that would never be considered if the sequential approach)
    – Christophe
    Jun 11, 2017 at 9:37
  • @Seeking_Truth I wanted to suggest that minimax is inspired from how humans make decisions. You're right I was too ambitious with that statement.
    – Paul92
    Jun 11, 2017 at 10:38
1

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.

3
  • what is the jargon for "defining goals"? Jun 11, 2017 at 3:12
  • I meant defining CHESS goals, like "let's get this rook to the 7th rank". Jun 11, 2017 at 3:19
  • @Seeking_Truth I just meant the phrasing: you described your aims in terms of "actions": "define", "know", "stop".
    – fdreger
    Jun 11, 2017 at 8:22
0

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

0

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/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.