Àû´ë Ž»ö

(Adversarial Search)

 

ÀΰøÁö´É-Áö´ÉÇü ¿¡ÀÌÀüÆ®¸¦ Áß½ÉÀ¸·Î : Nils J.Nilsson Àú¼­, ÃÖÁß¹Î. ±èÁØÅÂ. ½É±¤¼·. À庴Ź °ø¿ª, »çÀÌÅع̵ð¾î, 2000  (¿ø¼­ : Artificial Intelligence : A New Synthesis 1998), Page 205~223 

 

µÎ ¿¡ÀÌÀüÆ® °ÔÀÓ (Two-Agent Games)

ÃÖ´ëÃÖ¼Ò ¹æ¹ý (The Minimax Procedure)

¾ËÆÄ º£Å¸ ¹æ¹ý (The Alpha-Beta Procedure)

¾ËÆÄ º£Å¸ ¹æ¹ýÀÇ Å½»ö È¿À² (The Search Efficiency of the Alpha-Beta Procedure)

±âŸ Áß¿äÇÑ »çÇ×µé (Other Important Matters)

È®·ü °ÔÀÓ (Games of Chance)

Æò°¡ ÇÔ¼öÀÇ ÇнÀ (Learning Evaluation Functions)

Âü°í¹®Çå ¹× Åä·Ð (Additional Readings and Discussion)

 

 

µÎ ¿¡ÀÌÀüÆ® °ÔÀÓ

°èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼­ ¾î·Á¿î ¹®Á¦ Áß Çϳª´Â ´Ù¸¥ ´Éµ¿ÀûÀÎ ¿¡ÀÌÀüÆ®µéÀÌ Á¸ÀçÇϴ ȯ°æ¿¡¼­ °èȹÇÏ°í ÇൿÇÏ´Â °ÍÀÌ´Ù. ´Ù¸¥ ¿¡ÀÌÀüÆ®µéÀÌ ¾î¶»°Ô ÇൿÇÒ °ÍÀÎÁö¿¡ ´ëÇÑ Áö½ÄÀÌ ¾ø´Ù¸é, ¿¹Ãø ºÒ°¡´ÉÇÑ ¹Ì·¡¿¡ ´ëÇØ ¸Ö¸® °èȹÇÏÁö ¾Ê°í °¨Áö/°èȹ/Çൿ(sense/plan/act) ±¸Á¶¸¦ »ç¿ëÇÒ ¼ö¹Û¿¡ ¾ø´Ù. ±×·¯³ª ±×·¯ÇÑ Áö½ÄÀÌ ÀÖ´Ù¸é, ¿¡ÀÌÀüÆ®´Â ´Ù¸¥ ¿¡ÀÌÀüÆ®µéÀÇ Çൿ °á°ú¸¦ ¸í½ÃÀûÀ¸·Î °í·ÁÇÏ´Â °èȹÀ» ¼ö¸³ÇÒ ¼ö ÀÖ´Ù. µÎ °³ÀÇ ¿¡ÀÌÀüÆ®°¡ Àִ Ư¼öÇÑ °æ¿ì¸¦ »ý°¢ÇØ º¸ÀÚ. À̵éÀÌ ¼­·Î »ó´ë¹æÀÇ ÇൿÀ» °í·ÁÇÒ ¼ö ÀÖ´Â ÀÌ»óÀûÀÎ ¼³Á¤Àº ¿¡ÀÌÀüÆ®ÀÇ ÇൿÀÌ ¼­·Î ¹ø°¥¾Æ ÀϾ´Â °ÍÀÌ´Ù. ¿ì¼± ÇÑ ¿¡ÀÌÀüÆ®°¡ ÇൿÇÏ°í, ´ÙÀ½ ´Ù¸¥ ¿¡ÀÌÀüÆ®°¡ ÇൿÇÏ´Â ½ÄÀ¸·Î ÁøÇàÇÏ´Â °ÍÀ» ¸»ÇÑ´Ù.

¿¹¸¦ µé¾î ±×¸² 1 ¿¡ ÀÖ´Â °ÝÀÚ °ø°£À» »ý°¢ÇØ º¸ÀÚ. "Èæ" °ú "¹é" À̶ó´Â À̸§ÀÇ µÎ ·Îº¿Àº °¢ÀÚ Çà°ú ¿­ÀÇ ÀÎÁ¢ÇÑ Ä­À¸·Î À̵¿ÇÒ ¼ö ÀÖ´Ù. À̵éÀº ¹ø°¥¾Æ °¡¸ç À̵¿ÇÏ°í (¿¹¸¦ µé¾î ÈæÀÌ ¸ÕÀú À̵¿ÇÏ°í À̾ ¹éÀÌ À̵¿ÇÑ´Ù), ÀÚ±â Â÷·Ê°¡ µÇ¸é ¹Ýµå½Ã À̵¿ÇØ¾ß ÇÑ´Ù. ¹éÀÇ ¸ñÇ¥´Â Èæ°ú °°Àº Ä­¿¡ À§Ä¡ÇÏ´Â °ÍÀ̶ó°í ÇÏÀÚ. ÈæÀÇ ¸ñÇ¥´Â ±×°ÍÀ» ¸·´Â °ÍÀÌ´Ù. ¹éÀº Çϳª °Ç³Ê¸¶´ÙÀÇ ´Ü°è¿¡¼­ ÈæÀÇ À̵¿µµ °í·ÁÇϴ Ž»öÆ®¸®¸¦ ¸¸µé¾î °èȹÀ» ¼ö¸³ÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù. ÀÌ·± Ž»öÆ®¸®ÀÇ ÀϺθ¦ ±×¸² 2 ¿¡ ³ªÅ¸³»¾ú´Ù.

 

±×¸² 1  °ÝÀÚ °ø°£¿¡¼­ÀÇ µÎ ·Îº¿

 

±×¸² 2  µÎ ·Îº¿ÀÇ Çൿ¿¡ ´ëÇÑ Å½»öÆ®¸®

ÃÖ»óÀÇ Ã¹ ¹ø° ÇൿÀ» ¼±ÅÃÇϱâ À§Çؼ­ ¹éÀº °¡´ÉÇÑ °á°ú¸¦ ¾Ë¾Æ³»±â À§ÇØ ÈæÀÌ ¹éÀÇ ¸ñÇ¥¸¦ ÀúÁöÇÏ´Â ¹æÇâÀ¸·Î ÇൿÇÒ °ÍÀ̶ó´Â °ÍÀ» °í·ÁÇϸ鼭 Æ®¸®¸¦ ºÐ¼®ÇØ¾ß ÇÑ´Ù. ÀÌ¿Í °°ÀÌ ´ë¸³ÇÏ´Â »óȲÇÏ¿¡¼­ ¾î¶² °æ¿ì¿¡´Â ÇÑ ¿¡ÀÌÀüÆ®°¡ »ó´ë¹æ ¿¡ÀÌÀüÆ®°¡ ´ÙÀ½¿¡ ¾î¶² ÇൿÀ» ÇÏ´õ¶óµµ ÀÚ½ÅÀÇ ¸ñÇ¥¸¦ ÀÌ·ê ¼ö ÀÖ´Â »óÅ·Π°¡´Â ÇൿÀ» ãÀ» ¼öµµ ÀÖ´Ù. ÀϹÝÀûÀ¸·Î´Â, ¸Þ¸ð¸®¿Í ½Ã°£»óÀÇ Á¦ÇÑ ¶§¹®¿¡ ¾î´À ¿¡ÀÌÀüÆ®µµ ÀÚ½ÅÀÇ ¼º°øÀ» º¸ÀåÇÏ´Â ÇൿÀ» ãÀ» ¼ö ¾ø´Ù. ÀÌ·¯ÇÑ °æ¿ì¿¡ ´ëÇÏ¿©´Â ÈÞ¸®½ºÆ½ÇÏ°Ô ÀûÀýÇÑ ÇൿÀ» ã´Âµ¥ À¯¿ëÇÑ ½Ã°è Á¦ÇÑ (limited-horizon) Ž»ö ¹æ¹ýÀ» »ç¿ëÇÒ °ÍÀÌ´Ù. ¾î´À °æ¿ìµç ¿¡ÀÌÀüÆ®´Â ù ¹ø° ÇൿÀ» °áÁ¤ÇÑ ´ÙÀ½, ±× ÇൿÀ» ½ÇÇàÇÏ°í, »ó´ë ¿¡ÀÌÀüÆ®°¡ ¾î¶² ÇൿÀ» ÃëÇß´ÂÁö¸¦ ÀνÄÇÑ ´ÙÀ½, °¨Áö/°èȹ/Çൿ Çü½ÄÀ¸·Î °èȹ °úÁ¤À» ¹Ýº¹ÇÑ´Ù.

¿©±â¿¡ Á¦½ÃÇÑ °ÝÀÚ °ø°£ ¹®Á¦´Â µÎ ¿¡ÀÌÀüÆ® (two-agent), ¿ÏÀü Á¤º¸ (perfect information), Á¦·Î¼¶ (zero-sum) °ÔÀÓÀ̶ó´Â ¹®Á¦ÀÇ ÇÑ ¿¹ÀÌ´Ù. ¿©±â¼­ ´Ù·ê ÇüÅ¿¡¼­´Â Ç÷¹À̾î (player) ¶ó°í ÇÏ´Â µÎ °³ÀÇ ¿¡ÀÌÀüÆ®°¡ µÑ Áß Çϳª°¡ À̱â°Å³ª (µû¶ó¼­ ´Ù¸¥ ÂÊÀÌ Áö°Å³ª) ¶Ç´Â ºñ±æ ¶§±îÁö ¹ø°¥¾Æ ÇൿÇÑ´Ù. °¢ Ç÷¹À̾î´Â ȯ°æ°ú Àڽſ¡ °üÇÑ ¿ÏÀüÇÑ ¸ðµ¨°ú »ó´ë¹æÀÇ °¡´ÉÇÑ Çൿ ¹× ±× °á°ú¿¡ ´ëÇÑ ¿ÏÀüÇÑ ¸ðµ¨À» °¡Áö°í ÀÖ´Ù (¹°·Ð ¾î´À Âʵµ »ó´ë¹æÀÌ ¾î¶² »óȲ¿¡¼­ ½ÇÁ¦·Î ¹«½¼ ÇൿÀ» ÇÒ °ÍÀÎÁö¿¡ ´ëÇØ ¿Ïº®ÇÑ Áö½ÄÀ» °¡Áö°í ÀÖ´Â °ÍÀº ¾Æ´Ï´Ù). ÀÌ·± Á¾·ùÀÇ °ÔÀÓ¿¡ ´ëÇÑ ¿¬±¸¸¦ ¼öÇàÇÔÀ¸·Î½á, ¿¡ÀÌÀüÆ® »çÀÌÀÇ ¸ñÇ¥°¡ »óÈ£ Ãæµ¹ÇÏÁö ¾Ê´õ¶óµµ, ´Ù¼öÀÇ ¿¡ÀÌÀüÆ®°¡ ÀÖ´Â »óȲ¿¡¼­ °èȹÀ» ¼ö¸³ÇÏ´Â º¸´Ù ÀϹÝÀûÀÎ ¹®Á¦¿¡ ´ëÇØ ÅëÂûÇÒ ¼ö ÀÖ´Ù.

