Chess World.net presents: Artifical Intelligence Paper: How do Chess Engines work?!

[AylerKuppYT]

@DotSimLtd It's not that the static evaluation functions have not been improved but there is a tradeoff between the complexity of the evaluation function (requiring more time to compute) and the depth of the search (uncovering more tricks and traps). Thus, some engine developers presumably opt for a less comprehensive evaluation function in return for a deeper search in a given amount of time, and some engine developers opt for the reverse.

[gofookalime]

im 15 and i do not understand half of this,......

[link2998]

I second 111Socrates778.

[111Socrates777]

In a nutshell how would the average player make the most out of playing chess software, that to me would also be an interesting topic.

[mcpartridgeboy]

@111Socrates777 hello socrates would not be spending his time on a computer he would not resolve to an inferior veriosn of truth to try to solve true problems ! whay are you asking such a question mr socrates ? oh by the way who did write the pebublic some peoplee say it was you but i stil think it was platoe ! thanks

[TheFoxgirly]

Very very intresting video!!! I'm a computer science student myself and in spring next year I will study artificial intelligence. Go engines are highly intresting, mainly because they are not even close to beat professional players at maximum board size (19x19). There are many reasons why. Comparing to what's said in this paper about the first four moves, Go has 16,7 billion positions to check. Then of course we have the difficulty to set a value to a stone aswell.

[mcpartridgeboy]

@TheFoxgirly no point trying to solve any game, might as well just waiit for quantom computers, theyl just do it straight off !

[noxure]

@mcpartridgeboy That's a common misconception. A quantum computer can only solve so called BQP problems. It makes mistakes, but we know exactly how often, which gives us a small (but amazing) advantage. But it still has its limitations.

Chess is a "P-space complete" problem. It has the highest complexity possible in a perfect information system. Not even a quantum computer could solve a game that has billions on billions of times more possibilities than there are atoms in the universe.

[mcpartridgeboy]

@noxure ok your right of course about the figures but surely it could work out best moves until the end, ie create an opening system for the entire game, og course varients and side lines will wobble even the most powerful computer but after a certain amount of training in sub optimal moves, seeing something like 1 billion moves (with best move branches from those to the depth of 1 billion) would surely if not solve chess make an unbeatable game !

[YtubeUserr]

The knight is valued slightly higher than a bishop in that particular program?

[mtardibu]

I feel like I'm 8 again.

[truthcrackers]

KC as you know I watch all your videos (yes, all of them) and I'm an IT guy. This video I found, like the odd ones that go off the beaten track you make from time to time, a nugget of gold. God bless you KC and your wonderful happy chess world! I await you're next installment as always - 3 min? Bullet? Commentry? Evolution of style? Music only chess videos? Dog? Or the meat and potatoes annotated games. KC, you are a pleasure on youtube and best of luck in the classic. My advice? GO!

[fmakofmako]

The reason a bigger depth is not a real solution to the horizon effect is as explained earlier in the paper, basically you can only look so deep before the number of nodes that need to be checked is too high for you to complete in a reasonable time even with pruning.

[mschonert7]

@fmakofmako Remember though that when that paper was written they couldn't fathom more processing power could be a general solution (which it has been in part). That was the beginning of the internet/computer age as we know it. Windows 95 was just coming out. What Deep Blue did with a computer the size of a room you can now do with your ipod, a desktop computer can do it thousands of times better.

[fmakofmako]

@mschonert7 I want your ipod

[PachinkoTendo]

Many thanks KC. This is very interesting.

[hurikai]

Thanks for this video, very informative!

[880330145789]

could not follow the video... a bit technical for me.

[chumbucket843]

KC, I have tinkered with programming chess engines before and with all due respect this topic is better off being taught by a programmer. You are reviewing an outdated paper entirely focused on making engines FASTER. Modern engines are significantly more advanced and their weaknesses are negligible compared to their strengths when playing humans. There are some good online articles on how chess engines work; just google search.

[mschonert7]

@chumbucket843 He was just showing a paper. A paper written by someone who seemed perfectly apt at writing on the topic. He was just showing people a paper that introduces the basics of chess engines. It's fairly obvious to most of us that he wasn't implying everything about that paper still holds true. We all know Houdini and Rybka beat every Grandmaster with minimal computer power these days. It's interesting to see what they knew in the mid 90's and it's a good start.

[AbacusRiver]

@chumbucket843 This is a fantastic introduction for 95% of the audience out there. If you think you can do better, go and do it. Otherwise, shut up.

[YtubeUserr]

@chumbucket843 I'm was an AI programmer and the info supplied in the paper is still valid buddy.

