Rule-Based System (2)

2022.12.12 - [Game AI] - Rule-Based System (1)

Rule-Based System (1)

 

구조 및 인터페이스

---

 

룰베이스 시스템의 알고리즘은 간단하지만 자료구조는 구현이 까다롭다. 특히 매칭해주는 로직이 제일 무겁다.

 

 

DB

DB는 트리구조로 관리된다. 

 

class DataNode :
	string id
    
class DataGroup extends DataNode :
	DataNode[] children
    
class Datum extends DataNode : 
	object value

 

Datum은 실제 값... 몰랐는데 Data가 Datum의 복수형이라고 함  w(ﾟДﾟ)w

 

 

 

규칙

class Rule :
	Match ifClause
	void getActions(Bindings bindings)

bindings에는 조건에 부합하는 DB내의 와일드 카드 데이터들이 들어 있다.

 

 

 

IF절 (If Clause)

class Match :
	boolean matches(DataNode database, out Bindings bindings)

와일드 카드에 대한 데이터는 bindings에 담아준다. bindings를 읽고 수정하므로 레퍼런스로 받아줌. 

 

 

 

아이템 매칭

아이템 매칭에서는 트리를 순회하면서 아이템을 매칭한다. Database의 범위를 제한하고 싶다면 sub-root를 넘겨주는 식으로 작업하면 된다.  

 

 

Datum 매칭

그냥 같은 identifier와 범위 내의 값을 가지고 있으면 매치함. (와일드 카드인 경우의 identifier 비교도 포함)

 

 

Data Group의 매칭 

identifier가 일치하고, data group의 모든 children이 적어도 하나의 DB 내 child와 매칭하면 됨.

 

 

 

 

---

 

 

 

Rule Arbitration 

---

 

동시에 여러가지의 룰을 만족시킬 수 있는 경우가 있을 것임. 이런 경우를 어떻게 처리할지를 중재해주는 방법에 대해 알아보자.

 

First Applicable

- 그냥 처음 만족하는 규칙을 실행시킨다.

- 규칙들은 우선순위에 따라 정렬되어 있을 수 있음.

- 실행되는 애들만 계속 실행될 수 있다. 이런 경우 Flag를 하나 둬서 또 실행이 안 되게 할 수 있는데 Flag는 특정 데이터가 변경되었을 때 초기화해줄 수 있다.

 

 

LRU 

- 이름 그대로 Least Recently Used 인 규칙을 수행하는 것.

- 구현 방법으로는 연결리스트로 규칙들을 관리하고 있다가, 만족하는 규칙을 찾으면 바로 실행하고 리스트의 맨 뒤로 보내주면 됨.

 

 

Random 

- 말 그대로 랜덤. 

- 비효율적임. 무작위로 뽑기 위해서는 모든 규칙의 만족 여부를 계산해야 함.

 

Most Specific Condition

- 말 그대로 가장 구체적인 규칙을 가진 애를 수행한다는 그런 휴리스틱(?)한 방법.

-  if-Clause가 많을 수록 더 구체적이라고 볼 수도 있음.

- 사실상 구체적인 정도를 우선순위로 둔 First Applicable 방법과 동일함.

 

 

Dynamic Priority

- 우선순위를 동적으로 계산한다. 

- 우선순위는 동적으로 바뀔 수 있다. 예를 들어 'HP회복'을 하는 규칙은 HP가 낮을 때 더 우선순위가 높을 것.

- 그럼 HP를 여러 구간으로 나눠놓고 우선순위를 static하게 갈 수도 있지 않냐? 라는 의문이 드는데 동적 우선순위는 우선순위의 변화가 점진적이라서 더 자연스러움.

- 시간이 제일 오래걸린다. 

 

 

 

---

참고 : Ian Millington, AI for GAMES 3rd edition, CRC press, [Chapter 5.8]