ü½º (chess) ³ª üĿ (checker), ¹ÙµÏ µî ÀϹÝÀûÀÎ °ÔÀÓµéÀÌ ÀÌ ¹üÁÖ¿¡ µé¾î°£´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖÀ» °ÍÀÌ´Ù. ½ÇÁ¦·Î ÀÌ·¯ÇÑ °ÔÀÓÀ» ÇÒ ¼ö ÀÖ´Â ÇÁ·Î±×·¥µéÀÌ ¸¸µé¾îÁ® ÀÖÀ¸¸ç, ¾î¶² °æ¿ì¿¡´Â èÇǾð ¼öÁØÀÇ ´É·ÂÀ» °¡Áø °Íµµ ÀÖ´Ù. Tic-Tac-Toe °ÔÀÓÀº Èï¹Ì ÀÖ´Â °è»ê ¹®Á¦´Â ¾Æ´ÏÁö¸¸, ´Ü¼øÇϱ⠶§¹®¿¡ Ž»ö ±â¹ýÀ» ¼³¸íÇÏ´Â µ¥ ¾ÆÁÖ À¯¿ëÇϹǷΠÀÌ °ÔÀÓÀ» »ç¿ëÇÒ °ÍÀÌ´Ù. ¾î¶² °ÔÀÓµéÀº (Backgammon °ú °°Àº) È®·üÀûÀÎ ¿ä¼Ò°¡ Æ÷ÇÔµÇ¾î ºÐ¼®ÇϱⰡ ´õ ¾î·Æ´Ù. ¸¹Àº °ÔÀÓµé, ƯÈ÷ ü½º¿Í °°ÀÌ ÆÇ À§¿¡¼­ ÇÏ´Â °ÔÀÓµéÀÇ »óÅ°ø°£À» ¼³Á¤ÇÏ´Â µ¥´Â ¾ÆÀÌÄÜ Ç¥ÇöÀÌ ÀÚ¿¬½º·´´Ù. 8 × 8 °ÝÀÚ °ø°£¿¡¼­ Èæ°ú ¹é µÎ ·Îº¿ÀÇ ´Ù¾çÇÑ À§Ä¡¸¦ Ç¥ÇöÇϱâ À§ÇÏ¿© 8 × 8 ¹è¿­À» »ç¿ëÇÑ ¹Ù ÀÖ´Ù. °ÔÀÓ¿¡¼­ÀÇ ÇൿÀº ÇÑ »óÅ ǥÇöÀ» ´Ù¸¥ »óÅ ǥÇöÀ¸·Î ¹Ù²Ù´Â ¿¬»êÀÚ¿¡ ÀÇÇØ ³ªÅ¸³»¾îÁø´Ù. °ÔÀÓ ±×·¡ÇÁ´Â ½ÃÀÛ ³ëµå¿Í °¢ Ç÷¹À̾îÀÇ ¿¬»êÀÚ¿¡ ÀÇÇÏ¿© ¾Ï½ÃÀûÀ¸·Î Á¤ÀǵȴÙ. ù ¹ø° ÇൿÀ» ¼±ÅÃÇÏ´Â µ¥´Â ¿©·¯ °¡Áö ±â¹ýÀÌ »ç¿ëµÉ ¼ö ÀÖÁö¸¸, Ž»öÆ®¸®¸¦ ¸¸µå´Â °ÍÀº ÀÌÀü¿¡ Çß´ø °Í°ú °°Àº ¹æ¹ýÀ¸·Î ÇÒ ¼ö ÀÖ´Ù. ÀÌÁ¦ ÀÌ·¯ÇÑ ±â¹ýµéÀ» ¼³¸íÇÏ°Ú´Ù.

ÃÖ´ëÃÖ¼Ò ¹æ¹ý

°ÔÀÓ¿¡ ´ëÇÑ Áö±ÝºÎÅÍÀÇ ¼³¸í¿¡¼­´Â µÎ Ç÷¹À̾ MAX ¿Í MIN À̶ó°í ÇÒ °ÍÀÌ´Ù. ÁÖ¾îÁø ÀÓ¹«´Â MAX °¡ ¸ÕÀú ÇൿÇÏ°í³ª¼­ µÎ Ç÷¹À̾ ¹ø°¥¾Æ ÇൿÇÑ´Ù°í °¡Á¤ÇÏÀÚ. µû¶ó¼­ ±íÀÌ°¡ ¦¼öÀ̸é MAX °¡ ÇൿÇÒ Â÷·Ê¿¡ ÇØ´çÇÑ´Ù. À̵éÀ» MAX ³ëµå¶ó°í ÇÑ´Ù. ±íÀÌ°¡ Ȧ¼öÀ̸é MIN ÀÌ ÇൿÇÒ Â÷·Ê¿¡ ÇØ´çÇÑ´Ù. À̵éÀ» MIN ³ëµå¶ó°í ÇÑ´Ù. ±íÀÌ°¡ Ȧ¼öÀ̸é MIN ÀÌ ÇൿÇÒ Â÷·Ê¿¡ ÇØ´çÇϸç À̵éÀ» MIN ³ëµå¶ó°í ÇÑ´Ù (°ÔÀÓÆ®¸®ÀÇ Á¦ÀÏ À§ ³ëµå°¡ ±íÀÌ 0 ÀÌ´Ù). °ÔÀÓ Æ®¸®¿¡¼­ °ã ±íÀÌ (ply-depth) ÀÇ ÇÑ °ã (ply) Àº ±íÀÌ ¿Í ¿¡ ÀÖ´Â ³ëµåµé·Î Á¤ÀǵȴÙ. °ÔÀÓÆ®¸®¿¡¼­ÀÇ Å½»ö ¹üÀ§´Â º¸Åë ¾ÕÀ» ¹Ì¸® º¸´Â Á¤µµ¸¦ MAX ¿Í MIN ÀÇ Çൿ ½ÖÀ» ´ÜÀ§·Î ÇÏ¿© ³ªÅ¸³½ °ã ±íÀ̷ΠǥÇöµÈ´Ù.

ÀÌ¹Ì ¾ð±ÞÇÑ ´ë·Î, ´ëºÎºÐÀÇ °ÔÀÓ¿¡¼­ ¿ÏÀüÇÑ Å½»ö (½ÂÆп¡ ´ëÇÑ) Àº ½ÇÁúÀûÀ¸·Î ºÒ°¡´ÉÇÏ´Ù. ü½ºÀÇ °æ¿ì ¿ÏÀüÇÑ °ÔÀÓ ±×·¡ÇÁ¿¡´Â 1040 °³ÀÇ ³ëµå°¡ ÀÖ´Â °ÍÀ¸·Î ÃßÁ¤µÈ´Ù. ÀÚ½Ä ³ëµåµéÀ» 1/3 ³ª³ë Ãʸ¶´Ù Çϳª¾¿ »ý¼ºÇÒ ¼ö ÀÖ´Ù°í °¡Á¤Çصµ ü½º¿¡ ´ëÇÑ ¿ÏÀüÇÑ Å½»ö ±×·¡ÇÁ¸¦ ¸¸µé¾î³»´Â µ¥´Â ¾à 1022 ¼¼±â°¡ °É¸°´Ù (Âü°í·Î, ¿ìÁÖÀÇ ³ªÀÌ´Â ¾à 108 ¼¼±â·Î ÃßÁ¤µÈ´Ù). ´õ¿íÀÌ, ÈÞ¸®½ºÆ½ Ž»ö ±â¹ýµµ ½ÇÁúÀûÀÎ ºÐ±â °è¼ö¸¦ µµ¿òÀÌ µÉ ¸¸Å­ ÃæºÐÈ÷ ÁÙÀÌÁö´Â ¸øÇÑ´Ù. µû¶ó¼­ º¹ÀâÇÑ °ÔÀÓ¿¡ À־´Â °ÔÀÓÀÇ ³¡±îÁö Ž»öÇÑ´Ù´Â °ÍÀº (°ÔÀÓÀÇ ¸¶Áö¸· ºÎºÐ¿¡¼­´Â °¡´ÉÇÒ ¼öµµ ÀÖÁö¸¸) ºÒ°¡´ÉÇÏ´Ù´Â °ÍÀ» ¹Þ¾Æµé¿©¾ß¸¸ ÇÑ´Ù. ´ë½Å °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼­ ¼³¸íÇÑ ½Ã°è Á¦ÇÑ (limited-horizon) Ž»ö°ú °°Àº ¹æ¹ýÀ» »ç¿ëÇØ¾ß ÇÑ´Ù.

Á¾·á Á¶°ÇÀÌ ¹Ù²î¾î¾ß ÇÑ´Ù´Â °ÍÀ» Á¦¿ÜÇÏ°í´Â ±íÀÌ¿ì¼±À̳ª ³Êºñ¿ì¼± ¶Ç´Â ÈÞ¸®½ºÆ½ ¹æ¹ý µîÀ» »ç¿ëÇÒ ¼ö ÀÖ´Ù. ¸î °¡Áö ÀÎÀ§ÀûÀÎ Á¾·á Á¶°ÇÀÌ ½Ã°£ Á¦ÇÑ, ¸Þ¸ð¸® Á¦ÇÑ, ¶Ç´Â Ž»öÆ®¸®¿¡¼­ ³ëµåÀÇ ±íÀÌ¿¡ ´ëÇÑ Á¦ÇÑ µîÀ» ±â¹ÝÀ¸·Î Á¤ÇØÁú ¼ö ÀÖ´Ù. ¶ÇÇÑ ¿¹¸¦ µé¾î ü½º °°Àº °ÔÀÓ¿¡¼­´Â ¸¸ÀÏ °æ°è¿¡ ÀÖ´Â ³ëµå°¡ Áï°¢ÀûÀ¸·Î À¯¸®ÇÑ ±³È¯À» ÇÒ ¼ö ÀÖ´Â ¶óÀ̺ê (live) À§Ä¡¸¦ Ç¥ÇöÇÏ°í ÀÖ´Ù¸é Ž»öÀ» Áß´ÜÇÏÁö ¾Ê´Â °ÍÀÌ ÀϹÝÀûÀÌ´Ù.

Ž»öÀÌ ³¡³ª¸é Ž»öÆ®¸®·ÎºÎÅÍ ÃÖ»óÀ̶ó°í ÃßÁ¤µÇ´Â ÇൿÀ» ã¾Æ³»¾ß ÇÑ´Ù. ÀÌ·¯ÇÑ ÃßÁ¤°ªÀº Ž»öÆ®¸®ÀÇ ´Ü¸» (leaf) ³ëµå¿¡ Á¤Àû Æò°¡ ÇÔ¼ö (static evaluation function) ¸¦ Àû¿ëÇÏ¿© ¾òÀ» ¼ö ÀÖ´Ù. Æò°¡ ÇÔ¼ö´Â ´Ü¸» ³ëµåÀÇ °¡Ä¡¸¦ °è»êÇÑ´Ù. ÀÌ·¯ÇÑ °è»êÀº ³ëµåÀÇ °¡Ä¡¿¡ ¿µÇâÀ» ¹ÌÄ£´Ù°í »ý°¢µÇ´Â ´Ù¾çÇÑ Æ¯Â¡À» ±â¹ÝÀ¸·Î ÀÌ·ç¾îÁø´Ù. ¿¹¸¦ µé¾î ü½º¿¡¼­ À¯¿ëÇÑ Æ¯Â¡µéÀº »ó´ëÀûÀÎ ¸»ÀÇ ÀÌÁ¡, Áß½ÉÀÇ Á¦¾î±Ç, Å·¿¡ ÀÇÇÑ Áß½ÉÀÇ Á¦¾î ¿©ºÎ µîÀ» µé ¼ö ÀÖ´Ù. °ÔÀÓÆ®¸®¸¦ ºÐ¼®ÇÒ ¶§ MAX ¿¡ À¯¸®ÇÑ »óÅ¿¡¼­´Â Æò°¡ ÇÔ¼ö°ªÀÌ ¾ç¼ö, MIN ¿¡ À¯¸®ÇÑ »óÅ¿¡¼­´Â Æò°¡ ÇÔ¼ö°ªÀÌ À½¼ö, ±×¸®°í MAX ³ª MIN ¾î´À Æí¿¡ Ưº°È÷ À¯¸®ÇÏÁö ¾ÊÀº »óÅ¿¡¼­´Â 0 ¿¡ °¡±î¿î °ªÀ» °®µµ·Ï ÇÏ´Â °ÍÀÌ º¸ÅëÀÌ´Ù.

