Chess

러시아 AI 연구자인 Alexander Kronrod 가 말하기를 "chess 는 AI 의 초파리이다" 라고 하였다. 유전학자가 초파리로 다양한 실험을 하듯이 AI 연구자는 chess를 연구 대상으로 한다는 의미다.  chess 프로그램은 현재 상급 선수수준이지만 인간과 비교했을 때는 제한된 지능 메카니즘만을 가진다. 왜냐하면 이해를 해야할 것을 많은양의 계산으로 대신하기 때문이다. 세계 챔피언을 깨기 위해서는 초당 2억개의 position을 파악할 수 있는 능력과 믿을 만한 heuristic 을 필요로 한다. 일단 이러한 메카니즘을 더 잘 이해하면 우리는 현재의 프로그램이 하는 것보다 훨씬 더 적은 계산을 하고서도 인간수준의 프로그램을 만들 수 있을 것이다.... ( John McCarthy : Making computer chess scientific)

만일 체스에서 말의 가능한 움직임을 전체 tree 구조로 개발한다면 말 위치의 전체수는 10¹²⁰  이 된다. 그것은 대단히 큰 숫자로서 예를들면 우주를 탄생시킨 빅뱅이후에 단지 10²⁶ nanosecond 만이 흘렀다는 것에서도 알 수 있다. 전체 우주에는 단지 10⁷⁵ 개의 원자만이 있다는 것이다. 즉 은하계는 수십억개의 태양계로 구성되고 또한 수십억개의 은하계가 모이는 그 우주의 전체의 원자의 수이다. 그러한 숫자는 체스의 말의 움직임의 수에 비하면 아무것도 아니다. 체스는 얼마나 난해한 게임인가. 어떤 컴퓨터도 전체 tree를 계산할 수는 없다. 체스컴퓨터가 시도하려는 것은 5 또는 10 또는 20 수의 말의 위치를 미리 내다보는 tree를 생성하려는 것이다...... (컴퓨터 체스 작동 원리 : Marshall Brain : HowStuffWorks)

term :

Deep Blue   게임 (Game)   계산 (Computation)   계산가능성 이론 (Computability Theory)   계획 (Planning)   문제해결 (Problem Solving)   바둑 (baduk)   상태공간 (State Space)   인공지능 (Artificial Intelligence)   적대 탐색 (Adversarial Search)   청크 (Chunk)   체스 (chess)   추론 (Reasoning)   컴퓨터 (Computer)   탐색 (Search)   트리 (Tree)   학습 (Learning)   휴리스틱 (Heuristic)   Alan Turing

site :

AI Topics : Chess : AAAI.  미국 AI 학회

Wikipedia : Chess   Computer Chess

International Computer Game Association : 이전의 체스 협회

Computer Chess Programming : Paul Verhelst : publication   research group and people

chess link   chess base   Yahoo : Chess : 체스의 일반적 지식

paper :

두뇌와 기계 : Donald G. Fink

T. Anthony Marsland : publications

• Computers, Chess, and Cognition. Springer-Verlag, Berlin. 1990
• Computer chess and search, in Encyclopedia of Artificial Intelligence, S. Shapiro (editor), J. Wiley & Sons, 2nd edition, 1992, 224-241.

Heuristic Search 의 역사 : [Monty Newborn 1996 Computer Chess Comes of Age] 은 컴퓨터 체스에 관한 책으로서, 1996년에 DEEP BLUE 가 Garry Kasparov 에게 패할 때까지의 역사를 열거한 것이다. 이 책에 대한 서평과 AI 를 위한 연구용으로서의 체스의 역할에 대한 설명은 [John McCarthy 1997 AI as Sport] 을 참조하라. McCarthy 는 체스 프로그램이 좀더 인간과 비슷한 추론 방법을 사용한다면 더 적은 탐색으로도 더 나은 성능을 보일 것이라고 하였다. [Donald Michie 1966 Game Playing and Game Learning Automata] 는 기대값 최대화 (expectimax) 라는 말을 만들고 이 기법에 대한 실험을 수행하였다......

[신간 안내: '더 터크 (Turk)'] 컴퓨터, 터번 두르고 체스 두다 : 중앙일보 : The Turk : The University of Alberta GAMES Group : The Turk : 체스 프로그램 실행 :

history :

• 1769, Baron Wolfgang de Kempelen builds the Automaton Chess-Player, in what becomes one of the greatest hoaxes of its period.
• 1868, Charles Hooper presented the Ajeeb automaton—which had a human chess player inside.
• 1912, Leonardo Torres y Quevedo builds a machine that could play King and Rook versus King endgames.
• 1948, Norbert Wiener's book Cybernetics describes how a chess program could be developed using a depth-limited minimax search with an evaluation function.
• 1950, John von Neumann develops a chess program (on a bishopless 6x6 board) on the MANIAC I.
• 1951, Alan Turing develops on paper the first program capable of playing a full game of chess.
• 1952, Dietrich Prinz develops a program that solves chess problems.
• 1956, invention of alpha-beta search algorithm by John McCarthy
• 1958, NSS becomes the first chess program to use alpha-beta searching.
• 1958, first programs that could play a full game of chess were developed, one by Alex Bernstein and one by Russian programmers using a BESM.
• 1967, first computer chess match between the Kotok-McCarthy program and the ITEP program developed at Moscow Institute for Theoretical and Experimental Physics
• 1970, first year of the ACM North American Computer Chess Championships
• 1974, first World Computer Chess Championship
• 1977, establishment of the International Computer Chess Association
• 1980, Chess 4.6 developed at Northwesten University running on a Control Data computer becomes the first chess computer to be a successful at a major chess tournament.
• 1980, establishment of the Fredkin Prize.
• 1982, Ken Thompson's hardware chess player Belle earns a US master title.
• 1988, HiTech developed by Hans Berliner and Carl Ebeling wins a match against grandmaster Arnold Denker 3.5 - 0.5.
• 1988, Deep Thought shares first place with Tony Miles in the Software Toolworks Championship, ahead of a former world champion Mikhail Tal and several grandmasters including Samuel Reshevsky, Walter Browne, Gruenfeld and Gurevich. It also defeats grandmaster Bent Larsen, making it the first computer to beat a GM in a tournament. Its rating for performance in this tournament of 2745 (USCF scale) was the highest obtained by a computer player.
• 1989, Deep Thought loses two exhibition games to Garry Kasparov, the reigning world champion.
• 1992, first time a micro, the Chessmachine Gideon 3.1 by Ed Schroeder, wins the 7th World Computer Chess Championship in front of mainframes and special hardware.
• 1997, Deep Blue wins a six-game match against Garry Kasparov +2-1=3 (see [1] (http://chess.ibm.com)).
• 2002, Vladimir Kramnik draws an eight-game match against Deep Fritz.
• 2003, Kasparov draws a six-game match against Deep Junior.
• 2004, a team of computers (Hydra, Deep Junior and Fritz), win 8.5-3.5 against a rather strong human team formed by Topalov, Ponomariov and Karjakin, which have an average ELO rating of 2681. ........ (Wikipedia : Computer Chess)