[DotSimLtd]

@chumbucket843 I too have tried my hand at chess programming. To beat a top computer requires more than merely reading a dated paper, it requires a lot more research. The minmax-esque search techniques are probably still used but I suspect static evaluation functions have come a long way, also bear in mind with multiple cores (CUDA), I too suspect that some searches (not all) can be done in parallel (eg iterative deeping). Getting the source to Rybka may be a good starting point.

[kingscrusher]

@DotSimLtd I think the advice of keeping the position closed, and trying to win on time is probably from a chess perspective the only real thing you can do against modern engines to try and win - as I recently showed in a blitz live commentary game. The paper I thought was still valid because I think that the core algorithms haven't changed much. They haven't needed to because evolution is also driven by hardware and speed advances.

[DotSimLtd]

@kingscrusher I suspect your correct in that the "core" algorithms have not changed vastly, therefore it would be surprising that the static evaluation function have not been improved, which may account for why some programs (on the same hardware) are better than others. Its interesting to compare this paper to the Claude Shannons "Programming a Computer for Playing Chess" written in 1950. The core algorithms are similar but theres some innovations in the 1997 paper you posted.

[kingscrusher]

@chumbucket843 Programmers of chess engines will I think still try and look for the core understood Algorithms. Algorithms form the basis of AI and Computer Science research. Why do you seem to downplay the importance of algorithms such as alpha-beta pruning?! If you wanted to program a sorting routine, there are already algorithms out there. If you want to program a chess engine, surely you would want to know the basic algorithms?!

[TheOneBlackSheep1973]

@chumbucket843 With all due respect who asked you ?

[xdragon2k]

12:23 ... the result of a prune is KOTOV!!!!

[YsnipezYMw2]

what was the name of the cheater, I have not watched the video and will you be playing in the London Chess Championship?

[jerseyknight]

@YsnipezYMw2  search kingscrusher planless

[kingscrusher]

@jerseyknight I have put a reply video link now above - for the game vs the potential engine abuser

[ddavyCn]

Thanks for the video, good paper for explaining chess computers.

[arjuntemurnikano]

@kingscrusher chessprogramming wiki

[ShotDownInFlames2]

Kasparov came up with the technique to confound the computer in one of those matches. Create a pawn wall and move pieces behind it. Very similar to what you did, Crusher, in that 5 minute game. And you did it in just 5 minutes, by the way.

[mgcfrg]

Interesting.

"Horizon effect

...

Although techniques exist to mitigate its effect, there is no general solution to this problem. "

[ulujm]

I remember a system which was used on certain website against cheater. the cheater need to switch from the website to the engine. when the website see several time the switch then there is something. if you play you should stay on the same page and not check something else away from the webpage. of course this will work if you play live chess and you need to stay on the webpage for not to be consider a cheater during the game. Not sure why this system is not included in most of the chesswebsite

[dnowmects]

@ulujm I often look at other sites when waiting for an opponent to move (especially if they run away and leave the clock to run out), and I'd hate to be punished for not staring at a static screen. I think kingscrusher's approach of watching move strength and time intervals would have fewer false positives.

[ulujm]

@dnowmects

yes but if you play 5 min game it 's not to hard to stay on the site. even if you go to see other webpage I think it's fine. only there is a switch between each move it's suspicious so I doubt a real player will switch between each move. for ~40 moves game you may browse let say 10 times, quite different than 40 times.

[balanceseeker]

@ulujm If I were going to cheat, I would run the engine on a separate computer sitting next to me.

[ulujm]

@balanceseeker

yes i forgot to mention that

[MightyMoe1985]

Nice work, and how is the engine abuser getting along on the ICC?

[kingscrusher]

@MightyMoe1985 He seems to have beaten recently Yardbird (Eric Lobron) and also Nick Defirmian - over 2500 now. Not bad.

[MightyMoe1985]

@kingscrusher It was a quite unnatural playing style he had... But good anti-computer strategy =)

[jerseyknight]

@kingscrusher 2539 - his losses are time related and one early blunder

[scottie55901]

That does explain why there are moves that can be played that radically shift the evaluation though it is not mentioned as an engine best move, ie: Houdini/Rybka match where one program pruned off a line and didn't see the line through... as you mentioned in one of the games you covered "after this rook move the evaluation radically shifts." Interesting

[commentableuser]

Thanks for the post mate! Also, I was wondering if you might be willing to make some sort of video to help novice players like myself with the middle game. (I've read a few chess books, and the play-by-play's.) But I've never seen a youtube commentary. As always; have a good one.

[15Arkane15]

nice work!