ÁÁÀº ù ¹ø° ÇൿÀº ÃÖ´ëÃÖ¼Ò ÀýÂ÷ (minimax procedure) ¶ó°í ÇÏ´Â ¹æ¹ý¿¡ ÀÇÇØ ¼±Á¤µÉ ¼ö ÀÖ´Ù (´Ü¼øÈ­Çϱâ À§Çؼ­ °ÔÀÓ ±×·¡ÇÁ°¡ Æ®¸®ÀÎ °ÍÀ¸·Î °¡Á¤ÇÏ°í °ü·ÃµÈ ÀýÂ÷µéÀ» ¼³¸íÇÑ´Ù). ¸¸ÀÏ MAX °¡ Ž»öÆ®¸®ÀÇ ´Ü¸» ³ëµå Áß¿¡¼­ Çϳª¸¦ ¼±ÅÃÇÑ´Ù¸é Æò°¡ °ªÀÌ °¡Àå Å« °ÍÀ» ¼±È£ÇÑ´Ù°í °¡Á¤ÇÏÀÚ. MAX ´Â ÀÚ½ÅÀÇ Â÷·Ê°¡ µÇ¸é ½ÇÁ¦·Î ±× ³ëµå¸¦ ¼±ÅÃÇÒ °ÍÀ̱⠶§¹®¿¡ MIN ´Ü¸» ³ëµåÀÇ ºÎ¸ð ³ëµåÀÎ MAX ³ëµåÀÇ Àü´Þ°ª (backed-up value) Àº ´Ü¸» ³ëµåµé¿¡ ´ëÇÑ Æò°¡°ª Áß ÃÖ´ë°ªÀÌ µÈ´Ù. ¹Ý´ë·Î ¸¸ÀÏ MIN ÀÌ ´Ü¸» ³ëµå Áß¿¡¼­ Çϳª¸¦ ¼±ÅÃÇÑ´Ù¸é °¡Àå ÀÛÀº °ª (À½¼ö·Î °¡Àå Å« °ª) À» °¡Áø ³ëµå¸¦ ¼±ÅÃÇÒ °ÍÀÌ´Ù. MIN Àº ÀÚ½ÅÀÇ Â÷·Ê°¡ µÇ¸é ½ÇÁ¦·Î ±× ³ëµå¸¦ ¼±ÅÃÇÒ °ÍÀ̱⠶§¹®¿¡ MAX ´Ü¸» ³ëµåÀÇ ºÎ¸ð ³ëµåÀÎ MIN ³ëµå´Â ´Ü¸» ³ëµåµé¿¡ ´ëÇÑ Æò°¡°ª Áß ÃÖ¼Ò°ªÀ» Àü´Þ°ªÀ¸·Î ¹Þ°Ô µÈ´Ù. ¸ðµç ´Ü¸» ³ëµåÀÇ ºÎ¸ð ³ëµåµé¿¡ Àü´Þ°ªÀÌ ÁöÁ¤µÈ ´ÙÀ½¿¡´Â, MAX ´Â ÀÚ½Ä MIN ³ëµåµé Áß¿¡¼­ Àü´Þ°ªÀÌ ÃÖ´ëÀÎ ³ëµå¸¦ ¼±ÅÃÇÏ°í, MIN Àº ÀÚ½Ä MAX ³ëµåµé Áß¿¡¼­ Àü´Þ°ªÀÌ ÃÖ¼ÒÀÎ ³ëµå¸¦ ¼±ÅÃÇÑ´Ù´Â °¡Á¤ÇÏ¿¡¼­ ÀÌ °ªµéÀ» ÇÑ ´Ü°è À§·Î ´Ù½Ã Àü´ÞÇÑ´Ù.

ÀÌ Àü´Þ °úÁ¤À» ½ÃÀÛ ³ëµåÀÇ ÀÚ½Ä ³ëµåµéÀÌ ¸ðµÎ Àü´Þ°ªÀ» ¹Þ°Ô µÉ ¶§±îÁö ÇÑ ´Ü°è¾¿ ÁøÇàÇÑ´Ù. ½ÃÀÛÀº MAX ÀÇ Â÷·Ê¶ó°í °¡Á¤ÇÏ¿´À¸¹Ç·Î, MAX ´Â °¡Àå Å« Àü´Þ°ªÀ» °¡Áø ÀÚ½Ä ³ëµå¿¡ ÇØ´çÇÏ´Â ÇൿÀ» ¼±ÅÃÇÑ´Ù.

ÀÌ¿Í °°Àº °úÁ¤ÀÇ Á¤´ç¼ºÀº ½ÃÀÛ ³ëµåÀÇ Àڽĵé·ÎºÎÅÍ Àü´ÞµÇ´Â °ªµéÀÌ °¢ »óȲ¿¡ ´ëÇÏ¿© Á÷Á¢ÀûÀ¸·Î Á¤Àû Æò°¡ ÇÔ¼ö¸¦ Àû¿ëÇÏ¿© °è»êÇÏ´Â °Íº¸´Ù ±Ã±ØÀûÀÎ °¡Ä¡¸¦ Á» ´õ Á¤È®ÇÏ°Ô ³ªÅ¸³½´Ù´Â °¡Á¤ÇÏ¿¡¼­ ¼º¸³µÇ´Â °ÍÀÌ´Ù. °á±¹ Àü´Þ°ªÀ̶ó´Â °ÍÀº °ÔÀÓÆ®¸®¿¡¼­ ¾ÕÀ» ³»´Ùº¸´Â °ÍÀ» ±â¹ÝÀ¸·Î ÇÏ°í Àֱ⠶§¹®¿¡, º¸´Ù Áß¿äÇÏ´Ù°í ¿©°ÜÁö´Â °ÔÀÓÀÇ ³¡ ºÎºÐ¿¡ ´õ °¡±î¿î »óȲ¿¡¼­ÀÇ Æ¯Â¡µé¿¡ ÀÇÁöÇÏ´Â °ÍÀÌ´Ù.

Tic-Tac-Toe °ÔÀÓÀ» ÀÌ¿ëÇÑ °£´ÜÇÑ ¿¹·Î ÃÖ´ëÃÖ¼Ò ¹æ¹ýÀ» ¼³¸íÇÑ´Ù (Tic-Tac-Toe ´Â ¹ø°¥¾Æ °¡¸é¼­ 3 × 3 ¹è¿­¿¡ Ç¥½Ã¸¦ ÇÏ´Â °ÔÀÓÀÌ´Ù. ÇÑ »ç¶÷Àº X ¸¦ Ç¥½ÃÇÏ°í, »ó´ë¹æÀº 0 ¸¦ Ç¥½ÃÇÑ´Ù. ÇàÀ̳ª ¿­, ¶Ç´Â ´ë°¢¼±À» ¸ÕÀú ÀÚ½ÅÀÇ Ç¥½Ã·Î ä¿î »ç¶÷ÀÌ À̱ä´Ù). MAX °¡ X ¸¦ Ç¥½ÃÇÏ°í, MIN Àº 0 ¸¦ Ç¥½ÃÇϸç, MAX °¡ ¸ÕÀú ½ÃÀÛÇÑ´Ù°í °¡Á¤ÇÏÀÚ. ±íÀÌ Á¦ÇÑÀÌ 2 ÀÎ °æ¿ì, ·¹º§ 2 ÀÇ ¸ðµç ³ëµå°¡ »ý¼ºµÉ ¶§±îÁö ³Êºñ¿ì¼± Ž»öÀ» ¼öÇàÇÑ ´ÙÀ½, ÀÌµé ³ëµå¿¡ ´ëÇÏ¿© Á¤Àû Æò°¡ ÇÔ¼ö¸¦ Àû¿ëÇÑ´Ù. »óÅ ¿¡ ´ëÇÑ Æò°¡ ÇÔ¼ö °¡ ´ÙÀ½°ú °°ÀÌ ÁÖ¾îÁø´Ù°í ÇÏÀÚ.

Áï, ¸¸ÀÏ °¡ ´ÙÀ½°ú °°´Ù¸é,

°¡ µÈ´Ù.

ÀÚ½Ä ³ëµåµéÀ» »ý¼ºÇÒ ¶§´Â ´ëĪ¼ºÀ» °í·ÁÇÑ´Ù. ±×·¯¸é ´ÙÀ½ÀÇ »óŵéÀº ¸ðµÎ µ¿ÀÏÇÑ °ÍÀ¸·Î °£ÁֵȴÙ.

 

(°ÔÀÓ Ãʱ⿡´Â ´ëĪ¼º ¶§¹®¿¡ ºÐ±â °è¼ö°¡ ÀÛ°Ô µÇ°í, ³ªÁß¿¡´Â °¡´ÉÇÑ »óÅ°¡ Àû±â ¶§¹®¿¡ ºÐ±â °è¼ö°¡ ÀÛ°Ô µÈ´Ù.)

 

±×¸² 3  Tic-Tac-Toe Ž»öÀÇ Ã¹ ¹ø° ´Ü°è

±×¸² 3 ¿¡ ±íÀÌ 2 ±îÁö Ž»öÇßÀ» ¶§ »ý¼ºµÇ´Â Æ®¸®¸¦ ³ªÅ¸³»¾ú´Ù. Á¤Àû Æò°¡°ªÀº ´Ü¸» ³ëµåÀÇ ¿À¸¥ÂÊ¿¡ ³ª¿Í ÀÖ°í, Àü´ÞµÈ °ªµéÀº µ¿±×¶ó¹Ì ¾È¿¡ ÀÖ´Ù. ¾Æ·¡ÀÇ »óÅ°¡ °¡Àå Å« Àü´Þ°ªÀ» °¡Áö°í ÀÖÀ¸¹Ç·Î, ÀÌ »óÅ·Π°¡´Â °ÍÀÌ Ã¹ ¹ø° ÇൿÀ¸·Î ¼±ÅõȴÙ.

(¿ì¿¬È÷µµ, ÀÌ°ÍÀº ¿ÏÀüÇÑ Å½»öÀÌ ¼öÇàµÇ¾îµµ ¿ª½Ã MAX ÀÇ ÃÖ»óÀÇ ÇൿÀÌ´Ù.)
ÀÌÁ¦ °¨Áö/°èȹ/Çൿ Áֱ⿡ µû¶ó MAX °¡ À§ÀÇ ÇൿÀ» ÃëÇÏ°í MIN Àº ¿©±â¿¡ ´ëÇØ X ÀÇ ¿ÞÆí¿¡ 0 ¸¦ Ç¥½ÃÇß´Ù°í ÇÏÀÚ (ÀÌ°ÍÀº ¼­Åõ¸¥ ÇൿÀ¸·Î, MIN Àº ÁÁÀº Ž»ö Àü·«À» °¡Áö°í ÀÖÁö ¾ÊÀº °ÍÀÌ Æ²¸²¾ø´Ù). ±× ¾Æ·¡·Î ±íÀÌ 2 ¸¸Å­ ´Ù½Ã MAX °¡ Ž»öÀ» ¼öÇàÇÏ°í, ±× °á°ú ±×¸² 4 ¿¡ ÀÖ´Â °Í°ú °°Àº Ž»öÆ®¸®°¡ ¸¸µé¾îÁø´Ù. ¿©±â¼­´Â µÎ °¡ÁöÀÇ ÃÖ»óÀÇ ÇൿÀÌ °¡´ÉÇÏ´Ù. MAX °¡ ±×¸²¿¡ Ç¥½ÃµÈ ÇൿÀ» ÃëÇß´Ù°í ÇÏÀÚ. MIN Àº ´ÙÀ½°ú °°ÀÌ Áï°¢ÀûÀÎ Æй踦 ÇÇÇÒ ¼ö ÀÖ´Â ÇൿÀ» ÇÒ °ÍÀÌ´Ù.

MAX ´Â Ž»öÀ» ´Ù½Ã ¼öÇàÇÏ¿© ±×¸² 5 ¿Í °°Àº Æ®¸®¸¦ »ý¼ºÇÑ´Ù.
ÀÌ Æ®¸®ÀÇ ÀϺΠ´Ü¸» ³ëµå´Â (¿¹¸¦ µé¾î ¶ó°í Ç¥½ÃµÈ ³ëµå) MIN ÀÌ À̱â´Â °æ¿ìÀÌ¸ç µû¶ó¼­ Æò°¡°ªÀÌ ÀÌ´Ù. ÀÌ Æò°¡°ªµéÀÌ Àü´ÞµÇ¸é, MAX ÀÇ ÃÖ»óÀÇ Çൿµµ ¿ª½Ã Áï°¢ÀûÀÎ Æй踦 ÇÇÇÏ´Â °ÍÀ̶ó´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. ÀÌÁ¦ MIN
Àº ´ÙÀ½ ¹ø¿¡ MAX °¡ ¹«Á¶°Ç À̱ä´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ°í, µû¶ó¼­ MIN Àº Ç׺¹ÇÑ´Ù.

 

