CHESS
DEEP BLUE
The most powerful chess program ever built uses the combined power of six micro processors. Ultimately Gary Kasparov defeated Deep Blue in their last face to chip match. It's original name was Deep Thought, but today this amazing program is called Deep Blue. Deep Blue was created in 1989 and since its first public appearance it has changed the way we think about computers. It took many scientists, engineers and programmers eight years to build a computer that could beat a grand master which is the highest and most respected level of chess. Along with its micro processors, Deep Thought includes 250 chips to its arsenal. It was able to calculate 750,000 moves per second or ten and a half moves ahead of its previous position. Deep Blue was able to out think Deep Thought one thousand times. Deep Blue can calculate two million moves per second or fifty to one hundred billion moves in three minutes. Within the time span of one year Deep Blue advanced from rank 2450 to being able to beat a grandmaster in a tournament. Deep Blue's ranking was within the top one hundred. The name Deep Thought was created because it takes incredible concentration to even think of three moves ahead for the average person. In a tough match, it is common to find oneself in a zone when nothing can break concentration. In August of 1993 Deep Blue defeated the worlds youngest and best female chess player. Deep Blue was developed in C and runs under AIX operating system. Deep Blue was also given a database which stored many chess games over the last 100 years and another database that has every possible move for a checkmate with only five pieces remaining. It is predicted that in the next half century, Deep Blue will become unbeatable at the game of chess.
The Evolution Of Chess
Chess began in India in the seventh century, and there is evidence that there was a similar kind of chess that started in Asia around the first century. From India, the game quickly moved to Persia, Arabia, and then Europe. Within a century, chess was being played throughout the eastern hemisphere. It wasn't until the nineteenth century that chess clubs started and tournaments were organized. At this time, the rank of professional was awarded to the best chess players.
Out of all the pieces the knight is the only piece that has not changed since chess was invented and it is the only piece that can jump over other pieces.
The king is the most important piece on the board because, once it is taken, the game is over.
When the queen was first created it was considered the worst piece because it could only move four spaces and was known as the adviser to the king. Later in Europe the king often had a consort, so the piece named queen was given the ability to move as many spaces and in whatever direction as desired, and thus became the most powerful piece on the board.
The rook also known as castle in the past was the supreme piece, and the player had to be warned by the opponent every time it was in danger. Although the movement of the rook has not changed, its name has changed may times. Its original name was Ratha (Sanskrit for Chariot), then Europe started calling the piece Rukh, finally the Italians called the rook Rocco (Rook in english). The rook is one of the strongest pieces because it can move horizontally or vertically across the board until it meets up with another piece.
The bishop had changed when the game expanded from country to country. At the beginning it was a weak piece because it could only move diagonally one square. It was called the Fil or Al-Fil which meant elephant. When chess moved to Europe, Europeans had never seen an elephant and people had a tough time picturing one, so it was named Alfiere which meant standard-bearer. The Germans called this piece Laufer which meant runner. In the medieval age, the church was a major part in the political scene, thus the player thought the name bishop would be most appropriate. The piece lost its ability to move one space, but gained long distance maneuverability by moving diagonally. It's limitation was that it moved on only one colour, but with two bishops it would cut through defenses like a pair of scissors.
The pawn is the weakest piece on the board. It makes a path for the more powerful pieces. The pawn's original name came from the Latin word Pedis. People saw this piece as a foot soldier. The pawn has not changed its movements. It is the only piece that can't move backwards and it takes the opponents piece by moving one square diagonally. When the amount of time given to each player was decreased to make the game more interesting to watch, the pawn gained two new abilities. First the player could choose one or two spaces for its first move. Second if it reached the other side of the board, It could be changed into a more powerful piece.
Today chess and the rules governing chess is universal. Today chess is the most popular game on earth. It can be played by individuals around the world who have nothing else in common including language.
How It Works
A chess program has many databases and methods of searching. Generally speaking, the computer decides on each move by weighing the advantages to find the appropriate move. Because chess has a set of rules, original thought is not needed. Chess is played within well defined guide lines. All of the possibilities are programmed like a tree where one branch is a move and each move creates many other possible moves or branches. The ordered categories that are programmed for a chess game are: MiniMax and NegaMax, Alpha-Beta search, Transposition Table, Iterative Deepening, Memory Enhanced Test, Killer Heuristic, History Heuristic, Null move Heuristic, and Quiescence Search. Each search flows into the other search.
MiniMax and NegaMax:
This search scans all of its pieces and notices what pieces can move and it ignores the other pieces. Next, the computer scans the board searching for every possible move for each piece. This procedure is continued five or six times to make sure it has found all the possibilities.
Alpha - Beta Search:
This search reviews the MiniMax and NegaMax and looks at each move and eliminates those that do not advance the positions of the pieces of the game. With those possibilities limited, the computer then determines whether or not each piece will be well protected if moved in that manner. It has to be certain that the square it attacks or aquires must be protected by enough reinforcements that the opponent would be at a disadvantage if it traded with the computer. If the computer cannot gain any advantage for the square, it will cancel that move.
Iterative Deepening:
Once the search above limits the movement to a few pieces, a probe looking deeper into the game can be undertaken. The computer now examines the remaining possibilities, deleting those that have minor short term advantages. This task considers the effect of linked moves and retreats the investigation until maximum search depth in the allotted time has been reached.
Memory Enhanced Test:
This method analyzes the previous move , and checks to see if the strategy worked and if it could continue progressing. If so, the computer would not have to process a lot of methods. It would follow the decision made the turn before when it initiated the strategy. It would analyze its move and the opponents response then the computer would look even further ahead to predict what will happen as the strategy unfolds. It takes the computer a long time to make a decision even if it knows what move to make. It spends its majority of the time searching one more move ahead.
Killer Heuristic:
Killer Heuristic is programmed to scan the strategy the computer is using. It looks at every move or combination of moves its opponent may use to escape from its strategy. The computer will start eliminating those possible defenses by covering the squares that the opponent would use to escape. The outcome would mean that the opponent won't have a chance of escaping the trap.
History Heuristic:
This database stores chess games that have been played in the past one hundred years by grandmasters or professionals. Deep Blue has almost every game stored in its database. Deep Blue also records all of its games, so if it did make a mistake, it won't repeat it. The advantage of this information is that if a game is close and one wrong move can determine the winner, the computer would have the advantage because it could recall similar situations. Since it can't create new strategies, it relies on its store of chess games. The advantage the opponent has is that if he/she recognizes the computer's strategy, that player could make a defensive move the computer has never encountered.
Null Move Heuristic:
If there are many pieces on the board and the computer has predicted that it could checkmate the opponent, then it will ignore all other pieces and only focus on the pieces that it needs to win the game. The Computer would give up any piece (except its king) if there was a way of winning and there was no way the computer could loose.
Quiescense:
Quiescense searches for what its opponent can do to the computer. The computer looks for what pieces are protected: can the opponent take a free piece of mine, what can he do within two to three moves and can he/she disable my defense and force me to withdraw my attack? The computer doesn't move without trying to make sense of what its opponent is trying to accomplish. This search also looks for ways around the opponents strategy so that he/she ends up out of ideas later in the game. Meanwhile the computer is building up for its attack. This search will be used first over the other searches if it sees a problem developing, because if it ignored the opponent, he/she could beat the computer to a checkmate or loose a very important piece.
Man vs. Computer
When Kasparov was challenged to play Deep Blue, Kasparov responded by saying "I vow to defend human dignity". If a computer is to become supreme at the game of chess, it would have a profound impact on society. It would mean that for one task, sheer calculations are better than innovation and improvising. People would think that computers had grown to be more intelligent then humans. Is that really true? No, because computers only follow what is programmed. Computers can only make a move if it is beneficial or if there is a strategy where the computer will come out winning. A computer is only as intelligent as the people who put it together. Scientists and engineers don't have the technology yet to get a computer to learn from its mistakes and/or come up with new ideas.
Deep Blue was programmed in such a way that it knew how Kasparov likes to play chess. Deep Blue was able to anticipate almost every move Kasparov played because people programmed Kasparov's style of play into Deep Blue. If Deep Blue had been created to play chess without knowing Kasparov's style, Deep Blue would have lost for sure. It would not have recognized the strategies that were being executed, and therefore would have taken the most logical approach. Deep Blue would not succeed playing other grandmasters because it has not been programmed to recognize their techniques.
The matches between Kasparov and Deep Blue were very stressful for Kasparov. Part of the challenge between humans is the ability to deal with stress and fatigue. Deep Blue is not subject to these weaknesses. In game six Kasparov lost to Deep Blue because he was mentally beat after spending days looking and analyzing the chess board. Kasparov missed an easy checkmate because he couldn't concentrate any more. After the reprogramming of Deep Blue, Kasparov was essentially facing a new player. Everything that was learned by Kasparov about the weaknesses of Deep Blue became obsolete. If Deep Blue was playing, the programmers should have left the programming alone until the next match. The match between Kasparov and Deep Blue was an unfair test because after each game Deep Blue was reprogrammed by its creator. Deep Blue could not adapt on its own. Because Deep Blue had to be reprogrammed after every game, it means that humans still have the upper hand over machine. For a computer to truly win, technology has to advance to a level where a machine will be able to adapt on its own. Otherwise a machine like Deep Blue is no better than a calculator
Advantages That These Games Can Bring To Society
If a computer can decide one strategy over billions of other moves, then computers should be able to operate by themselves . The computer is not able to compromise or come up with new ideas, but it is able to put a value on each possibility and choose the one method that has the best odds. In the future, computers could develop into a vehicle like the one on Mars and go to further planets without the use of a human controlling it. It should be possible to program a robot to turn left or right if it runs into a wall or finds itself stuck in a ditch, and thus be able to escape. For a computer to become truly independent, it should be able to vacuum a home without being programmed to do so.
Other Games That Uses The Same Technique As Chess
Chess is not the only game that involves strategy and planning. There are other games that involve the same technique. Checkers is a game where you and your opponent start on equal terms and in order to defeat your opponent, you must jump over all of his/her pieces. Checkers is similar to chess because both games have rules to follow and many option within the boundaries. Checkers is not as complicated as chess, but there is still a lot to consider. You still need to look ahead and predict what will happen so you can stay one step ahead of your opponent. In checkers there are not a lot of possibilities because the moves are restricted to moving only one space diagonally. The same procedures and searches to make a chess program are used when creating a program for checkers.
Abalone is another game that involves weighing possibilities and making a move according to how the pieces are positioned. In abalone you as well have an opponent and the object of the game is to knock six of his/her balls off the board. You accomplish this by pushing one of your marbles against the opponents marble. If the opponents marble is trapped at the edge you then have the opportunity to push it off. The challenge is to be able to trap the marble while not getting trapped yourself. This game uses the same procedures and approaches as chess and checkers.
All the games are broken up into three categories: no option, option, and unique decisions or independence. No option, is a game like black jack where the computer just follows the rules given and doesn't have a choice whether to hit or stand. The option category, consists of games like chess, checkers and abalone. These games are based around rules but there are still many options and decisions that the computer has to decide on. The last category involves machines that can create its own solution without any methods given to it. For example it a robot comes across a river and wants to cross it, it would build a bridge so when it crosses it won't get wet. Robots today only perform what it is told or programmed to do. If the same robot uses the technology we have to day , it would drown and terminate itself. Maybe in the future, technology will advance at a level whe