MOGOçè¯ç
å
ä»
çä¸æ©è¯´èµ·å§ãä¸æ©æ¯å大æ°å¦00çå¦çï¼ä¹åæ¥Ecole Polytechniqueå¦ä¹
åºç¨æ°å¦ç¡å£«ï¼Polytechniqueæ¯æ³å½çæ¸
åï¼ãçå°ä»çååï¼ææ»æ¯ä¸ç±èªä¸»å°æ³èµ·
é²è¿
å»å¨ä¹¦æ¡ä¸çé£ä¸ªâæ©âåãäºå®ä¸ï¼ä¸æ©å¾èªæä¹å¾å¤å¥ï¼åäºè®¤çä¸ä¸ä¸èãäºå®ä¸ï¼mogoä¸ä»ç¼åç代ç å¯è¯»æ§æ强ã2006å¹´4æï¼ä»å¨lriï¼æ³å½ä¿¡æ¯ææ¯ç 究室ï¼ä½äºæ¯ä¸å®ä¹ ï¼åSylvain Gellyï¼å½æ¶è¿æ¯å¨è¯»å士ï¼ä¸èµ·å·¥ä½ãå 为ä¸æ©ä»ä»å°çç±å´æ£ï¼æçå´æ£å°±æ¯ä»æçï¼ååï¼ï¼å°±å¼å§å°è¯è®¡ç®æºå´æ£çç¼åã
å¨æçæ¥ï¼è®¡ç®æºå´æ£å象æ£ç¸æ¯ï¼ä¸»è¦é¾ç¹å¨äºæ²¡æä¸ä¸ªå¥½çè¯ä¼°å½æ°ï¼Evaluate functionï¼ãå¨
å½é
象æ£ä¸ï¼å¦æä¸æ¹æ失äºå¤§åï¼å¦åï¼æè
åå没æåæ¶å±å¼ï¼é£ä¹å½¢å¿å¾å¯è½å°±ä¸è¾¹åäºãæ以è¯ä¼°å½æ°å¾å¾æ¯å个åç
å æå¹³åï¼å ä¸æ¯ä¸ªåå¯ä»¥æ»å»å°ä½ç½®ï¼åå ä¸ä¸äºä¿®æ£é¡¹ãæäºè¯ä¼°å½æ°ï¼å°±å¤§å¤§ç®åäºæç´¢ãå¦æè¯ä¼°å½æ°æ¯100%精确çï¼åªè¦è¿è¡ä¸æ¬¡max minçæç´¢æ¾æ大å¼å°±å¯ä»¥äºãå³ä½¿è¯ä¼°å½æ°åªæ¯è¿ä¼¼ï¼ä¹å¯ä»¥çå»å¾å¤æ ç¨çæç´¢ãä½æ¯å¨å´æ£ä¸ï¼æ®ææç¥ï¼è¿æ²¡æä¸ä¸ªä»¤äººæ»¡æçè¯ä¼°å½æ°ãå¨è¿ç§æ
åµä¸ï¼å¤§å®¶å°±æåºç¨MC模ææ¥ä»£æ¿è¯ä¼°å½æ°ãä½æ¯é®é¢ååºç°äºï¼MC模æçæ¶æé度æ¯1/sqrt(N)ï¼èµ°ä¸è½åªæ¨¡æä¸æç´¢å
¶ä»å¯è½çæ£æ¥åãè¿å°±æ¯ä¸ä¸ªå
¸åçExploration vs Exploitationçé®é¢ãå¨Bandité®é¢ä¸ï¼UCTç®æ³æ¯ç¸å½ä¸éçãå½N(模æ次æ°)è¶äºæ ç©·æ¶ï¼æ好çåæ¯åå
¶ä»åæ¯ç模æ次æ°åå«æ¯NåLnNé级ãMCåUCTçç»å产çäºMOGOçéå½¢ã
å¨06å¹´6æ份ï¼MOGOçé形就å®æäºãä¸æ©é请æ们åMOGO对å¼ï¼æ¥å¯»æ¾bugãå½æ¶MOGOæ£åå¾å·®ï¼å¨9x9çæ£çä¸ï¼è¿æè¿ä¸ªåªå¦äº2个æå´æ£çèé¸é½ä¸ä¸è¿ãï¼æ³æ³ç°å¨ï¼æé½å·²ç»æ²¡æåmogoä¸æ£çåæ°äºï¼
MOGOçMCæ¹è¿
å¨
æ£éä¸ï¼
ä½ä¸ºï¼å¡ç¢é½å¨è¿½æ±çç¥ä¹ä¸æãæä¸æç½ç¥ä¹ä¸æçç¡®åå«ä¹ï¼ä½æ¯å¨çµèå´æ£è¿ä¸ªé¢åéï¼å¤§å®¶ç¡®å®æ¯ä¸æåæ°ï¼ä¸ææ¹è¿ï¼æ¥ææ人对å´æ£çåæã
Random MCé¨å
åé¢å·²ç»è¯´è¿äºï¼ç¨MC模ææ¥ä»£æ¿è¯ä¼°å½æ°ï¼ä½æ¯é®é¢æ¯å¥½æ¯ä¸¤ä¸ªé«æä¸æ£ï¼ä¸äºä¸åï¼è®©ä¸¤ä¸ªä¸ä¼ä¸æ£çé¨å¤æ±æ¥è¡èµ°ä¸æ°ï¼ç´è³
ç»å±ï¼æ¥å¤æä¹åé«æä¸æ£çå½¢å¿ãè¿æ»æ¯è¯´ä¸è¿å»çãä¸æ©å¨è¿éåäºä¸ä¸ªå
³é®çæ¹è¿ã
å³ä½¿å¨é«æä¸æ£ä¸ï¼é¤äºå¼å±åçªç¶æå
¥å¯¹æ¹éµå°çæ£ï¼å¤§å®¶ä¸è¬é½æ¯ä½¿ç¨é£ï¼é¿ï¼æï¼è¿ï¼å°ï¼å²ï¼ç«çå´ç»çèªå·±å·²ææ£åå对æ¹çæ£ååæç« çæ£ï¼æ以ä¸æ©è®©MC模æé¨ååªè½åè¿äºåºå®çå½¢ã就好æ¯æ¯é«æä¸æ£ä¹å让两个庸æä¸è³ç»å±ï¼è¿æ ·è¯å¤çæææ¯ä¸¤äººè¡ä¸ï¼è¦å¥½å¤ªå¤äºãè¿ä¸ªæ¹è¿ç«ç«¿è§å½±ï¼MOGOçæ£åç«å»å¯ä»¥åå·²æççµèå´æ£ç¨åºä¸è¾é«ä¸äºã
ä¹åï¼å°±æ¯å¯¹MCé¨åçå¾®è°äºï¼å¯ä»¥æ³è±¡ï¼å½MCé¨åè¶æºè½ï¼ä»ç»åºçç»å±ç»æè¶ææä¹ï¼ä½æ¯ç¸åºçè¿ç®æ¶é´å°±é¿ï¼æ¨¡æ次æ°å°±å°äºã为äºæ¾å°è¿ä¸¤è
ä¹é´ç平衡ï¼å
æ¯æçå°MC代ç ï¼å°±æ45ç§ï¼ä¸æ©åsylvain以åä¹åçå¼åè
ï¼ä¸åè¯éªï¼ä¸ææ¹è¿ã
UCTé¨å
äºå®ä¸ï¼å¨ç°å¨çMOGOç¨åºä¸ï¼å·²ç»ä¸ä½¿ç¨UCTç®æ³äºï¼èæ¯ä»£ä»¥å¾ç±»ä¼¼AMAFç®æ³ãä¹æ以æ¢ç®æ³ï¼åå ä¹å¾ç®åï¼ä½¿ç¨AMAFç®æ³çå´æ£ç¨åºå¯¹UCTçèçè¶
è¿50%ã
åºäºMCçå´æ£ç¨åºç¸å¯¹äºåºäºå´æ£ç¥è¯çç¨åºï¼æ大ç好å¤å°±æ¯ï¼éççµèè¿ç®è½åçæé«ï¼MCå´æ£çæ£åä¹æ¯æ°´æ¶¨è¹é«ã大家é½çç¥ç
æ©å°å®å¾--CPUçæ§è½æ¯18个ææé«ä¸åï¼ä»·é±ä¸éä¸åãæè®°å¾å å¹´åï¼å¤§å®¶è¿ççé¹é¹ç讨论æ©å°å®å¾æ¯å¦è½æç»ä¸å»--å 为éçIC尺度ç缩å°ï¼æ£çï¼éåæåºé½æ为é¾ä»¥é¾è¶çç¶é¢ãä½æ¯ç°å¨çæ¥ï¼è¿ä¸ªå®å¾éè¿å¦ä¸ç§æ¹æ³æç»ä¸å»äº--å¤æ ¸ææ¯ãï¼æä¸å¥é¢å¤è¯ï¼Playstation 3以ä»å¼ºå¤§å丽ç9æ ¸ï¼ä»¤äººä¹èçä»·æ ¼ï¼ä¸å°4000人æ°å¸ï¼åºäººææçæ¾å°äºé¤äºæ¸¸æè¿·å¤æ°çç²ä¸--并è¡è¿ç®çå®éªå®¤ï¼
å¤æä¸ä¸ªå´æ£ç¨åºä¼å£çæä½³æ¹æ³å°±æ¯ç¸äºä¸æ£çèµ¢æ£çï¼ä½æ¯è¿å¾èæ¶é´ãæ以大家éç¨äºå¦ä¸ä¸ªç´§å¯ç¸å
³ä½å¯ä»¥å®æ¶çæµçåæ°--æ¯ç§MCç次æ°ä½ä¸ºä¸ä¸ªä¼åçç®æ ãå¨åCPUçä¼åææçªç ´ä¹åï¼ä¸ä¸æ¥èªç¶æ¯å¹¶è¡è¿ç®ãäºå®ä¸ï¼MCæ¯å¤©ç¶éå并è¡è¿ç®çã
å¨è¿ä¸ç¹ä¸ï¼mogoåå
¶ä»åºäº
èç¹å¡æ´ç®æ³çç¨åºå°±æ¾ç¤ºåºä¼äºå
¶å®ä¼ ç»çåºäºå®å¼çç¨åºçä¼ç¹äºãå¦æåªæ¯å人类模仿ï¼æ¯æ°¸è¿èµ¢ä¸äºçã
mogoè¿ç¨äº800cpuçclusterãä»å¹´å¨è¢«è®©9åçæ
åµä¸å¨19x19ä¸æèäºå
«æ®µé©å½èä¸æ£å£«MyungwanKimãå½ç¶ï¼kimå¼å§ä¸¥éä½ä¼°äºmogoçæ£åï¼å¼å§ä¸å¾å¾å·®ãä»è¾æ£ä¹åï¼å½ç¶å¤§èµmogoï¼æ±ã
ä¸ä¸ªæï¼mogoå¨å°æ¹¾åå¨ä¿åææï¼å¨9x9ä¸åå
ï¼æé»æç½åä¸å±ï¼19x19被让7åï¼ãå¨9x9çæ¯èµä¸ï¼å¨ä¿åé©èï¼å¨19x19ä¸ï¼mogoä¸çå¾å·®ï¼mogoçç¹ç¹æ¯å¦æè½å¤é¢å
ï¼å°±è½å¬ä½ï¼ä¸åºæ¯è¾æè´¨éçæ£ï¼ä½æ¯ä¸æ¦è½åï¼å°±èªæ´èªå¼ï¼ãï¼ä¹æ¯ä¸ä¸ªæï¼å¨å京ï¼mogoè¾ç»äºmany faces goï¼ä¸ä¸ªç¾å½çå´æ£ç¨åºï¼åå æ®è¯´æ¯--ä½äºè·å
°çclusteréä¸åçµ...ï¼
MOGOæè¿åä½äºæ°çæ¹è¿ï¼ç°å¨åæºç大æ¦è¾¾å°KGSä¸1kçæ°´å¹³ãå¨kgsä¸MOGOçè´¦å·æ¯mogobot1åmogobot3ã