Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
การค้นหาปริภูมิสถานะแบบ SSS* เป็นขั้นตอนวิธีการค้นหาแบบหนึ่ง ซึ่งถูกนำเสนอขึ้นโดย George Stockman ในปี ค.ศ. 1979 โดยขั้นตอนวิธีนี้จะทำการสืบค้นปริภูมิสถานะ (อังกฤษ: Game Tree) ซึ่งจะเป็นประโยชน์มากต่อการคิดหาวิธีสร้างปัญญาประดิษฐ์ขึ้นในการเล่นเกมเพื่อค้นหาสถานะที่ดีที่สุดที่จะสามารถแก้ไขปัญหาสถานการณ์นั้นๆ ได้ (ตัวอย่างเช่น การเล่นหมากกระดาน ซึ่งเราต้องหาเส้นทางที่เป็นไปได้ในขั้นถัดไป และเลือกวิธีเล่นที่ดีที่สุดเพื่อให้เราชนะ)
แนวคิดของ SSS*
แนวคิดของ SSS* นี้จะเป็นไปในลักษณะการค้นหาแบบกว้าง ซึ่งมีความคล้ายคลึงกับขั้นตอนวิธีของขั้นตอนวิธีเอสตาร์ ในที่นี้ SSS* จะมีแนวคิดพื้นฐานอยู่บน (solution tree) โดยทั่วไปต้นไม้ของคำตอบนี้จะสามารถเกิดจาก โดยการลดจำนวนของกิ่งในแต่ละปมที่เป็น ให้เหลือ 1 กิ่ง (ปม Max ที่ว่านี้หมายถึงปมที่มีโอกาสชนะในการเล่นเกม ซึ่งในที่นี้จะเกี่ยวข้องกับ Minimax Theorem) แล้วเราจะได้แนวทางการแก้ไขปัญหาที่ดีที่สุดสำหรับปม เนื่องจากเป็นการปรับปม MAX สำหรับทุกลำดับของการเล่นที่เป็นไปได้ซึ่งเกิดจากการเล่นของฝ่ายตรงข้าม
ตัวอย่างของแนวคิด
สมมติให้มีต้นไม้สถานะของเกมมาให้แล้ว SSS* จะทำการค้นหาผ่านทางช่องว่างของส่วนหนึ่งของ และทำการพิจารณาต้นไม้ย่อยต่างๆ และค่อยๆ ขยายขนาดของต้นไม้ย่อยๆ นั้นจนกระทั่งสามารถสร้างต้นไม้ของคำตอบเพียงต้นเดียวที่มีราก (root) ร่วมกัน และค่า Minimax นั้นยังคงค่าเดิมของต้นไม้ที่รับมา ในที่นี้ SSS* จะไม่พิจารณาปมที่ จะทำการตัด และ SSS* อาจจะตัดกิ่งของปมที่ alpha-beta ไม่ได้ทำการตัด ซึ่ง George Stockman เห็นว่าขั้นตอนวิธี SSS* นี้น่าจะเป็นขั้นตอนวิธีที่ดีกว่า alpha-beta pruning อย่างไรก็ตาม Steve Rozen และ Judea Pearl ได้แสดงให้เห็นว่าจำนวนของตำแหน่งที่จะทำการบันทึกข้อมูลของ SSS* เมื่อเปรียบเทียบกับ alpha-beta แล้วจะเห็นว่ามันมีขอบเขตที่จำกัด และโดยทั่วไปนั้นอาจจะไม่พอที่จะเพิ่มทรัพยากรอื่นๆ
ขั้นตอนวิธี
ในขั้นตอนวิธี SSS* นี้จะมี OPEN คือแถวคอยลำดับความสำคัญที่จะเก็บสถานะ (J,s,h) ไว้ที่ปมของต้นไม้ โดย J จะเป็นตัวที่อ้างอิงถึงปมใดๆในต้นไม้นั้น (สัญกรณ์ของดิวอี้จะถูกใช้ในการระบุถึงปมใดๆ และกำหนดให้ ε แทนรากของต้นไม้) s Є {L,S} เป็นสถานะของปม J (L คือปมที่ยังอยู่หรือก็คือปมที่ยังไม่ได้คิดผลของคำตอบ และ S คือปมที่ได้ผลลัพธ์ของคำตอบแล้ว) และ h Є {-∞,∞} จะเป็นค่าของปมที่ถูกหาคำตอบแล้ว ซึ่งค่าที่อยู่ใน OPEN จะถูกเรียงลำดับความสำคัญจากมากไปน้อยตามค่าh ถ้าหากมีมากกว่า 1 ปมที่มีค่าhมากที่สุดแล้ว ในที่นี้จะเลือกปมที่อยู่ซ้ายสุดของต้นไม้มา
OPEN := { (e,L,inf) } while (true) // ทำงานจนกว่าเงื่อนไขที่กำหนดจะเป็นจริง ดึงสถานะ (J,s,h) มาจากข้อมูลตัวแรกของ OPEN และเก็บไว้ที่ P ถ้า ปมJ คือ e และ สถานะ s ถูกหาคำตอบแล้ว(S) หยุดการทำงานและนำค่า h ไปใช้ มิเช่นนั้น ทำการเรียกใช้ Γ สำหรับ p เพื่อหาคำตอบ กระบวนการ Γ สำหรับ p = (J,s,h) จะถูกนิยามดังนี้ :
ถ้า สถานะ s ยังไม่ถูกหาคำตอบ(L) ถ้า ปมJ เป็นปมสุดท้ายของต้นไม้ (1.) เพิ่มสถานะ ( J , S , min(h,value(J) ) ) ไปยัง OPEN มิเช่นนั้น ถ้า ปมJ เป็นปม MIN (2.) เพิ่มสถานะ ( ปมลูกซ้ายสุดของ J ,L,h) ไปยัง OPEN มิเช่นนั้น (3.) สำหรับ i ที่เป็นปมลูกของ J ให้ เพิ่มสถานะ (i,L,h) ไปยัง OPEN มิเช่นนั้น ถ้า ปมJ เป็นปม MIN (4.) เพิ่มสถานะ (ปมแม่ของ J ,S,h) ไปยัง OPEN ลบทุกสถานะใน OPEN ที่เกี่ยวข้องกับปมลูกของJ มิเช่นนั้น ถ้า J เป็นลูกปมสุดท้าย (5.) เพิ่มสถานะ ( แม่ของ J ,S,h) ไปยัง OPEN มิเช่นนั้น (6.) เพิ่มสถานะ ( ปมถัดไปที่เกี่ยวข้องกับปม J ,L,h) ไปยัง OPEN // ให้ T เป็นปมแม่ของ J, ปมที่จะถูกเพิ่มคือปมลูกของ T ที่ไม่ใช่ปม J
การประยุกต์ใช้
การค้นปริภูมิสถานะนี้จะมีประโยชน์ในการนำไปคิดปัญญาประดิษฐ์ในการเล่นเกมแบบ Zero-Sum Game ซึ่งเป็นเกมที่ฝ่ายใดฝ่ายหนึ่งต้องเอาชนะฝ่ายตรงข้าม เช่น เกมกระดาน, ฯลฯ ซึ่งการคิดกลยุทธ์เพื่อหาทางที่จะชนะนี้จำเป็นที่จะต้องมีการคิดสถานะการเล่นล่วงหน้าไว้ก่อน และเลือกเส้นทางที่ดีที่สุดที่สามารถจะชนะคู่ต่อสู้ในเกมนั้นๆได้ โดยในที่นี้ SSS* จะเป็นข้อตอนวิธีหนึ่งที่จะช่วยในการหาสถานะเพื่อนำมาใช้ในการสร้างกลยุธท์เพื่อเอาชนะได้อย่างรวดเร็วในระดับหนึ่ง
บทความที่เกี่ยวข้อง
- Stockman รายละเอียดของ George Stockman ผู้ที่นำเสนอ การค้นปริภูมิสถานะแบบSSS*
- Solution จาก Game Tree การหาผลของคำตอบจากเกมและปัญญาประดิษฐ์ โดยขั้นตอนวิธีแบบต่างๆ
- Maximin เก็บถาวร 2013-06-30 ที่ เวย์แบ็กแมชชีน เกี่ยวกับ Maximin
- GameVisual เก็บถาวร 2009-03-10 ที่ เวย์แบ็กแมชชีน จำลอง Minimax ในต้นไม้ของเกม
- Selective Search in Games of Different Complexity[] เอกสารเกี่ยวกับขั้นตอนวิธีการหาปริภูมิสถานะในเกมแบบต่างๆ
อ้างอิง
- Zero-Sum_Game[]
- "เกมกระดานที่ใช้ SSS*". คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2008-09-28. สืบค้นเมื่อ 2011-09-18.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
karkhnhapriphumisthanaaebb SSS epnkhntxnwithikarkhnhaaebbhnung sungthuknaesnxkhunody George Stockman inpi kh s 1979 odykhntxnwithinicathakarsubkhnpriphumisthana xngkvs Game Tree sungcaepnpraoychnmaktxkarkhidhawithisrangpyyapradisthkhuninkarelnekmephuxkhnhasthanathidithisudthicasamarthaekikhpyhasthankarnnn id twxyangechn karelnhmakkradan sungeratxnghaesnthangthiepnipidinkhnthdip aelaeluxkwithielnthidithisudephuxiherachna aenwkhidkhxng SSS aenwkhidkhxng SSS nicaepnipinlksnakarkhnhaaebbkwang sungmikhwamkhlaykhlungkbkhntxnwithikhxngkhntxnwithiexstar inthini SSS camiaenwkhidphunthanxyubn solution tree odythwiptnimkhxngkhatxbnicasamarthekidcak odykarldcanwnkhxngkinginaetlapmthiepn ihehlux 1 king pm Max thiwanihmaythungpmthimioxkaschnainkarelnekm sunginthinicaekiywkhxngkb Minimax Theorem aelweracaidaenwthangkaraekikhpyhathidithisudsahrbpm enuxngcakepnkarprbpm MAX sahrbthukladbkhxngkarelnthiepnipidsungekidcakkarelnkhxngfaytrngkham twxyangkhxngaenwkhid smmtiihmitnimsthanakhxngekmmaihaelw SSS cathakarkhnhaphanthangchxngwangkhxngswnhnungkhxng aelathakarphicarnatnimyxytang aelakhxy khyaykhnadkhxngtnimyxy nncnkrathngsamarthsrangtnimkhxngkhatxbephiyngtnediywthimirak root rwmkn aelakha Minimax nnyngkhngkhaedimkhxngtnimthirbma inthini SSS caimphicarnapmthi cathakartd aela SSS xaccatdkingkhxngpmthi alpha beta imidthakartd sung George Stockman ehnwakhntxnwithi SSS ninacaepnkhntxnwithithidikwa alpha beta pruning xyangirktam Steve Rozen aela Judea Pearl idaesdngihehnwacanwnkhxngtaaehnngthicathakarbnthukkhxmulkhxng SSS emuxepriybethiybkb alpha beta aelwcaehnwamnmikhxbekhtthicakd aelaodythwipnnxaccaimphxthicaephimthrphyakrxunkhntxnwithiinkhntxnwithi SSS nicami OPEN khuxaethwkhxyladbkhwamsakhythicaekbsthana J s h iwthipmkhxngtnim ody J caepntwthixangxingthungpmidintnimnn sykrnkhxngdiwxicathukichinkarrabuthungpmid aelakahndih e aethnrakkhxngtnim s Ye L S epnsthanakhxngpm J L khuxpmthiyngxyuhruxkkhuxpmthiyngimidkhidphlkhxngkhatxb aela S khuxpmthiidphllphthkhxngkhatxbaelw aela h Ye caepnkhakhxngpmthithukhakhatxbaelw sungkhathixyuin OPEN cathukeriyngladbkhwamsakhycakmakipnxytamkhah thahakmimakkwa 1 pmthimikhahmakthisudaelw inthinicaeluxkpmthixyusaysudkhxngtnimma OPEN e L inf while true thangancnkwaenguxnikhthikahndcaepncring dungsthana J s h macakkhxmultwaerkkhxng OPEN aelaekbiwthi P tha pmJ khux e aela sthana s thukhakhatxbaelw S hyudkarthanganaelanakha h ipich miechnnn thakareriykich G sahrb p ephuxhakhatxb krabwnkar G sahrb p J s h cathukniyamdngni tha sthana s yngimthukhakhatxb L tha pmJ epnpmsudthaykhxngtnim 1 ephimsthana J S min h value J ipyng OPEN miechnnn tha pmJ epnpm MIN 2 ephimsthana pmluksaysudkhxng J L h ipyng OPEN miechnnn 3 sahrb i thiepnpmlukkhxng J ih ephimsthana i L h ipyng OPEN miechnnn tha pmJ epnpm MIN 4 ephimsthana pmaemkhxng J S h ipyng OPEN lbthuksthanain OPEN thiekiywkhxngkbpmlukkhxngJ miechnnn tha J epnlukpmsudthay 5 ephimsthana aemkhxng J S h ipyng OPEN miechnnn 6 ephimsthana pmthdipthiekiywkhxngkbpm J L h ipyng OPEN ih T epnpmaemkhxng J pmthicathukephimkhuxpmlukkhxng T thiimichpm Jkarprayuktichkarkhnpriphumisthananicamipraoychninkarnaipkhidpyyapradisthinkarelnekmaebb Zero Sum Game sungepnekmthifayidfayhnungtxngexachnafaytrngkham echn ekmkradan l sungkarkhidklyuththephuxhathangthicachnanicaepnthicatxngmikarkhidsthanakarelnlwnghnaiwkxn aelaeluxkesnthangthidithisudthisamarthcachnakhutxsuinekmnnid odyinthini SSS caepnkhxtxnwithihnungthicachwyinkarhasthanaephuxnamaichinkarsrangklyuththephuxexachnaidxyangrwderwinradbhnungbthkhwamthiekiywkhxngStockman raylaexiydkhxng George Stockman phuthinaesnx karkhnpriphumisthanaaebbSSS Solution cak Game Tree karhaphlkhxngkhatxbcakekmaelapyyapradisth odykhntxnwithiaebbtang Maximin ekbthawr 2013 06 30 thi ewyaebkaemchchin ekiywkb Maximin GameVisual ekbthawr 2009 03 10 thi ewyaebkaemchchin calxng Minimax intnimkhxngekm Selective Search in Games of Different Complexity lingkesiy exksarekiywkbkhntxnwithikarhapriphumisthanainekmaebbtangxangxingZero Sum Game lingkesiy ekmkradanthiich SSS khlngkhxmulekaekbcakaehlngedimemux 2008 09 28 subkhnemux 2011 09 18