Deep Blue Programming

Replies

• 

  Kaustubh Katdare

  H-e-l-l-o !
  
  Why do threads like these get no response for a long time? Is everyone sleeping?
• 

  silverscorpion

  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.
• 

  Kaustubh Katdare

  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?
• 

  silverscorpion

  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?
• 

  silverscorpion

  hi
  sorry i was wrong in the last post. It was pure brute force, as i suggested before.
  
  Read this : Ibm Deep Blue
  
  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...
• 

  Kaustubh Katdare

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

  Ashraf HZ

  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*
• 

  Kaustubh Katdare

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

  sriramchandrk

  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
• 

  simplycoder

  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.
• 

  vinci

  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???
• 

  vinci

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