±×¸² 4  Tic-Tac-Toe Ž»öÀÇ µÎ ¹ø° ´Ü°è

 

±×¸² 5  Tic-Tac-Toe Ž»öÀÇ ¸¶Áö¸· ´Ü°è

¾ËÆÄ º£Å¸ ¹æ¹ý

¹æ±Ý ¼³¸íÇÑ Å½»ö ¹æ¹ýÀº Ž»öÆ®¸®¸¦ »ý¼ºÇÏ´Â °úÁ¤°ú »óŸ¦ Æò°¡ÇÏ´Â °úÁ¤À» ¿ÏÀüÈ÷ ºÐ¸®ÇÑ °ÍÀÌ´Ù. Æ®¸® »ý¼ºÀÌ ³¡³­ ´ÙÀ½¿¡¾ß ºñ·Î¼Ò »óÅ Æò°¡°¡ ½ÃÀ۵ȴÙ. ±×·¯³ª ÀÌ·¯ÇÑ ºÐ¸®´Â ´ë´ÜÈ÷ ºñÈ¿À²ÀûÀÎ Àü·«ÀÌ´Ù. ¸¸ÀÏ ´Ü¸» ³ëµåÀÇ Æò°¡¿Í Àü´Þ°ª °è»êÀ» Æ®¸®¸¦ »ý¼ºÇϸ鼭 µ¿½Ã¿¡ ÁøÇàÇÏ°Ô µÇ¸é (°°Àº ¼öÁØÀÇ ÁÁÀº ³ëµå¸¦ ¹ß°ßÇϱâ À§ÇØ) ÇÊ¿äÇÑ Å½»öÀÇ ¾çÀ» ³î¶ö ¸¸Å­ ( °æ¿ì¿¡ µû¶ó¼­´Â ÀÚ¸® ¼ö°¡ ¸¹ÀÌ Â÷À̳¯ ¸¸Å­) ÁÙÀÏ ¼ö ÀÖ´Ù. ÀÌ ¹æ¹ýÀº °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼­ ¼³¸íÇÑ ¾ËÆÄ Àý´Ü (alpha pruning) °ú ºñ½ÁÇÏ´Ù.
Tic-Tac-Toe Ž»öÀÇ ¸¶Áö¸· ´Ü°è¿¡ Àִ Ž»öÆ®¸®¸¦ »ý°¢ÇØ º¸ÀÚ (±×¸² 5). ¿©±â¼­ ´Ü¸» ³ëµå¸¦ »ý¼ºÇÏÀÚ¸¶ÀÚ Æò°¡ÇÑ´Ù°í °¡Á¤ÇÏÀÚ. ±×·¯¸é ¶ó°í ¾²¿©Áø ³ëµå°¡ »ý¼ºµÇ°í Æò°¡µÈ ´ÙÀ½¿¡´Â ³ëµå , , ¸¦ »ý¼º (±×¸®°í Æò°¡) ÇÏ´Â °ÍÀÌ ¾Æ¹« Àǹ̰¡ ¾ø´Ù. Áï, MIN ÀÌ ¸¦ ¼±ÅÃÇÒ ¼ö ÀÖ°í, º¸´Ù ´õ ¼±È£ÇÏ´Â ³ëµå°¡ ÀÖÀ» ¼ö ¾ø±â ¶§¹®¿¡, MIN Àº ¸¦ ¼±ÅÃÇÒ °ÍÀ̶ó´Â °ÍÀ» Áï°¢ ¾Ë ¼ö ÀÖ´Ù. ±×¸®°í ³ª¸é ÀÇ ºÎ¸ð ³ëµå¿¡ Àü´Þ°ª ¸¦ ÁöÁ¤ÇÒ ¼ö ÀÖ°í, ³ëµå , , ¸¦ »ý¼ºÇÏ°í Æò°¡ÇÏ´Â ¼ö°í¸¦ ÇÏÁö ¾Ê°íµµ Ž»öÀ» ÁøÇàÇÒ ¼ö ÀÖ´Ù (¸¸ÀÏ À̰ͺ¸´Ù ´õ ±íÀÌ Å½»öÀ» ¼öÇàÇÏ°í ÀÖ¾ú´Ù¸é ÁÙ¾îµå´Â Ž»öÀÇ ¾çÀº ÈξÀ ´õ Ŭ ¼öµµ ÀÖ´Ù´Â °ÍÀ» ÁÖ¸ñÇ϶ó. ±×·± °æ¿ì¿¡´Â ³ëµå , , ÀÇ ¸ðµç Àڼյ鵵 »ý¼ºµÇÁö ¾ÊÀ» °ÍÀ̱⠶§¹®ÀÌ´Ù). ³ëµå , , ¸¦ »ý¼ºÇÏÁö ¾Ê¾Æµµ MAX ÀÇ ÃÖ»óÀÇ ÇൿÀÌ ¹«¾ùÀÌ µÇ´Â°¡¿¡ ÀüÇô ¿µÇâÀ» ÁÙ ¼ö ¾øÀ½À» ±ú´Ý´Â °ÍÀÌ Áß¿äÇÏ´Ù.
ÀÌ ¿¹¿¡¼­´Â ³ëµå °¡ MIN ÀÌ À̱â´Â »óŸ¦ ³ªÅ¸³»±â ¶§¹®¿¡ Ž»öÀ» ÁÙÀÏ ¼ö ÀÖ¾ú´Ù. ±×·¯³ª Ž»öÆ®¸®ÀÇ ¾î¶² ³ëµå MAX ³ª MIN ÀÌ À̱â´Â »óŸ¦ ³ªÅ¸³»Áö ¾Ê´Â °æ¿ì¿¡µµ °°Àº ¹æ½ÄÀ¸·Î Ž»öÀ» ÁÙÀÏ ¼ö ÀÖ´Ù.

 

±×¸² 6  Tic-Tac-Toe Ž»öÀÇ Ã¹ ¹ø° ´Ü°èÀÇ ÀϺÎ

¾Õ¼­ º¸ÀÎ Tic-Tac-Toe Ž»öÀÇ Ã¹ ¹ø° ´Ü°è¸¦ »ý°¢ÇØ º¸ÀÚ (±×¸² 3). ÀÌ Æ®¸®ÀÇ ÇÑ ºÎºÐÀ» ±×¸² 6 ¿¡ ´Ù½Ã ³ªÅ¸³»¾ú´Ù. Ž»öÀº ±íÀÌ¿ì¼± ÇüÅ·ΠÁøÇàµÇ°í, ´Ü¸» ³ëµå°¡ »ý¼ºµÇÀÚ¸¶ÀÚ Á¤Àû Æò°¡ ÇÔ¼ö°¡ °è»êµÈ´Ù°í °¡Á¤ÇÏÀÚ. ¶ÇÇÑ ¾î¶² ³ëµå°¡ Àü´Þ°ªÀ» ¹ÞÀ» ¼ö ÀÖ°Ô µÇÀÚ¸¶ÀÚ Àü´Þ°ªÀÌ ÁöÁ¤µÈ´Ù°í ÇÏÀÚ. ÀÌÁ¦ ±íÀÌ¿ì¼± Ž»ö¿¡¼­ ³ëµå ¿Í ÀÇ ¸ðµç ÀÚ½Ä ³ëµåµéÀÌ »ý¼ºµÈ Á÷ÈÄ, °¡ »ý¼ºµÇ±â Àü¿¡ ÀϾ´Â »óȲ¿¡ ´ëÇØ »ý°¢ÇØ º¸ÀÚ. ³ëµå ´Â ÇöÀç Àü´Þ°ªÀÌ -1 ÀÌ´Ù. ÀÌ ½ÃÁ¡¿¡¼­ ½ÃÀÛ ³ëµåÀÇ Àü´Þ°ªÀº -1 ÀÌ»óÀ¸·Î Á¦Çѵȴٴ °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. ´Ù¸¥ ÀÚ½Ä ³ëµåµé·ÎºÎÅÍ Àü´ÞµÇ´Â °ª¿¡ µû¶ó¼­ ½ÃÀÛ ³ëµåÀÇ ÃÖÁ¾ Àü´Þ°ªÀº -1 º¸´Ù ´õ Ŭ ¼ö´Â ÀÖÁö¸¸ ´õ ÀÛÀ» ¼ö´Â ¾ø´Â °ÍÀÌ´Ù. ÀÌ ÇÏÇÑÀ» ½ÃÀÛ ³ëµåÀÇ ¾ËÆÄ°ª (alpha value) À̶ó°í ÇÑ´Ù.
ÀÌÁ¦ ±íÀÌ¿ì¼± Ž»öÀÌ ³ëµå ±îÁö ÁøÇàÇÏ¿© ù ¹ø° ÀÚ½Ä ³ëµå °¡ »ý¼ºµÇ¾ú´Ù°í ÇÏÀÚ. ³ëµå ÀÇ Æò°¡°ªÀº -1 ÀÌ´Ù. ¿©±â¼­ ³ëµå ÀÇ Àü´Þ°ªÀº -1 ÀÌÇÏ·Î Á¦Çѵȴٴ °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. ³ª¸ÓÁö ÀÚ½Ä ³ëµåµéÀÇ Æò°¡°ª¿¡ µû¶ó¼­ ³ëµå ÀÇ ÃÖÁ¾ Àü´Þ°ªÀº -1 º¸´Ù ÀÛÀ» ¼ö´Â ÀÖÁö¸¸ ´õ Ŭ ¼ö´Â ¾ø´Ù. ³ëµå ¿¡ ´ëÇÑ ÀÌ·¯ÇÑ »óÇÑÀ» º£Å¸ °ª (beta value) À̶ó°í ÇÑ´Ù. ±×·¯¹Ç·Î ÀÌ ½ÃÁ¡¿¡¼­ ³ëµå ÀÇ ÃÖÁ¾ Àü´Þ°ªÀº ½ÃÀÛ ³ëµåÀÇ ¾ËÆÄ°ªÀ» ³ÑÀ» ¼ö ¾ø´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ°í, µû¶ó¼­ ³ëµå ¾Æ·¡·ÎÀÇ Å½»öÀ» Áß´ÜÇÒ ¼ö ÀÖ´Ù. ³ëµå °¡ ³ëµå º¸´Ù ¼±È£µÇ´Â ³ëµåÀÏ ¼ö´Â ¾ø´Â °ÍÀÌ´Ù.
ÀÌ·¯ÇÑ Å½»öÀÇ °¨¼Ò´Â Àü´Þ°ªÀÇ ÇѰ踦 ±â¾ïÇÔÀ¸·Î½á ÀÌ·ç¾îÁö´Â °ÍÀÌ´Ù. ÀϹÝÀûÀ¸·Î ¾î¶² ³ëµåÀÇ Àü´Þ°ªÀÇ ÇÑ°è´Â ÀÚ½Ä ³ëµåµéÀÇ Àü´Þ°ªÀÌ ÁöÁ¤µÇ¸é¼­ ¼öÁ¤µÉ ¼ö ÀÖ´Ù. ±×·¯³ª ´ÙÀ½ÀÇ »ç½ÇÀ» º¸ÀÚ.

ÀÌ·¯ÇÑ Á¦¾àÁ¶°Ç ¶§¹®¿¡, ´ÙÀ½°ú °°Àº ±ÔÄ¢¿¡ ÀÇÇÏ¿© Ž»öÀ» Áß´ÜÇÒ ¼ö ÀÖ´Ù.

Ž»öÀÌ ÁøÇàµÇ´Â µ¿¾È ¾ËÆÄ°ª°ú º£Å¸°ªÀº ´ÙÀ½°ú °°ÀÌ °è»êµÈ´Ù.

