Evaluation Functions

Imperfect Real-Time Decisions

- 실시간으로 결정을 할 때에는 결함이 존재한다.

- Alpha-beta search 는 terminal state 까지 계산을 하는데 시간이 오래 걸린다. (실제로 바둑, 체스를 alpha beta 로 구현을 할 수 없음) -> 실용적이지 않다.

 

- Heuristic minimax

- terminal state 까지 검사를 하지 않아도 된다.

- terminal state 인지 테스트하는 대신 CUTOFF-TEST 를 사용한다. 원래는 utility(s) 로, s는 terminal state 였다.

그러나 EVAL(s) 에서는 depth-limit 와 유사하게, 제한을 둔 d까지만 탐색을 한다. cutoff 에 도달을 하였다면, EVAL(s) 로 minimax 값을 계산을 해야하고, 도달하지 않았다면 일반적인 minimax 알고리즘과 비슷하게 재귀적으로 호출하게 된다.

 

 

 

Evaluation Functions

terminal state 가 아닌 곳에서 게임을 진행하다 보면 언젠가는 terminal state 에 도달을 할 텐데 그때 기대되는 utility, 즉 utility 를 추정한다. 이는 heuristic 과 비슷하다.

 

- evaluation function 을 평가하는 기준

• terminal states 를 평가한다면 그 결과가 utility function 을 사용해서 얻은 결과와 같아야 한다. 즉, utility function 으로 계산한 값이 u(A) > u(B) 라면, evaluation function 으로 계산한 값도 e(A) > e(B) 가 되어야 한다.
• 계산하는데 오래 걸려선 안된다. -> realtime 이 가능해야 하기 때문에
• nonterminal state 의 경우 실제로 이길 확률과 관련이 있어야 한다. 즉, e(A) > e(B) 라면 A에서 이길 확률이 더 높아야 한다.

 

 

Evaluation Functions for Chess

- state 를 나타내기 위해 feature 을 사용한다.

• of white (black) pawns, queens, ....
• 두 state 가 말의 위치는 다르지만 feature 이 같을 수 있다. -> evaluation function 을 정의하는 입장에서 두 state 는 동등한 class 에 속한다.

- class 에 속하는 state 들이 이기거나 질 확률을 예측할 수 있게 된다.

- 그 추정하는 확률값을 가중치가 주어진 linear function 을 사용하여 나타낸다.

f1, f2,, 는 feature 이고, 그 feature 에 가중치를 곱한 값을 다 더한것을 EVAL(s) 로 사용할 수 있다.

위와 같이 말에 따라 가중치를 부여하여 EVAL(s) 값을 구할 수 있다. (흰색은 내 말, 검은색은 상대편 말)

 

 

 

State-of-the-Art Games Programs

- Chess (1997)

 

- Go (2016)