�� ���� ������ ���ǵ� Game Programming Gems 3 �ѱ�����(���� ��, ������ȭ��)�� �Ϻ��Դϴ�. �� �ۿ� ���� ��� �Ǹ��� ������ȭ�簡 ������ ������, ���� ��� ���̴� �� ����Ʈ �Խø� ����� ��� ������ ������� �����Ǿ� �ֽ��ϴ�.

�� ���� ���� ���� ���� �����̹Ƿ� ��Ÿ�� ������ ���� �� �ֽ��ϴ�. ���� �� �������� �Ѱ� ��, ������ ���̿� �μ�� ���¿ʹ� �ٸ� �� �ֽ��ϴ�. ���� å������ ǥ�� ������ �� �� ��Ȯ�� ���·� ǥ�õ� ���̸� �׸�/��ǥ ���� ������ ������ �ѱ�ȭ�� ���Դϴ�.

Game Programming Gem 3 �ѱ����ǿ� ���� ������ GPG ���͵�(http://www.gpgstudy.com/)���� ���� �� �ֽ��ϴ�.

3.5 AI ������Ʈ, ��ü, ����Ʈ�� ���� Ȯ�强�ִ� Ʈ���� �ý���

Steve Rabin, Nintendo of America, Inc.
steve_at_aiwisdom.com

������ 1�ο� ������ �Ļ��ع��� �÷��̾�� ������ �� ���� �������̳� ���� �����⸦ ã�� �ȴ�. �׸��� ������ �����Ϸ��� �׷� ��뿡�� ������ �� �־�� �Ѵ�. Ȯ�强 �ִ� ������� ����Ʈ���� �� ����� ���ӿ� ���� �ϳ��� ǰ�� �������� ���ֵ� �� ������, ������ �Ϲ����� ������ ����� �÷��� �� �ִ�. ������ �װ��� RTS�̵� �ƴϸ� RPG�� �׼��̵�, �÷��̾ ��� ���·ε� �������� Ŀ����ȭ�ϰų� ���ο� �������� �߰��ϴ� ���� �����ؾ� �Ѵ�.

Baldur��s Gate, StarCraft, Dungeon Siege�� �Ǹ��� �������� �򰡵Ǵ� �������� �÷��̾ ���ο� ����Ʈ���� ����ų� ������� AI�� �����ϰ� Ȯ���ϴ� ���� �����ϴٴ� ���鵵 ���Եȴ�. �׷��� �÷��̾�� ���α׷��Ӱ� �ƴϹǷ� �÷��̾�鿡�� ������ ���α׷��� �� ��쵵�� �ϰų� ������� �����ϴ� ���� �Ұ����ϴ�. ����� �÷��̾ ������ �����̳� ����Ʈ�� ���� �� �������� �������ٵ� �ܼ����� ����Ǿ�� �ϴµ�, �׷��� �ܼ����� Ȯ�强�ִ� Ʈ���� �ý����� ���ؼ� ������ �� �ִ�.

Ʈ���� �ý����� �Ұ�

Ʈ���� �ý����� �������� ���ϰ� ������ �����Ѵ١���� �� ���� ������ ���� �߾� ����ȭ�� �ڵ��̴�. �Ϸ��� ���ǵ��� �����Ǹ�, �Ϸ��� �������� ����ȴ�. �̷��� ������ �ý����� ����ϰ�, �����ϱ� �����, ������ �ֵ���[Rabin0]���� ����⵵ ����. Ʈ���� �ý����� �پ��� ������ �������� �ذ��� �� ������, Ư�� �����̳ʿ� �÷��̾ ���� ������ �� �ִٴ� ������ �ٶ����ϴ�. Ʈ���� �ý����� �ŷ��� �������ٵ� �÷��̾ Ž���� ��̷Ӱ� ��ȣ�ۿ����̸� ���ο� ȯ���� ���� ���� �� �ֵ��� �Ѵٴ� �� �ִ�.

�ϴ��� ���谡���� ������ Ž���ϴ� ������ �����غ���. ������ ���� ������ ����ϴ� ���� ������ ���� ��տ� ������ �Ұ� �ȴ�. �׸��� �λ����� ������ �������� ������ �� �ٶ��� �Ҿ� �� ȶ�ҵ� ���߸���. ������ ȶ�ҿ� ���� ���� �� ������ ���� �����ſ� �����̿� �� ���� ����ϸ��ϡ���� ������ ������ ���� ���. ��� �����غ� ��, ü���� ���ſ� ��� �ϳ��� ���� ����� ��ħ�뿡 �÷����Ҵ��� ���� ������ ������.

������ ����-���� �з������� �̿��ϴ� Ʈ���� �ý������� �̷��� ��ǵ��� �����ϴ� ���� �����ϴ�. ����� Ư�� ��� ��ü�� 1���� �̳��� �����ϸ� �ٶ� �Ҹ��� �ش��ϴ� ���� ȿ���� ����ϰ� �� �ֺ��� ȶ�ҵ��� ���߸��ٴ���, �÷��̾��� ��Ƽ ����� �� �ϳ��� ���� ����� ��ħ�� ���� �ö󰡸� ���� ���� ���� ������ ���� ���� ȿ���� ����ϴ� ���� ��� ����-���� �з����ӿ� ���Ѵ�.

Ʈ���� �ý����� �� �����Ѵٸ�, �����̳ʿ� �÷��̾� ��ΰ� ��â���� �ó����� �� ����Ʈ�� �ۼ��� ���� ���� �ð� ���� �����ϵ��� ���� �� �ִ� ��ġ���� ���� �� �ִ�. StarCraft �� ������� ������ ���� ���� Ʈ���� �ý����� ���̴�. ������ �ý����� �����ϰ� ���ο� ���̵� ����� ���� ���� �������� �⺻���� �ڼ��̴�.

��ü�� �����ϴ� Ʈ���� �ý���

Ʈ���� �ý����� ó�� ���� ������ �ϳ��� ������ Ʈ���� �ý���([Orkin02]�� ���� �� ����)�� ���ø��� �� ���̴�. �׷��� �� �� ������ ������ ���Ѵٸ� ��� ������Ʈ�� ��ü, ����Ʈ�� ������ �� �ִ� Ʈ���� �ý��� Ŭ������ ������ �� �� �ִ�. ��� ��ü�� Ʈ���� �ý����� ������ �ϴ� ���� �ƴ�����, ��ü���� �ڽ��� Ʈ���� �ý��� �ν��Ͻ��� ���� �� �ִٸ� ��ü �ȿ� �����͸� ĸ��ȭ�ϴ� ������ ������ �Ǹ� �ý����� �� �� �����ϰ� ��ü�������� �� �� �ִ�. ���� Ʈ���Ŷ�� �� ��ü�� Ư�� ��ü�� ���� �۵��ϰ� �ǹǷ�, �÷��̾ ������ ��� ������ ������ �ȴ�.

�������� �ٰ����� ������ ������ ����� �����غ���. �׷��� ����� ���� ������ �ȿ��� �����ϰ� �ű⿡ ������ ������ �ൿ�� �����ϴ� �ϳ��� Ʈ���� ���Ǹ� �ο��Ѵ�. �׸��� �����̳ʳ� �÷��̾ ������ ���� ���� �׷��� ��յ��� ��ġ�ϸ�, �����ϰԵ� �ǵ��ߴ� ����� ����� �� �� �ְ� �ȴ�. �̴� Ʈ���� �ൿ�� ��ü�� ���� �����Ǿ� �ֱ� ������ ������ ���̴�. �̷� ��Ŀ����� ��� ������Ʈ�� ��ü, ����Ʈ�� �������� �ش� ��ü���� ���� �����ϴ� �ڽŸ��� ������ Ʈ���� �ý����� ���� �� �ִ�.

������ ����

���� �ȿ��� ����ȭ�� �� �ִ� �̺�Ʈ�� ���¶�� ��� ���̶� ������ �� �� �ִ�. ������ ���� ���� �ȿ� ���������� �μ����̳� ���� �����⸦ ���ؼ� ������ �� �ִ� ������ �ſ� ũ��. ������ ������ �� ���� ���ǵ��̴�.

�ο� ������ ����� ���ǵ�

���ǵ��� AND, OR, NOT, XOR ���� �ο� �����ڵ�� ������ �� �ִٸ� ���ǵ��� �� �� �������� �� �ִ�. ���� ��� �÷��̾ ������, ��������, ���������� �����ؾ߸� � ���� ������ �Ǿ� �ִٸ� ���ǵ��� AND�� ���յǾ�� �Ѵ�. �� � ���� �÷��̾ �����質 �ذ񿭼� �� �ϳ��� ������ �־ ���� �� �ִٸ� ���ǵ��� OR�� ���յǾ�� �Ѵ�. �׸� 3.5.1�� 3.5.2�� �׷��� ���ǵ��� Ʈ�� ������ ǥ���� ���̴�.

                      AND        ���̸� Ʈ���� �ߵ�            �� ����

 ������ ����    �������� ����    �������� ����

�׸� 3.5.1 �� ���� ��� �������̸� ���� ������.

                     OR         ���̸� Ʈ���� �ߵ�              �� ����

 �����踦 ������ ����    �ذ񿭼踦 ������ ����

�׸� 3.5.2 �� �� �ϳ��� �������̸� ���� ������.

�� �� ������ ����, �÷��̾ ������, ��������, ���������� �����ϰ� ������ ������ �Ǵ� �ذ񿭼踦 ������ �־�� ���� ������ �ȴٸ� ��� �ɱ�? �׸� 3.5.3�� �׷��� ���ǵ��� ǥ���� ���̴�.

�̿� ���� �׸����� ���� �ð�ȭ�� �ڵ带 ����ȭ�ϴ� ���� ����� �����Ѵٴ� ������ �߿��� ���Ǹ� ���´�. �� ��Ұ� �ϳ��� Ŭ������ ��� �� ������ Ŭ������ �ʿ��ѵ�, �ϳ��� Operator Ŭ�����̰� �� �ϳ��� Condition Ŭ�����̴�. Operator Ŭ������ ������ �ο� ������ó�� �۵��ϵ��� ������ �� ���̴�. ���� ���� ������, �ǿ����ڵ��� ���Ե� ǥ������ ��Ÿ���� ���ؼ��� �ٸ� Operator �ν��Ͻ����̳� Condition �ν��Ͻ������ �����͵��� ��ϵ� ��ƾ� �Ѵ�. Condition Ŭ������ ������ ���� ������ ���ǵ��� ���� �� �־�� �ϸ�, ������ Ŀ����ȭ�� ���� �μ����� ��ƾ� �Ѵ�.

              AND       ���̸� Ʈ���� �ߵ�               �� ����

 ������ ����  �������� ����  �������� ����              OR

                                     �����踦 ������ ����   �ذ񿭼踦 ������ ����

�׸� 3.5.3 ���� �� �� ������ ���ǵ�

������ ����

���� �ȿ��� �����ϰ��� �ϴ� ���³� �ൿ�̶�� ��� �͵� ������ �� �� �ִ�. ���ǰ� ����������, ���� ��ü�� ���� ���� �ȿ� ���������� �μ��� �Ǵ� ���� �����⸦ ���ؼ� ������ �� �ִ�. ������ ������ �������� ����̴�.

Ư�� ���ǵ��� ������ �����Ǹ� �׿� �ش��ϴ� ������ ����ȴ�. �̸� �� �ϳ��� ������ �ƴ϶� ���� ���� �������� �������� Ȯ���� ���� �ִ�. �׷��� �ϸ� �ϳ��� Ʈ���� �ߵ��� ���� ���� �͵鿡 ���ÿ� ������ ��ġ�� �� ���� �ְ�, ���� ������ �� ������ ���� ����ǵ��� �� ���� �ִ�.

Ʈ������ ��

Ʈ���ſ� ���ǵ��� ���ǵǾ��ٰ� �� ��, �������� �ʿ��� ���� �� Ʈ������ ���ǵ��� ���ؼ� �ߵ� ���θ� �Ǵ��ϴ� �����̴�. �켱 ������ ����, Ư�� ������ �̺�Ʈ �ֵ�������(Ʈ���� �ý��ۿ� �̺�Ʈ�� �����DZ⸦ ��ٸ��� ��) �ƴϸ� ���� ���踦 �ֱ������� �����ؾ� �ϴ����� �����ϴ� ���̴�. �� ��� ��� �����ϴ� ���� �������� ������ �ȴ�.

�̺�Ʈ �ֵ����� ������ ���, �̺�Ʈ�� Ʈ���� �ý��ۿ� ������ �� �ֵ��� �ϴ� �������̽��� �ʿ��ϴ�. ���� ������ ����� �̺�Ʈ �޽����� ����ϴ� ���̴�. �̺�Ʈ �޽����� �߻��� �̺�Ʈ�� ������ �̺�Ʈ�� ���õ� ��Ÿ ������ ������ �����ȴ�. �̺�Ʈ �޽����� ���� �� �� �ڼ��� ������ [Rabin02]�� �����ϱ� �ٶ���.

�ֱ��� ���� ����� �����̶��, Ʈ���� �ý��� �ȿ��� ������ ���ǵ��� �����ϴ� ��� ���� �Լ��� ȣ���ϴ� ��Ŀ� ���� �����غ� �� �ִ�. �׷� �Լ����� �̺�Ʈ �ֵ��� ���ǵ鿡 ���� ������ �Ͼ�� �ʾƾ� �Ѵ�.

�̺�Ʈ �޽����� �ֱ��� ���� ������ Ʈ���� �ý��ۿ� ���Դٸ�, �װ��� ���ǵ鿡�� �����ؾ� �Ѵ�. �׸� 3.5.4�� �̺�Ʈ �޽����� �ֱ��� ���� ��θ� �䱸�ϴ� �ϳ��� ���� ������ ���̴�. ���� ������ �浹 �̺�Ʈ�� ��ٸ��� �ݸ�, �ݸ� ������ ������ �ֱ��� ���� ������ ������ �� ������ �����Ѵ�.

�̺�Ʈ �޽����� �ֱ��� ���� ������ Ʈ���� �ý��ۿ� ������, �װ��� �� Ʈ������ ��Ʈ Operator �ν��Ͻ��� �����Ѵ�. Operator�� �װ��� �ڽ��� �ڽĵ鿡�� �Ѱ��ָ�, �ڽĵ��� �׿� ���� �Ǵ� ����� ������ �Ǵ� ������������ �����ش�. �� �ڽ� ���� �׷��� ��û�� �ڽ��� �ڽĵ鿡 �Ѱ��ش�. �׷��� ��û�� ���� ���ǿ� �����ϸ� ��/���� ������ �Ͼ�� �ǰ�, �� ������� ���� Operator �ν��Ͻ��� �ö󰡼� �ο� �����ڿ� ���� ��/���� ������ �Ͼ��. �׷� ������ ��/������ ��Ʈ���Ա��� �ö󰡸� �������� ����� ���������.

 �̺�Ʈ �޽��� �� 
 �ֱ��� ���� ����

                       AND                ���̸� Ʈ���� �ߵ�         �� 10 ���� ����

 �÷��̾ 10 ���� �̳�     �÷��̾��� �ǰ��� 50% �̻�

�׸� 3.5.4 �ϳ��� Ʈ���Ű� �̺�Ʈ �ֵ��� ����(�Ʒ� ����)�� �ֱ��� ���� ����� ����(�Ʒ� ������)�� ��� ���� ��

Operator Ŭ������ �ڽĵ��� ó���� �� ���� ��(lazy evaluation)�� ����ؾ� �Ѵٴ� ���� �����ϱ� �ٶ���. ��� ������ �ش� �����ڿ� ���� �������� ���� ���, Ʈ������ ������ �� �������� ������. ���� ��� �׸� 3.5.4���� ��� �̺�Ʈ �޽����� ���� ���ǿ� ���޵ǰ� �װ��� ������������ �����Ǿ��ٸ� ������ �������δ� �� �̺�Ʈ �޽����� ���޵��� �ʵ��� �ϴ� ���̴�. �̷��� �ϸ� ó�� �ð��� ���̴� �� ������ �ȴ�.

�� �ٸ� �߿��� �� �ϳ���, �̺�Ʈ �ֵ��� ������ ��� ������ ���������� �缳���DZ� �������� �̺�Ʈ���� ����ϰ� �־�� �Ѵٴ� ���̴�. �׸� 3.5.4�� �������� �÷��̾ 10���� �̳��� �����ϸ� �浹 �̺�Ʈ�� Ʈ���ſ� ���޵Ǿ�� �Ѵ�. ���� ������ �� �̺�Ʈ�� ����� �ΰ�(�÷��̾ 10 ���� �ٱ����� ������ ��������), ������ �̺�Ʈ �޽����� �ֱ��� ���� ���ſ� ���� �׻� �������� ������� �Ѵ�.

��� ��������, Ư�� Ʈ������ ���ǵ��� ��� ���� �����شٸ� Ʈ���Ű� �ߵ��ȴ�. Ʈ���Ű� �ߵ��Ǹ� �ߵ��Ǿ��ٴ� ����� ����ؼ� ���޾� �ٽ� �ߵ��Ǵ� ���� ������ �ؾ� �Ѵ�.

���� �ߵ��� �缳�� �ð�

��� Ʈ���ŵ鿡�� �߰������� �� ���� �Ӽ����� �� �ʿ��ϸ�, �� �Ӽ����� �����̳ʰ� �����ϰ� �ȴ�.

 bool SingleShot;  // Ʈ���Ű� �� ���� �ߵ��Ǿ�� �ϴ����� ����
 float ReloadTime; // Ʈ���Ű� ���� �� �ߵ��Ǿ�� �ϴ� ���,
                   // �缳���DZ������ �ð�

�� �� �Ӽ����� Ʈ���Ű� �� �� �̻� �ߵ��� �� �ֵ��� �Ѵ�. SingleShot �Ӽ��� Ʈ���Ű� �� ���� �ߵ��Ǿ�� �ϴ��� �ƴϸ� ���� �� �ߵ��� �� �ִ����� ���θ� ����Ų��. SingleShot�� ���������� ��, ReloadTime�� Ʈ���Ű� �� �� �ߵ��� �� �ٽ� �ߵ��� �� ���� ������, �� ���ǵ��� �ʱ�ȭ�ϰ� �ٽ� �̺�Ʈ�� �ް� �� ������ �ɸ��� �ð��� �����Ѵ�.

Ʈ���Ÿ� �÷��� �� ī���Ϳ� ����

Ʈ���ŵ��� �Բ� ���յ� �� ��������, �ý��� ���� ��� Ʈ���ŵ��� ������ �� ������ ��� ������ �� �ִ� ���µ��� �����ؾ� �Ѵ�. ���� Ʈ���� �ý����� �ߵ��� Ʈ���ŵ��� ���¸� ������ �� �ִ� �Ϸ��� �÷��׵�� ī���͵��� ���� �ʿ䰡 �ִ�. �̸� �ִ��� �Ϲ�ȭ�ϱ� ����, ������ Ʈ���Ű� ���ڿ� �̸����� ������ �� �ִ� ������ �÷��׵��� ���� �� �ֵ��� ����. Ʈ���� �ý����� �÷��� �̸��� ������ �� �÷��׸� �����ϰų�, �����Ǿ� �ִٸ� �ƴϸ� �÷��׸� �����Ѵ�. ������ �÷��״� �ý����� ����� ������ �����ȴ�.

������ ���� ���ο� ���ǵ��� �����غ���.

�̷� ���ǵ��� �߰��ȴٸ�, ������ ���� ���ο� �������� �ʿ��� ���̴�.

�̷��� �÷��׵�� ī���͵��� ������ Ʈ���� �ý����� Ư�� �̺�Ʈ�� ǥ�ø� �ϰų� �ߵ� Ƚ���� �� �� ������, �̸� ���ؼ� ���� ��� �÷��̾ Ư�� ������ �鸰 Ƚ�� ���� �� �� �ִ�. ���� �̺�Ʈ���� Ư���� ������ �߻����� ������(���� ��� �� ���� Ÿ�ϵ��� Ư���� ������ ����� �� ��) Ʈ���Ű� �ߵ��ǵ��� �� ���� �ִ�. �̷��� �÷��׵�� ī���͵��� ���� ������ �����Ƿ�, �� �� ���� ������ Ʈ���ŵ��� ����������.

�׸� 3.5.5�� �÷��̾ � ���� ���� ���ؼ� Ư�� ������ �ݺ������� ã�ƿ��� ��쿡 �� ���⿡ ���� �ܼ��� �����ϴ� ���̴�. �� ���� �������� Ʈ���ŵ��� ��Visited����� �̸��� ī���͸� ���ؼ� ���� ���������� �۵��Ѵٴ� ���� �ָ��ϱ� �ٶ���.

             AND           "Visited"�� ����             AND           "Visited"�� ����
                                                                                      
�÷��̾        "Visited"��               �÷��̾        "Visited"��              
���� A �ȿ� ����  ¦��                      ���� C �ȿ� ����  Ȧ��                     

                             AND      �� D�� ���� 
                                      �ܼ��� ����߸�

                    "Visited"��   �� D�� 
                    8�� ����      �����

_�׸� 3.5.5 �� ���� Ʈ���ŵ��� ��Visited"��� �̸��� ī���͸� ���ؼ� �Բ� �۵��ϴ� ��. �÷��̾ �� D�� ���� ���� ä�� ���� A�� C�� ������ 8�� �湮�ϸ� �ܼ��� ���õȴ�.

�÷��׿� ī���Ͱ� �߰��Ǹ�, Ʈ���� �ý����� ���´� ���� ��Ű����[Isla02]�� �ſ� ���������. �÷��׵�� ī���͵��� ������ �ǰ� Ʈ���ŵ��� ������ ������ �����ϴ� ���� ��õ(knowledge source)�� ������ �ϰ� �Ǵ� ���̴�. �׷��� Ʈ���ŵ��� ��κ� ������ �ܺηκ��� ��Ե� �����Ϳ� ���� �ۿ��ϹǷ�, ������ ���ؼ� Ʈ���� �ý����� �� ���� ��Ű������ ���� �ƴϴ�.

Ʈ���� �ý��� �� ��ũ���� ���

Ʈ���� �ý����� ��ɼ��� ��ũ���� ����� ��ɼ��� ����ϴٴ� ���� ��ġ æ ���ڵ� ���� ���̴�. Ư�� ���� ������ �߰��Ǹ� ���� ���������. �� ���� ��ɼ��� ��ġ�� �κе� �����ϳ�, ������ ����� ���� ��ũ���� �� ���� Ʈ���� �ý����� ������ ���� �������� ������.

�Ѱ�

�� �ۿ��� ���� �� �ý����� �ֵ� �Ѱ�� �Ը𰡺���(scalability)�� ���� �ʴٴ� ���̴�. �׷��� �̷��� ������ ������ Ʈ���ŵ��� �ɷ����� �߰����� �ڵ带 ���ؼ� �ذ��� �� �ִ�. �������� ���� ���ܴ� �̹� �� ȿ���� ������� �����Ǿ���.

�� �ٸ� �Ѱ�� ���ǵ�� �������� �����ϱ� ���� ���ְ� �������� �ȿ� �����Ǿ� �ִٴ� ���̴�. ������� ������ �ڵ�� �����ϴ� �κ��� ���α׷����� ���� ���ľ� �Ѵ�. �̴� ������ ������ �Ǵ� �Ҽ��� �ǵ��� �������κ��� ��ȣ�� �� �ִٴ� ������ �DZ⵵ �ϴ�.

���

������ ���� ������ �ô޸��� ���� �����ڵ鿡�� �־� Ȯ�强 �ִ� Ʈ���� �ý����� ���� ���� ��ġ������ ������ ���� ���� ���̴�. �׷��� ������ ��ŭ�� ��ġ�� ���̸� ���ӿ� �ο��� �� �ִٴ� ���� ���� ���ƾ� �� ���̴�. Ȯ�强�ִ� Ʈ���� �ý����� ���� ���α׷��� �ɷ��� ������ ���� ���� �����̳ʵ� ������ ������ �� �ְ� �ϴ� ȿ������ �����̴�. ��� ���� Ʈ���� �ý����� �ʹ� ������ �ذ�å���� ������ ���� �ְ�����, ��ǥ�� �����̳ʿ� �÷��̾�� �� ���� �ɷ��� �ο��ϴ� �� ������ �ؾ�� �� �ȴ�. ����� ���� ���� ������ �����ϴ� ����� ����� ������� ������ ���� Ȯ��ǰ� �÷��̾�� �� ���� ��̸� ���� �� �ִ�.

�����ڷ