Ž»öÀÌ ±ÔÄ¢ 1 ¿¡ ÀÇÇØ Áß´ÜµÇ¸é ¾ËÆÄ Àý´Ü (alpha cut-off) ÀÌ ÀϾ´Ù°í ¸»ÇÑ´Ù. Ž»öÀÌ ±ÔÄ¢ 2 ¿¡ ÀÇÇØ Áß´ÜµÇ¸é º£Å¸ Àý´Ü (beta cut-off) ÀÌ ÀϾ´Ù°í ¸»ÇÑ´Ù. ¾ËÆÄ°ª°ú º£Å¸°ªÀ» ±â¾ïÇϸ鼭 Àý´ÜÀ» ¼öÇàÇØ °¡´Â ¸ðµç °úÁ¤À» ÀϹÝÀûÀ¸·Î ¾ËÆÄ º£Å¸ ¹æ¹ý (alpha-beta procedure) ¶ó°í ÇÑ´Ù. ÀÌ °úÁ¤Àº ½ÃÀÛ ³ëµåÀÇ ¸ðµç ÀÚ½Ä ³ëµåµéÀÌ ÃÖÁ¾ÀûÀÎ Àü´Þ°ªÀ» °®°Ô µÇ¸é Á¾·áÇϸç, ±×¸®°í ³ª¸é ÃÖ»óÀÇ ÇൿÀº °¡Àå ³ôÀº Àü´Þ°ªÀ» °®´Â ÀÚ½Ä ³ëµå¸¦ ¸¸µå´Â °ÍÀÌ µÈ´Ù. ÀÌ ¹æ¹ýÀ» Àû¿ëÇϸé Ç×»ó °°Àº ±íÀ̱îÁö ±âº»ÀûÀÎ ÃÖ´ëÃÖ¼Ò ¹æ¹ýÀ¸·Î Ž»öÀ» ¼öÇàÇßÀ» ¶§ ã¾ÆÁö´Â Çൿ°ú °°Àº ¼öÁØÀÇ ÇൿÀ» ã°Ô µÈ´Ù. À¯ÀÏÇÑ Â÷ÀÌ´Â ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» »ç¿ëÇϸé ÀϹÝÀûÀ¸·Î ÈξÀ ÀûÀº Ž»öÀ» ÇÏ°í ÃÖ»óÀÇ ÇൿÀ» ã´Â´Ù´Â °ÍÀÌ´Ù.
Áö±Ý±îÁö ¼³¸íÇÑ ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» °£°áÇÑ ÀÇ»çÄÚµå (pseudocode) ¿¡ ÀÇÇØ ±Í³³Àû ¾Ë°í¸®ÁòÀ¸·Î ³ªÅ¸³¾ ¼ö ÀÖ´Ù. ¾Æ·¡¿¡ ÀÖ´Â Àý´Ü°ª ¹× ¿Í °ü·ÃÇÏ¿© ³ëµå ÀÇ ÃÖ´ëÃÖ¼Ò°ªÀ» °è»êÇÏ´Â ¾Ë°í¸®ÁòÀº [Pearl 1984, p.234] ¿¡¼­ °¡Á®¿Â °ÍÀÌ´Ù.

 

    1. ÀÌ ±íÀÌ ÇÑ°è¿¡ ÀÖÀ¸¸é ÀÇ Á¤Àû Æò°¡°ªÀ» ¹ÝȯÇÑ´Ù. ±×·¸Áö ¾ÊÀ¸¸é ¸¦  ÀÇ (¼ø¼­ ÀÖ´Â) ÀÚ½Ä ³ëµåµéÀ̶ó°í ÇÏ°í, ·Î ÇÑ´Ù. ÀÌ MAX ³ëµåÀÌ¸é ´Ü°è 2 ·Î °¡°í, ¾Æ´Ï¸é ´Ü°è 2' ·Î °°´Ù.

    2. .

    3. ÀÌ¸é ¸¦ ¹Ýȯ ; ¾Æ´Ï¸é °è¼Ó.

    4. ÀÌ¸é ¸¦ ¹Ýȯ ; ¾Æ´Ï¸é ·Î ÁøÇà. Áï ·Î ÇÏ°í ´Ü°è 2 ·Î °¨.

    2'.

    3'. ÀÌ¸é ¸¦ ¹Ýȯ ; ¾Æ´Ï¸é °è¼Ó.

    4'. ÀÌ¸é ¸¦ ¹Ýȯ ; ¾Æ´Ï¸é ·Î ÁøÇà. Áï ·Î ÇÏ°í ´Ü°è 2' ·Î °¨.

¾ËÆÄ º£Å¸ Ž»öÀº °¡ ½ÃÀÛ ³ëµåÀÏ ¶§, ¸¦ È£ÃâÇÏ¿© ½ÃÀÛÇÑ´Ù. ¾Ë°í¸®ÁòÀÌ ÁøÇàµÇ´Â µ¿¾È ÀÌ´Ù. ´Ü°è 1¿¡¼­ ³ëµåÀÇ ¼ø¼­´Â, ¾ÕÀ¸·Î º¸°ÚÁö¸¸, È¿À²¿¡ Áß¿äÇÑ ¿µÇâÀ» ¹ÌÄ£´Ù.

 

±×¸² 7  ¾ËÆÄ º£Å¸ Ž»öÀÇ ¿¹

¾ËÆÄ º£Å¸ ¹æ¹ýÀÇ ÀÀ¿ë ¿¹¸¦ ±×¸² 7 ¿¡ ³ªÅ¸³»¾ú´Ù. ¿©±â¿¡´Â ±íÀÌ 6 ±îÁöÀÇ Å½»öÆ®¸®°¡ ³ª¿Í ÀÖ´Ù. MAX ³ëµå´Â ³×¸ð·Î ±×·ÁÁ® ÀÖ°í, MAX ³ëµå´Â µ¿±×¶ó¹Ì·Î ±×·ÁÁ® ÀÖ´Ù. ´Ü¸» ³ëµå¿¡´Â Æò°¡°ªÀÌ ¾²¿© ÀÖ´Ù. ÀÌÁ¦ ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ½á¼­ ±íÀÌ ¿ì¼± Ž»öÀ» ¼öÇàÇÑ´Ù°í ÇÏÀÚ (¿©±â¼­´Â ¹Ù´Ú ÂÊÀÇ ³ëµå°¡ ¸ÕÀú »ý¼ºµÇ´Â °ÍÀ¸·Î ÇÏ¿´´Ù). ¾ËÆÄ º£Å¸ ¹æ¹ý¿¡ ÀÇÇØ »ý¼ºµÇ´Â ºÎºÐÆ®¸®°¡ ÁøÇÏ°Ô ³ªÅ¸³ª ÀÖ´Ù. Àý´ÜµÇ´Â ³ëµåµé¿¡´Â X °¡ ±×·ÁÁ® ÀÖ´Ù. ¿ø·¡ÀÇ 41 °³ ´Ü¸» ³ëµå Áß¿¡¼­ 18 °³¸¸ Æò°¡ÇÏ¸é µÈ´Ù (ÀÌ ¿¹¿¡ ´ëÇÑ ¾ËÆÄ º£Å¸ Ž»öÀ» µû¶óÇØ º¸¸é ÀÌ ¹æ¹ýÀ» Àß ÀÌÇØÇß´ÂÁö ½ÃÇèÇØ º¼ ¼ö ÀÖÀ» °ÍÀÌ´Ù).

¾ËÆÄ º£Å¸ ¹æ¹ýÀÇ Å½»ö È¿À²

¾ËÆÄ ¹× º£Å¸°ªÀº ´Ü¸» (leaf) ³ëµåÀÇ Á¤Àû Æò°¡°ªÀ» ±â¹ÝÀ¸·Î ÇÏ´Â °ÍÀ̱⠶§¹®¿¡, ¾ËÆÄ ¹× º£Å¸ Àý´ÜÀ» ¼öÇàÇϱâ À§Çؼ­´Â ÃÖ¼ÒÇÑ Æ®¸®ÀÇ ÇÑ ºÎºÐÀÌ ÃÖ´ë ±íÀ̱îÁö »ý¼ºµÇ¾î¾ß¸¸ ÇÑ´Ù. µû¶ó¼­ ÀϹÝÀûÀ¸·Î ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ÀÌ¿ëÇÏ´Â µ¥´Â ±íÀÌ¿ì¼± ÇüÅÂÀÇ Å½»öÀÌ »ç¿ëµÈ´Ù. ¶ÇÇÑ Å½»öÀÌ ÁøÇàµÇ´Â µ¿¾È ÀÌ·ç¾îÁö´Â Àý´ÜÀÇ ¼ö´Â ÃʱâÀÇ ¾ËÆÄ ¹× º£Å¸°ªÀÌ ÃÖÁ¾ÀûÀÎ Àü´Þ°ªÀ» ¾ó¸¶³ª °¡±õ°Ô ÃßÁ¤Çϴ°¡¿¡ ´Þ·ÁÀÖ´Ù.
Æ®¸®ÀÇ ±íÀÌ°¡ ÀÌ°í ¸ðµç ³ëµå (´Ü¸» ³ëµå¸¦ Á¦¿ÜÇÑ) °¡ Á¤È®È÷ °³ÀÇ ÀÚ½Ä ³ëµå¸¦ °¡Áö°í ÀÖ´Ù°í ÇÏÀÚ. ÀÌ·± Æ®¸®¿¡´Â Á¤È®È÷ °³ÀÇ ´Ü¸» ³ëµå°¡ ÀÖÀ» °ÍÀÌ´Ù. ¾ËÆÄ º£Å¸ Ž»öÀÌ ÀÚ½Ä ³ëµå, ±×¸®°í MAX ³ëµå¿¡¼­´Â ³ôÀº °ªÀ» °®´Â ÀÚ½Ä ³ëµå, ±×¸®°í MAX ³ëµå¿¡¼­´Â ³ôÀº °ªÀ» °®´Â ÀÚ½Ä ³ëµåÀÇ ¼øÀ¸·Î »ý¼ºÇÑ´Ù°í Çغ¸ÀÚ (¹°·Ð ÀÚ½Ä ³ëµåµéÀ» »ý¼ºÇÒ ¶§´Â º¸Åë ÀÌ Àü´Þ°ªµéÀ» ¾Ë ¼ö ¾øÀ¸¹Ç·Î, ÀÌ·¯ÇÑ ¼ø¼­´Â ¿ì¿¬ÀÌ ¾Æ´Ï°í´Â ½ÇÁ¦·Î ÁöÄÑÁú ¼ö ¾ø´Ù).
ÀÌ·¯ÇÑ ¼ø¼­°¡ Àý´ÜÀÇ ¼ö¸¦ ÃÖ´ëÈ­ÇÏ°í, »ý¼ºµÇ´Â ´Ü¸» ³ëµåÀÇ ¼ö¸¦ ÃÖ¼ÒÈ­ÇÏ°Ô µÈ´Ù. ÀÌ·¯ÇÑ ÃÖ¼ÒÀÇ ´Ü¸» ³ëµå ¼ö¸¦ ¶ó°í ÇÏÀÚ. ±×·¯¸é ´ÙÀ½À» Áõ¸íÇÒ ¼ö ÀÖ´Ù [Slagle & Dixon 1969, Knuth & Moore 1975].

