TD-Gammon은 1990년대 IBM의 토머스 J. 왓슨 연구 센터에서 제럴드 테사우로가 개발한 컴퓨터 주사위 놀이 프로그램이다. 그 이름은 시간차 학습, 특히 TD-Lambda에 의해 훈련된 인공 신경망을 사용한 데서 유래한다. 이 프로그램은 인간이 추구하지 않았던 전략을 탐구했고 올바른 백개먼 플레이 이론의 발전에 기여했다. 1993년, TD-Gammon(버전 2.1)은 150만 번의 자가 대국으로 훈련되었으며, 당시 인간 최고의 백개먼 플레이어와 겨루기에 약간 못 미치는 수준의 플레이를 달성했다. 1998년, 100경기 시리즈 동안 세계 챔피언에게 단 8점 차이로 패배했다. 일부 개방 전략에 대한 비전통적인 평가는 전문가들에 의해 받아들여지고 채택되었였다. TD-Gammon은 일반적으로 강화 학습과 신경망의 초기 성공 사례로 인용되며, 딥 큐 강화학습(deep Q-learning)과 AlphaGo에 대한 논문에서 참고되었다.
플레이와 학습 알고리즘
플레이 중에 TD-Gammon은 각 차례마다 모든 가능한 합법적 움직임과 그에 대한 모든 가능한 응답(전방 검색)을 조사하고, 각 결과로 생기는 보드 위치를 평가 함수에 입력하여 가장 높은 점수를 얻는 보드 위치로 이어지는 움직임을 선택한다. 이러한 면에서 TD-Gammon은 거의 다른 모든 컴퓨터 보드 게임 프로그램과 다르지 않다. TD-Gammon의 혁신은 평가 함수를 학습하는 방법에 있었다.
TD-Gammon의 학습 알고리즘은 각 차례 후 신경망의 가중치를 업데이트하여 이전 차례 보드 위치의 평가와 현재 차례 보드 위치의 평가 사이의 차이를 줄이는, 즉 "시간 차이 학습"(temporal-difference learning)을 사용한다. 모든 보드 위치의 점수는 프로그램이 가능한 각 게임 결과의 가능성을 추정한 개의 숫자로 구성된다: 백(White)이 정상 승, 흑(Black)이 정상 승, 백이 백룬(gammon) 승, 블랙이 개먼 승. 게임 최종 보드 위치에서는 프로그램 자신의 보드 위치 평가가 아니라 실제 게임 결과와 비교하여 학습한다.
TD-Gammon의 핵심은 3개의 층으로 이루어진 신경망이다. 입력 층은 두 유형의 뉴런으로 구성된다. 첫 번째 유형은 보드 위치를 인코딩합니다: 0에서 15까지의 비음수 정수로 각 보드 위치에 있는 백 또는 흑의 체커 수를 나타내며, 각각 99개의 입력 뉴런으로 이루어 전체 198개의 뉴런이 된다. 다른 유형은 수공(hand-crafted)된 특징을 인코딩하며, 이전에 Neurogammon에서 사용된 "전진 앵커", "봉쇄 강도", "홈 보드 강도" 및 "단일 체커"가 맞을 확률과 같은 인간 전문가가 사용하는 표준 개념을 나타내는 특징을 담고 있다. 은닉층에는 은닉 뉴런이 있으며, 이후 버전에서는 더 많다. 출력 층에는 4개의 뉴런이 있으며, 현재 보드가 각각: 백 정상 승, 백 개먼 승, 흑 정상 승, 흑 개먼 승으로 이어질 확률("상동 분율"로 불림)을 평가한다. 백그먼(백들의 최대 승리) 승은 너무 희귀하여 테사우로는 표현하지 않기로 선택했다.
각 차례 후, 학습 알고리즘은 다음 규칙에 따라 각 가중치를 업데이트합니다: w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, 알고리즘은 학습률이며, Y_t는 차례에서의 평가, lambda는 감쇠 매개변수입니다. 작은 람다를 선택하면 성능이 거의 동등하고, 큰 람다는 성능을 저하시키는 것이 발견되었습니다. 이 때문에 1992년 이후 TD-Gammon은 lambda = 0으로 훈련되어 표준 TD학습으로 변형되었으며, 이로 인해 계산량이 약 2배 줄게 되었습니다.
개발 역사
버전 1.0은 간단한 1-ply 검색을 사용했습니다: 각 다음 이동을 신경망으로 평가하고, 가장 높은 점수를 받은 이동을 선택합니다. 버전 2.0과 2.1은 2-ply 검색을 사용했습니다: 먼저 1-ply 분석으로 가능성이 낮은 이동을 제거하고(전향 가지치기), 그 다음 가능한 이동만에 대해 2-ply minimax 분석을 수행하며, 상대의 21 가지 주사위 결과마다(더블이 아닌 것은 두배 가중) 확률로 가중된 최상의 이동을 선택합니다. 버전 3.0와 3.1은 3-ply 검색을 사용하며, 21개 대신 21^2 = 441 개의 주사위 결과를 고려합니다. 마지막 버전인 3.1은 1998년 AAAI Hall of Champions의 전시 경기에서 Malcolm Davis와 대결하도록 특별 훈련되었습니다. 즉시 -8점으로 패배했고, 주요 원인은 TD-Gammon이 더블을 선택하고 -32점으로 게임온을 당한 하나의 실수였습니다.
실험과 학습 단계
Neurogammon(또한 테사로가 작성)을 포함한 이전의 신경망 백감 프로그램이 "정확한" 평가를 제공하는 전문가에 의해 훈련된 반면, TD-Gammon은 처음에는 "지식 없는" 상태로 프로그래밍되었습니다. 초기 실험에서는 인간이 설계한 특징 없이 원시 보드 인코딩만을 사용하여 TD-Gammon은 Neurogammon 수준인 중급 인간 백갱 선수 수준에 도달했습니다.
TD-Gammon는 자체 통찰력 있는 특징을 발견했지만, 테아로는 Neurogammon과 같은 수제 특징을 사용하여 플레이를 개선할 수 있는지 궁금했습니다. 실제로, 전문가가 설계한 특징을 사용한 자가 학습 TD-Gammon은 이전의 모든 컴퓨터 백감 프로그램을 곧 능가했습니다. 약 15,000,000개의 게임(자가 대전)이후 개선이 중단되었고, 198개의 입력 뉴턴이 전문가 특징을 인코딩하고, 80개의 은닉 뉴런, 그리고 승리 확률을 예측하는 하나의 출력 뉴런을 가진 신경망을 사용했습니다.
백그먼 이론 발전
TD-Gammon의 독점적 자가 대전 훈련(모방 학습 대신)은 인간이 이전에 고려하지 않았거나 잘못 판단한 전략을 검토할 수 있게 했습니다. 이 프로그램의 비전통적 전략 성공은 백그먼 커뮤니티에 큰 영향을 미쳤습니다. 1991년 후반, Bill Robertie, Paul Magriel, Malcolm Davis는 TD-Gammon(버전 1.0)과 경기에 초청되었으며, 총 51 게임을 진행했습니다. TD-Gammon는 -0.25 ppg로 패배했습니다. Robertie는 TD-Gammon을 강한 인간 선수 수준으로 보았으며, 이후 전문가들에 의해 채택되고 개방 전략 이해를 변경했습니다.
영향과 유산
TD-Gammon은 머신러닝과 인공지능 분야에서 중요한 이정표로 널리 인정되며, 신경망이 자가 대전과 시간차 학습을 통해 복잡한 전략 게임을 학습할 수 있음을 증명했습니다. 그 성과는 강화 학습의 후속 작업에 영감을 주었고, 딥 Q 네트워크와 AlphaGo와 같은 발전에 영향을 미쳤습니다. 또한 TD-Gammon가 인간이 놓친 새로운 전략을 발견하는 것은 신경망이 게임에서 인간의 추론을 초월할 가능성을 보여주었으며, AI 연구 역사상 고전적인 예로 남아 있습니다.