An aspect of game theory that has received very little attention to data is how to take advantage of an opponent's nonoptimal play. Intuitively an algorithm based on the knowledge of the opponent's actual play or at least a good estimate of his strategy should yield a better performance index than conventional algorithm which assumes that the opponent plays optimally. This study presents an algorithm for a player to improve his performance by adapting optimally over his nonoptimally playing opponent in discrete-time differential games.
The algorithm first estimates the opponent's actual strategies and then constructs an adaptive strategy for the player. The adaptive strategy in periodically updated according to the opponent's behavior using the dynamic programming technique for linear system and the neighboring optimal solution technique for nonlinear system.
The algorithm is applied to both zero-sum and nonzero-sum games and an example is given which demonstrates the superiority of this algorithm over the conventional one which assumes that the opponent plays optimally. The results of this study can be used as an analytical tool for many pursuit-evasion situations such as fighter vs. fighter combat or ship vs. ship battle.
디퍼런샬 게임에서 통상적인 해법으로 유도되는 최적 전략은 saddle-point (zero-sum 게임인 경우) 전략이나 equilibrium-point (nonzero-sum 게임인 경우)전략이다. 이들 최적전략의 잇점은 상대편이 이들 전략을 사용 할 경우에 한하여 다른 전략을 사용 하는 것 보다 이들 최적전략을 사용함으로서 더 좋은 결과를 얻을 수 있는데 있다. 그러나 현실적인 상황을 고려할 때 player가 게임의 진행과정에서 게임 상황의 부정확한 판단이나 계산상의 오차 등으로 인하여 최적전략의 정확한 값을 도출 할 수 없거나, 도출된 전략의 수행 과정에서 여러가지 이유로 인하여 정확한 최적전략을 사용 할 수 없을 경우가 발생한다. 이와 같이 상대편이 정확한 최적전략을 사용 하지 못하는 경우 자기의 최적전략을 고수하기 보다는 상대편의 전략편차를 이용하여 도출된 적응 전략을 사용함으로서 자기에게 보다 유리하게 게임을 유도 할 수가 있다. 본 논문에서는 이러한 상황에서 적용 할수 있는 적응 전략의 해법을 개발 하였다. 본 연구에서 사용된 적응전략의 도출 과정은 다음과 같다.
(1) 도출된 최적전략을 사용 하면서 적의 전략편차를 관찰한다.
(2) 적의 전략편차가 계속될 것이 예상되고 과거의 전략편차에 대한 충분한 자료가 축척되면 적응전략 사용을 결정한다.
(3) 과거의 자료로서 장래의 적의 전략편차를 예측한다.
(4) 예측된 적의 전략편차를 이용하여 최적화 문제를 형성, 적응 전략을 도출한다.
(5) 도출된 적응전략을 사용하면서 예측된 적의 전략편차에 대한 예측오차를 산출한다.
(6) 산출된 오차를 이용하여 전략편차의 예측치를 수정한다.
(7) 수정된 예측치를 이용하여 다음단계의 적응전략을 도출한다.
본 논문에서 다룬 네 가지 게임 상황은 다음과 같다.
상황 1 : 게임 상태 방정식이 변수들(게임 상태변수, 전략변수들)의 선형 함수 형태이고payoff 함수가 이들 변수들의 제곱형의 합으로 표시될 경우의 zero-sum 게임.
상황 2 : 게임 상태 방정식과 payoff 함수가 변수들의 일반적인 비선형 함수 형태 일 때의 zero-sum 게임.
상황 3 : 게임 상태 방정식이 변수들의 선형 함수 형태이고 payoff 함수 들이 이들 변수들의 제곱형의 합으로 표시될 경우의 nonzero-sum 게임.
상황 4 : 게임 상태 방정식과 payoff 함수들이 변수들의 일반적인 비선형 함수 일 때의 nonzero-sum 게임.
제 II 장에서는 맥시민/미니맥스 이론과 동적계획법을 이용하여 상황 1의 경우의 적응전략 도출 해법을 다루었고, 적응전략과 적응전략을 사용할 경우 기대되는 payoff 상의 이득을 적의 전략편차의 함수로 유도 하였다.
제 III 장 에서는 Anderson 의 Near-Optimal 해법을 개선하여 상황 2의 경우에 적용 될 수 있는 적응 전략 도출 해법을 다루었고,
제 IV 장에서는 Stackelberg 전략과 equilibrium-point전략이 동일하게 될 충분조건을 유도하였고, 이 결과와 등적계획법을 이용 하여 상황 3의 경우에 적용될 적응전략을 도출 하고 이 적응전략을 사용 할 경우 기대되는 payoff 상의 잇점을 적의 전략 편타의 함수로 유도 하였다.
제 V 장에서는 제 III 장에서 개발된 해법을 상황 4에 확대 적용 하였고,
제 VI 장에서는 시 계열 모형을 적용하여 적의 전략편차를 예측 하는 절차를 수립하였으며,
제 VII 장 에서는 간단한 예로서 최적전략에 대한 적응전략의 우월성을 설명 하였다.
본 연구 결과에 의하면 만약 적이 최적전략에서 이탈된 전략을 사용할 경우 적응전략을 사용함으로서 open-loop 전략은 물론 closed-loop 전략보다 더 훨씬 유리한 게임을 수행 할 수 있다.
본 연구에서는 적응전략을 완전 정보의 가정 하에서 유도 하였으나 본 해법은 불완전 정보하의 게임 상황에서도 적용 될 수 있으며 player 가 두 사람 이상인 경우에도 적용이 가능하다.
본 연구 결과는 여러 게임 상황에 널리 적용이 가능하나 특히 군 전술연구(전투기의 공중 전투 기동 전술연구, 대 함정기동 전술연구)에 효과적으로 활용 될 수 있다.