Áï, ÃÖÀûÀÇ ¾ËÆÄ º£Å¸ Ž»ö¿¡ ÀÇÇØ »ý¼ºµÇ´Â ±íÀÌ ÀÇ ´Ü¸» ³ëµå ¼ö´Â ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ¾²Áö ¾Ê¾ÒÀ» ¶§ ±íÀÌ ¿¡¼­ »ý¼ºµÇ´Â ´Ü¸» ³ëµå ¼ö¿Í °ÅÀÇ °°´Ù´Â °ÍÀÌ´Ù. µû¶ó¼­ ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ¾²Áö ¾Ê´Â Ž»öÀÌ ±íÀÌ ¿¡¼­ ÁߴܵǴ ½Ã°£¿¡ ¾ËÆÄ º£Å¸ Ž»öÀº (¿Ïº®ÇÑ ¼ø¼­¿¡ µû¶úÀ» ¶§) ±íÀÌ ±îÁö ÁøÇàÇÒ ¼ö ÀÖ´Ù. ´Ù½Ã ¸»Çϸé, ¿Ïº®ÇÑ ¼ø¼­¿¡ ÀÇÇÑ ¾ËÆÄ º£Å¸ Ž»öÀº ½ÇÁúÀûÀÎ ºÐ±â °è¼ö¸¦ ¿¡¼­ ´ë·« ·Î °¨¼Ò½ÃŲ´Ù.
¹°·Ð ¿Ïº®ÇÑ ³ëµå »ý¼º ¼ø¼­´Â ÀÌ·ê ¼ö ¾ø´Ù (¸¸ÀÏ ÀÌ·ê ¼ö ÀÖ´Ù¸é, Ž»öÀÌ ÀüÇô ÇÊ¿äÄ¡ ¾ÊÀ» °ÍÀÌ´Ù). ÃÖ¾ÇÀÇ °æ¿ì¿¡´Â ¾ËÆÄ º£Å¸ Ž»öÀÌ ÀüÇô Àý´ÜÀ» ¼öÇàÇÏÁö ¸øÇÏ°í, µû¶ó¼­ ½ÇÁúÀûÀÎ ºÐ±â °è¼ö´Â º¯ÇÔÀÌ ¾ø°Ô µÈ´Ù. Pearl Àº ¸¸ÀÏ ÀÚ½Ä ³ëµåµéÀÌ ÀÓÀÇÀÇ ¼ø¼­·Î »ý¼ºµÈ´Ù¸é, ¾ËÆÄ º£Å¸ Ž»öÀ» ¼öÇàÇÔÀ¸·Î½á Ž»ö ±íÀÌ°¡ ´ë·« 4/3 ¸¸Å­ Áõ°¡ÇÑ´Ù´Â °ÍÀ» Áõ¸íÇÏ¿´´Ù. Áï, Æò±Õ ºÐ±â °è¼ö°¡ ¾à
4  À¸·Î °¨¼ÒÇÑ´Ù´Â °ÍÀÌ´Ù [Pearl 1982b] (¿ÏÀüÇÑ ºÐ¼®Àº [Pearl 1984, 9Àå]À» º¸¶ó). ½ÇÁ¦·Î ÀÚ½Ä ³ëµåµéÀÇ ¼ø¼­¸¦ Á¤ÇÏ´Â µ¥ ÁÁÀº ÈÞ¸®½ºÆ½À» ¾²¸é ¾ËÆÄ º£Å¸ ¹æ¹ýÀº ÀϹÝÀûÀ¸·Î °ÅÀÇ ÃÖÀû¿¡ °¡±õ°Ô ½ÇÁúÀûÀÎ ºÐ±â °è¼ö¸¦ °¨¼Ò½Ãų ¼ö ÀÖ´Ù.
ÀÚ½Ä ³ëµåµéÀÇ ¼ø¼­¸¦ Á¤ÇÏ´Â °¡Àå °£´ÜÇÑ ¹æ¹ýÀº Á¤Àû Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇÏ´Â °ÍÀÌ´Ù. ¶Ç ´Ù¸¥ ³ëµå Á¤·Ä ±â¹ýÀº ¹Ýº¹Àû ±íÀÌÁõ°¡ (iterative deepening) ¹æ¹ýÀ» »ç¿ëÇϸ鼭 ºÎ»ê¹°·Î ³ªÅ¸³­ °ÍÀ¸·Î½á, ü½º ÇÁ·Î±×·¥ÀÎ CHESS 4.5 ¿¡ óÀ½ »ç¿ëµÇ¾ú´Ù [Slate & Atkin 1977].  ÀÌ ÇÁ·Î±×·¥Àº óÀ½¿¡ ÇÑ °ãÀÇ ±íÀÌ ÇÑ°è±îÁö Ž»öÀ» ¼öÇàÇÏ¿© ÃÖ»óÀÇ ÇൿÀ» °è»êÇÏ´Â ½ÄÀ¸·Î µ¿ÀÛÇÏ¿´´Ù. ÀÌ·¯ÇÑ Áߺ¹ÀÇ, ±×¸®°í ³¶ºñÀÎ µíÇÑ Å½»öÀ» ¼öÇàÇÑ ÁÖµÈ ÀÌÀ¯´Â °ÔÀÓ ÇÁ·Î±×·¥¿¡ ´ëºÎºÐ ½Ã°£ Á¦ÇÑÀÌ Àֱ⠶§¹®ÀÌ´Ù. ½Ã°£ÀÌ ¾ó¸¶³ª Àִ°¡¿¡ µû¶ó ´õ ±íÀº °÷±îÁöÀÇ Å½»öÀº ¾ðÁ¦µçÁö Áß´ÜµÉ ¼ö ÀÖ°í, ¹Ù·Î ÀÌÀüÀÇ Å½»ö¿¡¼­ °¡Àå ÁÁ´Ù°í ÆÇ´ÜµÈ ÇൿÀ» ÃëÇÒ ¼ö ÀÖ´Ù. °ã±îÁöÀÇ Å½»ö¿¡¼­ ÃÖ»óÀ̶ó°í ÆÇ´ÜµÈ ÀÚ½Ä ³ëµåµéÀ» °ã±îÁöÀÇ Å½»ö¿¡¼­ ³ëµåÀÇ ¼ø¼­¸¦ Á¤ÇÏ´Â µ¥ »ç¿ëÇÒ ¼ö Àֱ⠶§¹®¿¡ ³ëµåÀÇ Á¤·ÄÀÌ ÀÌ ¹æ¹ýÀÇ ºÎ»ê¹°·Î ¾ò¾îÁö´Â °ÍÀÌ´Ù.

±âŸ Áß¿äÇÑ »çÇ×µé

´ëºÎºÐÀÇ °ÔÀÓ¿¡¼­´Â °ÔÀÓÀÌ ³¡³ª´Â »óȲ ÀÌÀü¿¡ Ž»öÀ» Áß´ÜÇØ¾ß Çϱ⠶§¹®¿¡ (½Ã°è Á¦ÇÑ) ¿©·¯ °¡Áö ¾î·Á¿î ¹®Á¦µéÀÌ ¾ß±âµÈ´Ù. ÀÌ·± ¹®Á¦ ÁßÀÇ Çϳª´Â, Ž»öÀÌ MAX (¶Ç´Â MIN) °¡ ¾ÆÁÖ ÁÁÀº ÇൿÀ» ÇÒ ¼ö ÀÖ´Â »óÅ¿¡¼­ Áß´ÜµÉ ¼öµµ ÀÖ´Ù´Â °ÍÀÌ´Ù. ÀÌ ¶§¹®¿¡ ´ëºÎºÐÀÇ °ÔÀÓ Å½»ö ÇÁ·Î±×·¥Àº ¾î¶² »óÅ¿¡¼­ °í¿äÇÏ´Ù´Â °ÍÀº ±× »óÅ°¡ °í¿äÇÑ (quiescent) °ÍÀÎÁö¸¦ È®ÀÎÇÑ´Ù. ¾î¶² »óÅ°¡ °í¿äÇÏ´Ù´Â °ÍÀº ±× »óÅÂÀÇ Á¤Àû Æò°¡°ªÀÌ Çϳª ȤÀº µÎ °³ ¾ÕÀÇ ÇൿÀ» ³»´Ùº¸¾ÒÀ» ¶§ÀÇ Àü´Þ°ª°ú Å« Â÷ÀÌ°¡ ¾ø´Ù´Â °ÍÀ» ¸»ÇÑ´Ù.

Ž»öÀ» Á¾·áÇϱâ Àü¿¡ °í¿äÇÔÀ» È®ÀÎÇÏ´õ¶óµµ, Ž»öÀÇ ½Ã°è (horizon) ¹Ù·Î ÀúÆí¿¡ ¾ÆÁÖ ¾È ÁÁÀº »óȲÀ̳ª ȤÀº ÀÌ±æ ¼ö ÀÖ´Â »óȲÀÌ ¼û¾î ÀÖ´Â °æ¿ì°¡ ÀÖ´Ù. ¾î¶² °ÔÀÓ¿¡¼­´Â MIN ÀÌ ¾î¶² ÇൿÀ» ÃëÇÏ´õ¶óµµ MAX °¡ À̱â´Â ±æ·Î °¥ ¼ö¹Û¿¡ ¾ø´Â »óȲÀÌ Àִµ¥, ÀÌ °æ¿ì MIN ÀÌ MAX °¡ À̱â´Â »óŸ¦ Ž»ö ½Ã°è ¹ÛÀ¸·Î ¹Ð¾î³»µµ·Ï °í¿äÇÔÀ» À¯ÁöÇϸç ÇÇÇØ ´Ù´Ï´Â ÇൿÀ» ÇÒ ¼öµµ ÀÖ´Ù. ÀÌ ½Ã°èÈ¿°ú (horizon-effect) ¶ó°í ÇÏ´Â »óȲÀº °ÔÀÓ ÇÁ·Î±×·¥µéÀÌ °¡Áö°í ÀÖ´Â ±Ùº»ÀûÀÎ ¹®Á¦ ÁßÀÇ ÇϳªÀÌ´Ù.

ÃÖ´ëÃÖ¼Ò ¹æ¹ý°ú ±×°ÍÀÇ È®ÀåÀÎ ¾ËÆÄ º£Å¸ ¹æ¹ýÀº »ó´ë¹æÀÌ ¾ðÁ¦³ª Àڽſ¡°Ô ÃÖ»óÀÇ ÇൿÀ» ¼±ÅÃÇÑ´Ù°í °¡Á¤ÇÏ°í ÀÖ´Ù. ÀÌ·¯ÇÑ °¡Á¤ÀÌ ÀûÀýÇÏÁö ¸øÇÒ ¶§µµ ÀÖ´Ù. ¿¹¸¦ µé¾î, MIN ÀÌ ÃÖÀûÀÇ ÇൿÀ» Çϸé MAX °¡ Áú °Í °°Àº »óȲ¿¡ ÀÖ´Ù°í ÇÏÀÚ. ±×·¡µµ, MIN ÀÌ ½Ç¼ö¸¦ Çϱ⸸ ÇÑ´Ù¸é MAX °¡ ÀÌ·± »óȲ¿¡¼­ ºüÁ® ³ª¿Ã ¼ö ÀÖµµ·Ï ÇØÁÖ´Â ÇൿÀÌ ÀÖÀ» °ÍÀÌ´Ù. ÃÖ´ëÃÖ¼Ò Å½»öÀº MIN ÀÌ ½Ç¼ö¸¦ ÇҰŶó°í µµ¹ÚÀ» °Å´Â µ¥ Ãß°¡ÀûÀÎ ÇൿÀÌ ÀÖÀ» °ÍÀÌ´Ù. ÃÖ´ëÃÖ¼Ò Å½»öÀº MIN ÀÌ ½Ç¼ö¸¦ ÇҰŶó°í µµ¹ÚÀ» °Å´Â µ¥ Ãß°¡ÀûÀÎ À§ÇèÀÌ °ÅÀÇ ¾ø´õ¶óµµ ±×·¯ÇÑ ÇൿÀ» ÃßõÇÏÁö´Â ¸øÇÑ´Ù (¾î´À °æ¿ì¿¡µµ Áú °ÍÀ̹ǷÎ). ÃÖ´ëÃÖ¼Ò ¹æ¹ýÀº ¶ÇÇÑ ÇÑÂÊÀÌ »ó´ë¹æÀÇ Àü·«¿¡ ´ëÇÑ ¾î¶² ¸ðµ¨ÀÌ ÀÖ´Â °æ¿ì¿¡µµ ºÎÀûÀýÇÏ´Ù.

È®·ü °ÔÀÓ

