위키원
리처드 그린블라트
리처드 그린블라트(Richard D. Greenblatt, 1944년 12월 25일~9)는 미국의 컴퓨터 프로그래머이다. 빌 고스퍼(Ralph william Gosper Jr.)와 함께 해커 커뮤니티를 설립했다. 매사추세츠 공과대학교(Massachusetts Institute of Technology, MIT)에서 일했으며 PDP-6의 맥리스프(Maclisp)의 주요 구현자였고, 맥리스프가 있던 운영체제인 ITS(Incompatible Timesharing System)의 공동 개발자였다. 체스 프로그램 '맥핵(MacHack)'의 개발자이기도 하다.
생애
리처드 그린블라트는 1944년 12월 25일 오리건주 포틀랜드에서 태어났고, 그의 가족은 그가 어렸을 때 펜실베이니아로 이사했다. 몇 년 동안은 펜실베이니아에서 자랐지만 부모가 이혼하자 어머니와 여동생과 함께 미주리주의 컬럼비아로 이사했다.
1962년 가을, 학부생으로 두 번째 임기 즈음에 MIT에 등록했고, MIT의 유명한 테크 모델 철도 클럽(Railway Club)으로 가는 길을 찾았다. 당시 피터 샘슨(Peter Samson)은 IBM 709시리즈 기계에서 작동되는 포트란(Fortran)언어로 철도 클럽의 방대한 모델 열차 배치에 대한 복잡한 시간표를 작성하는 업무를 자동화하는 프로그램을 작성하고 있었다. 그린블라트는 PDP-1이 부족한 포트란 컴파일러를 구현해야 한다고 느꼈지만, 컴파일러를 디버깅하거나 컴퓨터에 입력할 수 있는 시간이 없어 AI 연구소로 향했다. 하지만 그는 그곳에서 PDP 기계를 프로그래밍 하는데 너무 많은 시간을 소비하여 2학년 때 MIT에서 탈락했다. 그래서 그는 6개월 뒤 AI 연구소가 그를 다시 고용할 때까지 '찰스 애덤스 어소시에이츠'라는 회사에 취직해있었다.[1]
1966년과 1977년에 MIT 리스프 머신의 메인 디자이너 톰 나이트(Tom Knight)와 함께 활동하며 맥핵을 개발했다. 1979년, 그린블라트는 러셀 노프츠커(Russell Noftsker), 톰 나이트, 잭 할로웨이(Jack Holloway)를 중심으로 MIT AI 랩(Lab) 동료들이 설립한 심볼릭스(Symbolics)와 경쟁하여 리스프 머신을 제작 및 판매하기 위해 주식회사 리스프 머신스(Lisp Machines)를 설립하였다. 하지만 1987년 파산한 이후 그린블라트는 자취를 감추었다.[2]
경력
학력
- 1962년 미국 MIT(매사추세츠 대학교) 중퇴
저서
리처드 그린블라트가 직접 지은 책은 없고, 일부 내용만 다른 책에 실렸다.
- 1967년 : AFIPS Fall Joint Computing Conference 1967, The Greenblatt chess program: 801-810 / 리처드 그린블라트, 도널드 이스트레이크, 스테판 크로커
- 1980년 : Computer Architecture for Non-Numeric Processing 1980: 137-138 / 리처드 그린블라트, 토마스 나이트, 존 할로웨이, 데이비드 문
- 1992년 : J.Int. Comput. Games Assoc. 15(4): 192-198 / 리처드 그린블라트
주요 활동
맥핵(MacHack)
2016년 3월, 바둑계에서 최고라 불리는 '이세돌'과 최고의 바둑 인공지능 '알파고'가 바둑 대결을 펼쳤다. 결과는 알파고가 4승 1패로 승리했다. 경우의 수가 10의 170제곱이나 되는 바둑의 특성상, 알파고의 함수를 짠 프로그래머가 그 모든 경우의 수를 일일이 짤 수 없기에 인간이 이길 거라고 예상한 사람들은 큰 충격에 빠졌고, 학계에서도 뜨거운 반응을 보였다. 이와 같은 결과는 바둑과 같은 매우 복잡한 분야에서도 인공지능이 활약할 수 있다는 것을 본격적으로 알리는 계기가 되었다. 이런 알파고의 조상 격이 바로 '맥핵'이다.[3]
맥핵은 1967년에 리처드 그린블라트가 만든 체스 프로그램이다. 인공지능에는 한계가 있다고 비판했던 철학자 겸 아마추어 체스 선수 후버트 드레퓌스(Hubert Dreyfus)의 도전에 응하기 위해 만들어졌다. 결과는 후버트의 패배로, 맥핵은 인간에게 승리한 인공지능의 첫 사례가 되었다. 하지만 드레퓌스가 뛰어난 선수가 아니었고, 체스 챔피언 '바비 피셔(Bobby Fischer)'에게 '3전 3패'라는 이력이 있어 맥핵이 완전히 이겼다고는 볼 수 없다는 의견이 있다.[4]
맥핵은 보스턴 지역에서 인간과의 여러 토너먼트에 참가하여 체스 대결을 했지만, 1500년대 초반의 수준이라는 낮은 평가를 받았다.
1960년대 중반, 타임 쉐어링은 초기 단계였지만, MIT는 이 분야에서 연구를 진행할 수 있는 많은 정부 보조금을 받고 있었다. 그것은 '프로젝트 MAC'이라고 불렸는데, 여기서 MAC은 '다중 액세스 컴퓨팅'을 의미한다.
또한, 맥핵은 1978년 컴퓨터 체스에서 최초의 전용 하드웨어 접근 방식 중 하나인 체스 지향 프로세싱 시스템 CHEOPS에 적응했다.
변환 테이블
MIT에서 코토크(Kotoc)/맥카시(McCarthy) 프로그램의 성공 이후, 리처드 그린블라트는 새로운 시도를 시작했다. 1966년 말 스탠포드를 방문했을 때 코토크/맥카시 프로그램과 이텝 프로그램의 경기 중 한 게임에서 나온 움직임의 목록을 보고 스스로 프로그램을 작성하도록 하는 영감을 받았고, 그 결과 그는 한 달 만에 도널드 이스트레이크와 스티븐 크로커의 도움을 받으며 워킹 프로그램을 만들었다.[5]
변환 테이블은 컴퓨터 게임 플레이 프로그램에 의해 생성된 게임 트리에서 이전에 본 위치 및 관련 평가의 캐시다. 다른 이동 순서를 통해 위치가 반복되면 해당 위치 아래의 게임 트리를 다시 검색하지 않도록 테이블에서 위칫값을 검색한다. 변환 테이블은 게임 전체 상태를 항상 모든 플레이어가 알 수 있는 완벽한 정보 게임에서 주로 유용하다. 변환 테이블의 사용은 본질적으로 트리 검색에 적용되는 메모 화로서 동적 프로그래밍의 한 형태이기 때문이다.
일반적으로 현재 보드 위치를 해시 인덱스로 인코딩하는 해시 테이블의 형태로 구현된다. 게임 트리에서 발생할 수 있는 위치의 수는 검색 깊이의 지수 함수로, 수천에서 수백만 또는 그보다 훨씬 더 클 수 있다. 따라서 변환 테이블은 사용 가능한 시스템 메모리의 대부분을 차지할 수 있으며 대개 게임 실행 프로그램의 메모리 설치 공간의 대부분을 차지한다.
게임 플레이 프로그램은 게임의 다음 몇 번의 움직임에서 발생할 수 있는 수백만 개의 위치를 분석함으로써 작동한다. 전형적으로, 이 프로그램들은 '깊이 우선 검색'과 같은 전략을 채택하고 있는데, 이것은 그들이 지금까지 분석된 모든 위치를 추적하지 못한다는 것을 의미한다. 많은 게임들은 한 가지 이상의 방법으로 주어진 위치에 도달하는 것이 가능하다. 이것을 '변환'이라고 한다. 예를 들어 체스에서 이동 순서는 1. d4 Nf6 / 2. c4 g6 (대수 체스 표기법 참조) 이렇게 두 개의 선택지가 있는데, 어느 한 선수가 이동 순서를 바꿀 수 있기 때문에 총 4개의 변환이 가능하다. 일반적으로 n이 이동한 후 가능한 변환 상한은 (n!)2이다. 이들 중 상당수는 불법 이동 시퀀스지만 결국 같은 위치를 여러 차례 분석하는 것으로 끝날 가능성이 높다.
이 문제를 피하고자 변환 테이블을 사용한다. 그러한 표는 지금까지 분석된 각각의 위치를 일정한 깊이까지 해시표로 나타낸 것이다. 새로운 직책에 직면했을 때, 프로그램은 그 직책이 이미 분석되었는지 확인하기 위해 표를 체크한다. 이것은 상각된 일정한 시간에 신속하게 처리될 수 있다. 만일 그렇다면, 표에는 이전에 이 위치에 할당한 값이 포함되어 있다. 이 값은 직접 사용된다. 그렇지 않으면 값을 계산하고 해시 테이블에 새 위치를 입력한다.
컴퓨터에 의해 검색된 위치의 수는 종종 그것이 실행되는 시스템의 메모리 제한을 크게 초과한다. 따라서 모든 위치가 저장될 수 있는 것은 아니다. 테이블이 가득 차면 사용량이 적은 위치가 제거되어 새로운 위치를 위한 공간을 만든다. 이는 배치 테이블을 일종의 캐시로 만든다.
변환 테이블 조회를 통해 절약되는 연산은 단순히 단일 위치의 평가만이 아니다. 대신에 전체 하위 트리에 대한 평가는 피한다. 따라서 게임 트리의 얕은 깊이에 있는 노드에 대한 대체 테이블 항목은 더 가치 있고(이러한 노드에 뿌리를 둔 하위 트리의 크기가 더 크기 때문에) 따라서 테이블이 채워지고 일부 항목은 폐기해야 할 때 더 중요성이 부여된다.
변환 테이블을 구현하는 해시 테이블은 변환을 찾는 것 외에 다른 용도로 쓰일 수 있다. 알파-베타 가지치기에서는 최상의 이동에 해당하는 노드의 자식을 항상 먼저 고려할 때 '검색이 가장 빠른지'를 고려한다. 물론 사전에 최선의 움직임을 알 방법은 없지만, 반복적인 심층화를 사용할 때 얕은 곳 검색에서 최고로 판명된 움직임은 좋은 근사치가 된다. 그러므로 이 조치가 먼저 시도된다. 노드의 가장 좋은 하위 항목을 저장하기 위해, 전환 테이블의 해당 노드에 해당하는 항목이 사용된다.[6]
- 교체 전략
변환 테이블은 사용 가능한 시스템 메모리에 의해 최대 크기가 제한되는 캐시로, 언제든지 오버플로우할 수 있다. 실제로 오버플로우가 예상되며, 언제든지 캐시 가능한 포지션의 수는 게임 트리의 노드 수보다 작은 일부(규모가 작은 순서도 포함)에 지나지 않을 수 있다. 대부분의 노드는 변환 노드가 아니므로, 즉 재발할 위치가 아니므로, 잠재적인 변환 노드를 유지하고 다른 노드를 대체하는 효과적인 교체 전략은 트리 크기를 현저히 감소시킬 수 있다. 대체는 대개 나무 깊이와 노화를 기반으로 한다. 나무에서 더 높은 노드(뿌리에 더 가까운 노드)가 선호된다. 그 아래 하위 트리가 더 크고 더 큰 절감 효과를 낳기 때문이다. 그리고 더 최근의 노드는 더 오래된 노드가 더 이상 현재 위치와 비슷하지 않기 때문에 노드 전환 가능성이 더 낮기 때문이다. 다른 전략은 주요 변동에 있는 노드, 트리의 깊이에 관계 없이 하위 트리가 큰 노드, 컷오프를 발생시킨 노드 등을 유지하는 것이다.[6]
- 크기 및 성능
변환이 될 노드의 분율은 작지만, 게임 트리는 기하급수적인 구조여서, 그러한 노드의 극히 적은 수를 캐시 하는 것은 상당한 차이를 만들 수 있다. 체스에서는 복잡한 중간 게임 위치에서 0~50%의 검색 시간 단축, 최종 게임에서 최대 5배까지 검색 시간이 단축된 것으로 보고됐다.[6]
- 관련 기법
포지션의 특정 특징에 대한 평가를 캐싱하기 위해 유사한 기법을 사용할 수 있다. 예를 들어, 폰 해시 테이블을 사용하여 폰 구조에 대한 평가를 위치에 저장할 수 있다. 일반적으로 조사된 폰 포지션 수가 검색된 총포지션 수보다 훨씬 적기 때문에, 폰 해시 테이블은 적중률이 매우 높아 프로그램이 여러 번 재사용되기 때문에 정교한 폰 평가에 더 많은 시간을 할애할 수 있다. 리퓨테이션 테이블은 루트 노드에서 리프 노드로의 이동 순서를 저장하는 데 사용될 수 있다. 여기에는 주요 변동과 열등하다는 것을 보여주는 다른 라인에 대한 반응이 포함된다. 기억력이 더 제한되었던 컴퓨터 체스의 초기에는 테이블의 위치를 바꾸는 대신 리퓨테이션 테이블이 사용되기도 했다. 일부 현대 체스 프로그램에서는 이동 순서를 위한 전환 테이블 외에 리퓨테이션 테이블을 사용한다. 보드의 각 공간에 있는 각 유형의 조각의 가능한 움직임의 정적 비트맵은 프로그램 초기화에 캐시될 수 있으므로, 조각의 법적 움직임(또는 이동 생성을 위한 모든 법적 움직임)을 연속적으로 열거할 필요 없이 단일 메모리 로드로 검색할 수 있다. 이것들은 일반적으로 비트보드 구현에 사용된다.[6]
각주
- ↑ 리차드 그린블라트 아카데믹 - https://enacademic.com/dic.nsf/enwiki/280096
- ↑ 리차드 그린블라트 체스 프로그래밍 위키 - https://www.chessprogramming.org/Richard_Greenblatt
- ↑ 오대석 기자, 〈"알파고, 두 신경망으로 경우의 수 줄여 직관 모방"〉, 《전자신문》, 2016-03-08
- ↑ 박건형 기자, 〈인공지능, 인간 꺾는데 퀴즈 7년·체스 30년… 바둑은 47년?〉, 《조선비즈》, 2016-03-02
- ↑ Monty Newborn, 〈Mac Hack and Transposition Tables〉, 《SpringerLink》, 2016-03-02
- ↑ 6.0 6.1 6.2 6.3 리차드 그린블라트 WikiVisually - https://wikivisually.com/wiki/Richard_Greenblatt_(programmer)
참고자료
- WikiVisually - https://wikivisually.com/wiki/Richard_Greenblatt_(programmer)
- Monty Newborn, 〈Mac Hack and Transposition Tables〉, 《SpringerLink》
- academic - https://enacademic.com/dic.nsf/enwiki/280096
- Chess Programming WIKI - https://www.chessprogramming.org/Richard_Greenblatt
- 오대석 기자, 〈"알파고, 두 신경망으로 경우의 수 줄여 직관 모방"〉, 《전자신문》, 2016-03-08
- 박건형 기자, 〈인공지능, 인간 꺾는데 퀴즈 7년·체스 30년… 바둑은 47년?〉, 《조선비즈》, 2016-03-02
- stephenmcloughlin, 〈Richard D Greenblatt"〉, 《Timetoast》
같이 보기
이 문서는 로고 수정이 필요합니다.
