Deep Blue Programming

@thebigk • Oct 25, 2024

Oct 25, 2024

1.4K

Okay, for the uninitiated, "Deep Blue" is the name of the computer that was built to beat the human in the brainy game of 'Chess'!

I've always been thinking, how did they write the software to calculate the moves of Deep Blue?

Anyone's got any idea? If you were to write such a software, what would be your approach?

Like 0 Replies 12

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

CrazyEngineers powered by Jatra Community Platform

Kaustubh Katdare

@thebigk • Oct 8, 2008

H-e-l-l-o !

Why do threads like these get no response for a long time? Is everyone sleeping?
0
silverscorpion

@silverscorpion-iJKtdQ • Oct 8, 2008

ok, I'm not very good in programming. But what i read about deep blue is this.
It has a basic chess engine and a very fast processor. It has millions of chess
positions in it's memory and compares the current position with it's database.
It decides which move is the best for current position and makes its move.
The speed with which it searches is really huge - about 200 million chess
positions per second.

so, finally, deep blue is not really intelligent or an efficient chess player. It's
really a super fast search engine with algoroithm for determining the best
chess move for any given position.
0
Kaustubh Katdare

@thebigk • Oct 8, 2008

silverscorpion
It decides which move is the best for current position and makes its move.
You see, that's the part I want our CEans to discuss. How does it decide the best move?
0
silverscorpion

@silverscorpion-iJKtdQ • Oct 8, 2008

hi,
May be, it compares the current position with previous games that are stored in the memory. Say, in a previous game, in a position similar to this, the move made was x. then the computer tries x here too. it's a matter of training and prediction i guess.. wat do u say?
0
silverscorpion

@silverscorpion-iJKtdQ • Oct 8, 2008

hi
sorry i was wrong in the last post. It was pure brute force, as i suggested before.

Read this : <a href="https://en.wikipedia.org/wiki/IBM_Deep_Blue" target="_blank" rel="nofollow noopener noreferrer">Ibm Deep Blue</a>

I cant imagine how they packed so much power into a computer, that it defeated a grand master. I was always of the opinion that machines can never overrun humans. I'm not sure now...

0
Kaustubh Katdare

@thebigk • Oct 8, 2008

Yes, I've been guessing the same. Feeding all possible moves is just impossible. Anyone knows how this brute force works in Deep Blue?
0
Ashraf HZ

@Ash • Oct 8, 2008

The_Big_K
H-e-l-l-o !

Why do threads like these get no response for a long time? Is everyone sleeping?
Biggie, you're just so eager for a response! Its only been six hours since you first posted it 😛

No idea how Deep Blue works in detail, but if I were to do a basic chess AI, I'd use some kind of tree algorithm with a database stored with LOTS of possible moves, but to a limit.

I'd also implement Fuzzy logic to react with the opponent's moves *grin*
0
Kaustubh Katdare

@thebigk • Oct 8, 2008

How about getting the people who programed Deep Blue for Small Talk? 😁 ! Can anyone help us with contacts?
0
sriramchandrk

@sriramchandrk-wt4rlR • Oct 13, 2008

Hi,

I dont know anyone who were involved in deep blue.

But i have an idea about how it might be working.

You have heard of Game-Tree(a sort of decision tree)
For each possible move what all next possibles and from that point again what all etc.,

For simple problems the game tree is usually small.
but when you think of game like chess where billions or possibilities are there, you cant draw the complete game tree which takes you to win position, istead you have to stop drawing game tree at a certain positions based on your resources.

On a simple machine for example you can think of a gametree of height of 1000 and you need to stop at this level and make the best move or else you will run out of resources.

But on a better architecture (may be super computer) where in the calculation of game tree is distributed, has more space, power etc., you will get good moves as compared to regular home computers.

Even a powerful supercomputer cannot draw a complete gametree. The process of calculating the tree goes on as moves happen.

Hope this will give an idea about how it works.

Thanks & Regards
Sriram
0
simplycoder

@simplycoder-NsBEdD • Sep 7, 2011

I like this thread a lot, one it shares with chess,two its programing.
Few months back I programmed a decent chess AI. Trust me its complicated.
Assume number of legal moves on average in a game is 35

In terms of Game trees, there is something called as branching factor, in chess this is approx 35(legal moves).
so at parent node there are 35 possibilites.

There would 35 child-nodes per parents thus yeilding to 1225 nodes.
At level three its 42875.
At level 4 its 1500625.
At level 5 its 52521875
At level 6 its 1838265625
Assuming this, this will cause an explosion.

To play decent chess, engine must think 6 plies ahead.
So we shall add up all the nodes to check for the particular position at 6th ply or 6th level
So total number of nodes at this level is 1892332260

This is just a huge numbers and the computer is thinking just 3 moves ahead(seriously to rate this, I would say that its not even an average chess player)
There is time required for move generation and evaluation as well so see this its going to take long time.

Deep blue defeated Garry Kasparov(GOD of chess), Being a consistent chess player for over 8 years, by studying his games, I can say that Garry Kasparov thinks
about 10 to 12 moves ahead in critical position.

I have no guts to write the number of nodes now(35[SUP][SUB]24[/SUB][/SUP]). No processor can beat this huge number.
brute force is O(n[SUP]b[/SUP]). This is where brute force solution fails.
So programer thought about bruteforce and later on added some thing to it called as alpha-beta pruning(refer google).
This has running time of O(n[SUP]b/2[/SUP])
This is just fantastic now search space is decreased to (branch factor)/2 in the best case and branch factor in worst case, so we can assume that the average case will prune some nodes and search. This increases the speed and hence the depth.
There are many algorithms that are implemented in deep-blue I just cannot cover each and every one of them. However if I get time, I shall write a tutorial on this for sure, we would learn board game programing for tic-tac-toe AI.

Thus we donot need to store all positions for chess and we cannot store all positions for chess if we want to make it a decent player.
Go is even more horrible than chess.
0
vinci

@vinci-e4PtMU • Sep 12, 2011

Hello friends !!!
I read above posts and i found this topic really fantastic as well as interesting !!! Deep blue is an IBM super computer(Chess computer) that won game against world champion in 1997.but remember this machine was built by humans so who is more powerful???
0
vinci

@vinci-e4PtMU • Sep 12, 2011

really nice post .You seems to be a programmer,and very well know data structures.Good .keep write something in AI
0