Backgammon °ú °°Àº °ÔÀÓ¿¡´Â È®·üÀû ¿ä¼Ò°¡ Æ÷ÇԵǾî ÀÖ´Ù. ¿¹¸¦ µé¾î ÁÖ»çÀ§¸¦ ´øÁ³À» ¶§ÀÇ °á°ú¿¡ µû¶ó ÃëÇÒ ¼ö ÀÖ´Â ÇൿÀÌ ´Þ¶óÁú ¼ö ÀÖ´Ù. ÀÌ·± Á¾·ùÀÇ °ÔÀÓÀÇ ÇÑ ¿¹¿¡ ´ëÇÑ °ÔÀÓÆ®¸®¸¦ ±×¸² 8 ¿¡ ³ªÅ¸³»¾ú´Ù (Æ®¸®¸¦ ´Ü¼øÈ­Çϱâ À§ÇÏ¿© ÇϳªÀÇ ÁÖ»çÀ§¸¦ ´øÁ³À» ¶§ ³ª¿À´Â 6 °³ÀÇ ¼­·Î ´Ù¸¥ °á°ú¸¸À» ³ªÅ¸³»¾ú´Ù). MAX ¿Í MIN ÀÇ Â÷·Ê¿¡´Â ÀÌÁ¦ ÁÖ»çÀ§¸¦ ´øÁö´Â °ÍÀÌ Æ÷ÇԵȴÙ. ÁÖ»çÀ§¸¦ ´øÁú ¶§¸¶´Ù °¡»óÀÇ ¼¼ ¹ø° Ç÷¹À̾î DICE °¡ ÇൿÀ» ÃëÇÑ´Ù°í »ý°¢ÇÒ ¼ö ÀÖ´Ù. ÀÌ ÇൿÀ» È®·üÀûÀ¸·Î °áÁ¤µÈ´Ù. ÇϳªÀÇ ÁÖ»çÀ§¸¦ ´øÁö´Â °æ¿ì¿¡´Â 6 °³ÀÇ °á°ú°¡ ¸ðµÎ °°Àº È®·üÀ» °®°í ÀÖÁö¸¸, È®·ü¿ä¼Ò´Â ÀÓÀÇÀÇ È®·ü ºÐÆ÷¸¦ °¡Áú ¼öµµ ÀÖ´Ù.

È®·üÀû ÇൿÀÌ Æ÷ÇÔµÈ °ÔÀÓÆ®¸®¿¡¼­µµ °ªÀº Àü´ÞµÉ ¼ö ÀÖÀ¸³ª, È®·üÀû ÇൿÀÌ ÀÖ´Â ³ëµå·Î °ªÀ» Àü´ÞÇÒ ¶§´Â Ãִ볪 ÃÖ¼Ò°ª ´ë½Å¿¡ ÀÚ½Ä ³ëµåÀÇ ±â´ë°ª (expected value)À» Àü´ÞÇÒ ¼ö ÀÖ´Ù. ±×¸² 8¿¡¼­ °¢ ³ëµåÀÇ ¿·¿¡ ÀÖ´Â ¼ýÀÚ´Â Àü´Þ°ªÀÇ ÃßÁ¤Ä¡ÀÌ´Ù. MIN ÀÇ Â÷·Ê¿¡ ÇØ´çÇÏ´Â ³ëµåÀÇ ÀÚ½Ä ³ëµå·ÎºÎÅÍ´Â ÃÖ¼Ò°ªÀ», MAX ÀÇ Â÷·Ê¿¡ ÇØ´çÇÏ´Â ³ëµåÀÇ ÀÚ½Ä ³ëµå·ÎºÎÅÍ´Â ÃÖ´ë°ªÀ», ±×¸®°í DICE ÀÇ Â÷·Ê¿¡ ÇØ´çÇÏ´Â ³ëµåÀÇ ÀÚ½Ä ³ëµå·ÎºÎÅÍ´Â ±â´ë°ªÀ» Àü´ÞÇÑ´Ù. ÀÌ·¯ÇÑ ¼öÁ¤µÈ Àü´Þ ¹æ¹ýÀ» ±â´ë°ª ÃÖ´ëÈ­ (expectimaxing) ¶ó°íµµ ÇÑ´Ù.

 

±×¸² 8  ÁÖ»çÀ§ ´øÁö±â°¡ Æ÷ÇÔµÈ °ÔÀÓÀÇ °ÔÀÓÆ®¸®

È®·üÀû ÇൿÀ» µµÀÔÇÏ¸é ´ë°³ °ÔÀÓÆ®¸®ÀÇ ºÐ±â°¡ È¿°úÀûÀΠŽ»öÀ» Çϱ⿡ ³Ê¹« ¸¹¾ÆÁø´Ù. ÀÌ·¯ÇÑ °æ¿ì¿¡´Â ÁÁÀº Á¤Àû Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇÏ¿© Ž»öÀÌ ³Ê¹« ±íÀÌ ÁøÇàÇÏÁö ¾Êµµ·Ï ÇÏ´Â °ÍÀÌ ¸Å¿ì Áß¿äÇÏ´Ù. ¸¸ÀÏ ÃæºÐÈ÷ ÁÁÀº Á¤Àû Æò°¡ ÇÔ¼ö°¡ ÀÖ´Ù¸é, MAX ÀÇ Çൿ ¼±Åà Á¤Ã¥Àº ÇÑ ´Ü°è ¾ÕÀÇ »óŸ¸À» º¸°í À̵éÀÇ Á¤Àû Æò°¡ ÇÔ¼ö°ªÀÌ ÃÖ´ë°¡ µÇ´Â Çൿ ÃëÇÏ´Â °ÍÀÏ ¼ö ÀÖ´Ù. ´ÙÀ½ Àå¿¡¼­´Â Çൿ Á¤Ã¥À» ÇнÀÇÏ´Â ¹æ¹ý°ú ºÐ±â °è¼ö°¡ ³Ê¹« Ä¿¼­ Ž»öÇÒ ¼ö ¾ø´Â °ÔÀÓÀÇ Á¤Àû Æò°¡ ÇÔ¼ö¸¦ ÇнÀÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ À̾߱âÇÏ°Ú´Ù.

Æò°¡ ÇÔ¼öÀÇ ÇнÀ

¹ÙµÏ°ú °°Àº °ÔÀÓÀº °¢ ´Ü°è¿¡¼­ ³Ê¹« ¸¹Àº ÇൿÀÌ °¡´ÉÇϱ⠶§¹®¿¡ ±íÀº Ž»öÀÌ °¡´ÉÇÏÁö ¾ÊÀº °ÍÀ¸·Î »ý°¢µÈ´Ù. Ž»öÀ» ÇÏÁö ¾ÊÀ¸¸é, ÀÚ½Ä ³ëµå¿¡ ´ëÇÑ Á¤Àû Æò°¡ °ª¸¸À» ±â¹ÝÀ¸·Î Çϰųª, ´Ù¾çÇÑ ÆÐÅÏÀÎ½Ä ±â¹ýÀ» ÀÌ¿ëÇØ ÇöÀçÀÇ »óÅ¿¡ ¹ÝÀÀÇÏ´Â ¹æ¹ýÀ¸·Î ÃÖ»óÀÇ ÇൿÀ» ¼±ÅÃÇؾ߸¸ ÇÑ´Ù. ¿¹¸¦ µé¾î ¹ÙµÏ¿¡¼­´Â ÇöÀçÀÇ »óȲÀ» Æò°¡ÇÏ´Â ¹æ¹ý°ú »óȲ¿¡ ¹ÝÀÀÀûÀ¸·Î ´ëóÇÏ´Â ¹æ¹ý¿¡ ´ëÇÑ ¿¬±¸°¡ ÁÖ·Î ÀÌ·ç¾îÁ³´Ù [Zobrist 1970, Reitman & Wilcox 1979, Kierulf, Chen, & Nievergelt 1990]. ¾î¶² °æ¿ì¿¡´Â ÁÁÀº Á¤Àû Æò°¡ ÇÔ¼ö¸¦ ½Å°æ¸ÁÀ» ÀÌ¿ëÇÏ¿© ÇнÀÇÒ ¼öµµ ÀÖ´Ù. TD-GAMMON [Tesauro 1992, Tesauro 1995] À̶ó´Â ÇÁ·Î±×·¥Àº ´ÙÃþ (layered) ÇǵåÆ÷¿öµå (feedforward) ½Å°æ¸ÁÀ» ÈÆ·ÃÇÏ¿© BackgammonÀ» ÇÏ´Â ¹æ¹ýÀ» ÇнÀÇÑ´Ù. ½Å°æ¸ÁÀÇ ±¸Á¶´Â ±×¸² 9 ¿Í °°´Ù. 198 °³ÀÇ ÀÔ·Â À¯´Ö (Backgammon ÀÇ ÇöÀç »óȲÀ» Ç¥ÇöÇÔ) ÀÌ Àº´Ð À¯´Öµé¿¡ ¿ÏÀü ¿¬°áµÇ¾î ÀÖ°í, Àº´Ð À¯´ÖµéÀº ´Ù½Ã Ãâ·Â À¯´Öµé¿¡ ¿ÏÀü ¿¬°áµÇ¾î ÀÖ´Ù. Àº´Ð À¯´Ö°ú Ãâ·Â Ãâ·ÂÀº ¸ðµÎ ½Ã±×¸ðÀ̵å (sigmoid) ÀÌ´Ù. Ãâ·Â À¯´ÖµéÀº ÁÖ¾îÁø ÀÔ·Â »óȲÀ¸·ÎºÎÅÍ ¿©·¯ °¡Áö °¡´ÉÇÑ °á°úµéÀÇ È®·ü¿¡ ´ëÇÑ ÃßÁ¤°ª , , , ¸¦ »êÃâÇϵµ·Ï µÇ¾î ÀÖ´Ù. ¾î¶² »óȲ¿¡ ´ëÇÑ ÀüüÀûÀÎ °¡Ä¡´Â ÃßÁ¤µÈ º¸»ó°ª (payoff), ·Î ÁÖ¾îÁø´Ù. ÀÌ ½Å°æ¸ÁÀ» ÀÌ¿ëÇÏ¿© Backgammon À» Çϸé, ¿ì¼± ÁÖ»çÀ§°¡ ´øÁ®Áö°í, ÇöÀçÀÇ »óȲ°ú ÁÖ»çÀ§ÀÇ °ªÀ¸·ÎºÎÅÍ °¡´ÉÇÑ ¸ðµç »óȲµéÀÌ ½Å°æ¸Á¿¡ ÀÇÇØ Æò°¡µÈ´Ù. °¡Àå ÁÁÀº °ªÀ» °®´Â »óȲÀÌ ¼±Åõǰí, ±× »óȲÀ» ¸¸µå´Â ÇൿÀ» ¼öÇàÇÏ°Ô µÈ´Ù (¹éÀÇ Â÷·Ê¶ó¸é °ªÀÌ ³ôÀ»¼ö·Ï ÁÁÀº °ÍÀÌ°í, ÈæÀÇ Â÷·Ê¶ó¸é °ªÀÌ ³·À»¼ö·Ï ÁÁÀº °ÍÀÌ´Ù).
½Å°æ¸ÁÀÇ ½Ã°£ Â÷ÀÌ (temporal difference) ÈÆ·ÃÀº ½Å°æ¸ÁÀÌ ÀÚ±â ÀڽŰú ½ÃÇÕÀ» Çϸ鼭 ÀÌ·ç¾îÁø´Ù. ÇϳªÀÇ ÇൿÀ» ÇÏ°í ³ª¸é, ¿ªÀüÆÄ (backpropagation) ¿¡ ÀÇÇÏ¿©, ¿ø·¡ »óȲ¿¡¼­ ÃßÁ¤µÈ º¸»ó°ªÀÌ °á°ú »óȲ¿¡¼­ÀÇ ½ÇÁ¦ º¸»ó°ª¿¡ Á¢±ÙÇϵµ·Ï ½Å°æ¸ÁÀÇ °¡ÁßÄ¡µéÀÌ Á¶Á¤µÈ´Ù. ½±°Ô ¼³¸íÇϱâ À§ÇØ ÀÌ ¹æ¹ýÀÌ ¼ø¼öÇÑ ½Ã°£ Â÷ÀÌ ÇнÀÀ» ÇÏ´Â °ÍÀ¸·Î ÇÏ°Ú´Ù (½ÇÁ¦·Î´Â ¾à°£ ´Ù¸£Áö¸¸, ¿©±â¼­ ±× ºÎºÐÀº Áß¿äÇÏÁö ¾Ê´Ù). °¡ ½Ã°£ ¿¡¼­ÀÇ º¸»ó°ª¿¡ ´ëÇÑ ÃßÁ¤Ä¡ÀÌ°í, ÀÌ ½Ã°£ ¿¡¼­ÀÇ ÃßÁ¤Ä¡¶ó¸é, ÀüÇüÀûÀÎ ½Ã°£ Â÷ÀÌ °¡ÁßÄ¡ Á¶Á¤ ±ÔÄ¢Àº ´ÙÀ½°ú °°´Ù.

´Â ½Ã°£ ¿¡¼­ÀÇ ½Å°æ¸ÁÀÇ ¸ðµç °¡ÁßÄ¡¿¡ ´ëÇÑ º¤ÅÍÀÌ°í, ´Â °¡ÁßÄ¡ °ø°£¿¡¼­ ÀÇ ±â¿ï±â (gradient) ÀÌ´Ù (TD-GAMMON °ú °°Àº ´ÙÃþ ÇǵåÆ÷¿öµå ½Å°æ¸Á¿¡¼­ °¢ ÃþÀÇ °¡ÁßÄ¡ º¤ÅÍÀÇ º¯È­´Â ½Å°æ¸Á¿¡¼­ ±â¼úÇÑ °Í°ú °°Àº ½ÄÀ¸·Î ³ªÅ¸³¾ ¼ö ÀÖ´Ù). ½Å°æ¸ÁÀº ¸ðµç ¿¡ ´ëÇÏ¿© ÇൿÀÌ ÃëÇØÁö±â ÀüÀÇ ÀԷ¿¡ ´ëÇÑ Ãâ·Â °¡ ÇൿÀÌ ÃëÇØÁø ÈÄÀÇ ÀԷ¿¡ ´ëÇÑ Ãâ·Â ¿¡ °¡±î¿öÁöµµ·Ï (°ª ¹Ýº¹¿¡¼­Ã³·³) ÈƷõȴÙ. ÀÌ·¯ÇÑ ÈÆ·Ã ¹æ¹ý¿¡ ´ëÇÑ ½ÇÇèÀÌ ½Å°æ¸ÁÀÌ ÀÚ±â ÀڽŰú ¼ö½Ê¸¸ ¹øÀÇ ½ÃÇÕÀ» Çϵµ·Ï ÇÔÀ¸·Î½á ¼öÇàµÇ¾ú´Ù (ÈƷðúÁ¤¿¡¼­ ¾à 50 ¸¸ ¹øÀÇ °ÔÀÓÀ» ¼öÇàÇÏ¿´´Ù).
Àß ÈÆ·ÃµÈ ½Å°æ¸ÁÀÇ ¼º´ÉÀº °ÅÀÇ Ã¨ÇǾð ¼öÁØÀÌ´Ù. ¾ÕÀ» ³»´Ùº¸´Â Ž»öÀ» ¾à°£ »ç¿ëÇÑ ÇÁ·Î±×·¥°úÀÇ 40 ¹øÀÇ °ÔÀÓ °á°ú¸¦ ±âÃÊ·Î ÇÏ¿©, Bill Robertie (Àü Backgammon ¼¼°è èÇǾð) ´Â TD-GAMMON 2.1 ÀÇ ¼öÁØÀÌ ¼¼°è ÃÖ°í ¼±¼ö¿Í °ÅÀÇ °°Àº Á¤µµÀÎ strong master ¼öÁØÀ̶ó°í ÃßÁ¤ÇÏ¿´´Ù [Tesauro 1995].

Âü°í¹®Çå ¹× Åä·Ð

ÆÛÁñó·³ °ÔÀӵ鵵 AI ±â¹ýµéÀ» ´Ùµë°í ½ÃÇèÇÏ´Â µ¥ ¸Å¿ì Áß¿äÇÑ ¿ªÇÒÀ» ÇØ¿Ô´Ù. ¿¹¸¦ µé¾î [Russell & Wefald 1991 (Russell, S., and Wefald, E., Do the Right Thing, Cambridge, MA: MIT Press, 1991.), 4 Àå] ´Â ¾ËÆÄ º£Å¸º¸´Ù È¿°úÀûÀÎ ¹æ¹ýÀ¸·Î Ž»öÆ®¸®¸¦ ÁÙÀ̱â À§ÇØ (°è¼ÓµÇ´Â Ž»öÀÇ ±â´ë°ªÀ» ÀÌ¿ëÇÏ¿©) ¸ÞŸ ·¹º§ °è»êÀ» ¼öÇàÇÏ´Â °ÔÀÓÆ®¸® ¾Ë°í¸®Áò (MGSS* ¿Í MGSS2) À» Á¦¾ÈÇÏ¿´´Ù. Berliner ÀÇ B* ¾Ë°í¸®Áòµµ ±¸°£ ÇÑ°è (interval bound) [Berliner 1979] ¸¦ »ç¿ëÇÏ¿© º¸´Ù È¿°úÀûÀÎ Àý´ÜÀ» ÇÑ´Ù. [Korf 1991 (Korf, R., "Multi-Player Alpha-Beta Pruning," Artificial Intelligence}, 48:99-111, 1991.)] Àº ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ¿©·¯ ¸íÀÌ ÇÏ´Â °ÔÀÓ¿¡ Àû¿ëÇϵµ·Ï È®ÀåÇÏ¿´´Ù.

¼öÄ¡ Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇÏ´Â ´ë½Å¿¡, °ÔÀÓ¿¡ ´ëÇÑ ÀϺΠ¿¬±¸¿¡¼­´Â ÇϳªÀÇ »óȲÀÌ ´Ù¸¥ »óȲ¿¡ ºñÇØ ´õ ÁÁÀºÁö (better than) ȤÀº ´õ ³ª»ÛÁö (worse than) ¸¦ ÆÇ´ÜÇÏ´Â µ¥ ÆÐÅÏÀÎ½Ä (pattern recognition) ±â¹ýÀ» »ç¿ëÇÏ¿´´Ù. ÀÌ·¯ÇÑ ±â¹ýÀº ü½ºÀÇ °ÔÀÓ ¸¶Áö¸· ºÎºÐÀ» ¼öÇàÇÏ´Â ÇÁ·Î±×·¥¿¡ »ç¿ëµÇ¾ú´Ù [Huberman 1968 (Huberman, B. J., A Program to Play Chess End Games, Stanford University Computer Science Department Report CS 106, August 19, 1968.), Bratko & Michie 1980 (Bratko, I., and Michie, D., "An Advice Program for a Complex Chess Programming Task," Computer Journal, 23(4):353-359, 1980.)].

°ÔÀÓ¿¡ ´ëÇÑ °¡Àå ¼º°øÀûÀÎ Ãʱ⠾÷ÀûÀº üĿ (Checker) °ÔÀÓ¿¡¼­ÀÇ ±â°è ÇнÀ (machine learning) ¹æ¹ýÀ» °³¹ßÇÑ Arthur Samuel ÀÇ ¿¬±¸ÀÌ´Ù [Samuel 1967 (Samuel, A. L., "Some Studies in Machine Learning Using the Game of Checkers IIm Recent Progress," IBM Jour. R & D, 11(6), 601-617, 1967.) Some Studies in Machine Learning Using the Game of Checkers]. Samuel ÀÇ Ã¼Ä¿ ÇÁ·Î±×·¥Àº èÇǾ𿡠°¡±î¿î ¼öÁØÀ¸·Î °ÔÀÓÀ» ¼öÇàÇÏ¿´´Ù. ÇöÀç´Â University of Alberta ¿¡ ÀÖ´Â Jonathan Schaeffer ÀÇ CHINOOK ÇÁ·Î±×·¥ [Schaeffer et al.1992 (Schaeffer, J., Culberson, J., Treloar, N., Knight, B., Lu, P., and Szafron, L., "A World Championship Caliber Checkers Program," Artificial Intelligence, 53(2-3:273-289, 1992.) A World Championship Caliber Checkers Program, Schaeffer 1997 (Schaeffer, J., One Jump Ahead: Challenging Human Supremacy in Checkers, New York: Springer-Verlag, 1997.)] ÀÌ ¼¼°è üĿ èÇǾðÀ¸·Î ¾Ë·ÁÁ® ÀÖ´Ù. 1997³â¿¡´Â IBM ÀÇ ÇÁ·Î±×·¥ÀÎ DEEP BLUE °¡ èÇǾð ŸÀÌƲÀü¿¡¼­ ¼¼°è ü½º èÇǾðÀÎ Garry Kasparov ¸¦ ÀÌ°å´Ù.

[Monty Newborn 1996 (Newborn, M., Computer Chess Comes of Age, New York: Springer-Verlag, 1996.) Computer Chess Comes of Age] Àº ÄÄÇ»ÅÍ Ã¼½º¿¡ °üÇÑ Ã¥À¸·Î¼­, 1996³â¿¡ DEEP BLUE °¡ Garry Kasparov ¿¡°Ô ÆÐÇÒ ¶§±îÁöÀÇ ¿ª»ç¸¦ ¿­°ÅÇÑ °ÍÀÌ´Ù. ÀÌ Ã¥¿¡ ´ëÇÑ ¼­Æò°ú AI ¸¦ À§ÇÑ ¿¬±¸¿ëÀ¸·Î¼­ÀÇ Ã¼½ºÀÇ ¿ªÇÒ¿¡ ´ëÇÑ ¼³¸íÀº [John McCarthy 1997 AI as Sport] À» ÂüÁ¶Ç϶ó. McCarthy ´Â ü½º ÇÁ·Î±×·¥ÀÌ Á»´õ Àΰ£°ú ºñ½ÁÇÑ Ãß·Ð ¹æ¹ýÀ» »ç¿ëÇÑ´Ù¸é ´õ ÀûÀº Ž»öÀ¸·Îµµ ´õ ³ªÀº ¼º´ÉÀ» º¸ÀÏ °ÍÀ̶ó°í ÇÏ¿´´Ù. [Michie.D 1966 Game Playing and Game Learning Automata] ´Â ±â´ë°ª ÃÖ´ëÈ­ (expectimax) ¶ó´Â ¸»À» ¸¸µé°í ÀÌ ±â¹ý¿¡ ´ëÇÑ ½ÇÇèÀ» ¼öÇàÇÏ¿´´Ù.

[Lee & Mahajan 1988 (Lee, K.-F., and Mahajan, S., "A Pattern Classification Approach to Evaluation Function Learning," Artificial Intelligence, 36(1):1-26, 1988.)] Àº °­È­ ÇнÀ (reinforcement learning) ¹æ¹ýÀ» ¿À¼¿·Î (Othello) °ÔÀÓ¿¡ Àû¿ëÇÏ¿´À¸¸ç, [Schraudolph, Dayan, & Sejnowski 1994 (Schraudolph, N., Dayan, P., and sejnowski, T., "Temporal Difference Position Evaluation in the Game of GO," in Cowan, J., et al. (eds.), Advances in Neural Information Processing Systems, 6, pp.817-824, San Francisco: Morgan Kaufmann, 1994.] ´Â ½Ã°£Â÷ÀÌ (temporal difference) ±â¹ýÀ» ¹ÙµÏ¿¡ Àû¿ëÇÏ¿´´Ù. ÀϹÝÀûÀÎ °ÔÀÓ Å½»ö ¹æ¹ý¿¡ ´ëÇØ ´õ ¾Ë°í ½Í´Ù¸é [Judea Pearl 1984 (Pearl, J., Heuristics: Intelligent Search Strategies for Computer Problem Solving, Reading, MA: Addison-Wesley, 1984.), Heuristics Intelligent Search Strategies... 9 Àå] À» ÂüÁ¶Ç϶ó.