การค้นหาแบบทริปเพิลเอสสตาร์

การค้นหาปริภูมิสถานะแบบ SSS* เป็นขั้นตอนวิธีการค้นหาปริภูมิสถานะแบบหนึ่ง ซึ่งถูกนำเสนอขึ้นโดย George Stockman ในปี ค.ศ. 1979 โดยขั้นตอนวิธีนี้จะทำการสืบค้นปริภูมิสถานะต้นไม้ของเกม (อังกฤษ: Game Tree) ซึ่งจะเป็นประโยชน์มากต่อการคิดหาวิธีสร้างปัญญาประดิษฐ์ขึ้นในการเล่นเกมเพื่อค้นหาสถานะที่ดีที่สุดที่จะสามารถแก้ไขปัญหาสถานการณ์นั้นๆ ได้ (ตัวอย่างเช่น การเล่นหมากกระดาน ซึ่งเราต้องหาเส้นทางที่เป็นไปได้ในขั้นถัดไป และเลือกวิธีเล่นที่ดีที่สุดเพื่อให้เราชนะ)

แนวคิดของ SSS*

แนวคิดของ SSS* นี้จะเป็นไปในลักษณะการค้นหาแบบกว้าง ซึ่งมีความคล้ายคลึงกับขั้นตอนวิธีของขั้นตอนวิธีเอสตาร์ ในที่นี้ SSS* จะมีแนวคิดพื้นฐานอยู่บนต้นไม้ของคำตอบ (solution tree) โดยทั่วไปต้นไม้ของคำตอบนี้จะสามารถเกิดจากต้นไม้ของเกม โดยการลดจำนวนของกิ่งในแต่ละปมที่เป็น MAX ให้เหลือ 1 กิ่ง (ปม Max ที่ว่านี้หมายถึงปมที่มีโอกาสชนะในการเล่นเกม ซึ่งในที่นี้จะเกี่ยวข้องกับ Minimax Theorem) แล้วเราจะได้แนวทางการแก้ไขปัญหาที่ดีที่สุดสำหรับปม MAX เนื่องจากเป็นการปรับปม MAX สำหรับทุกลำดับของการเล่นที่เป็นไปได้ซึ่งเกิดจากการเล่นของฝ่ายตรงข้าม

ตัวอย่างของแนวคิด

สมมติให้มีต้นไม้สถานะของเกมมาให้แล้ว SSS* จะทำการค้นหาผ่านทางช่องว่างของส่วนหนึ่งของต้นไม้ของคำตอบ และทำการพิจารณาต้นไม้ย่อยต่างๆ และค่อยๆ ขยายขนาดของต้นไม้ย่อยๆ นั้นจนกระทั่งสามารถสร้างต้นไม้ของคำตอบเพียงต้นเดียวที่มีราก (root) ร่วมกัน และค่า Minimax นั้นยังคงค่าเดิมของต้นไม้ที่รับมา ในที่นี้ SSS* จะไม่พิจารณาปมที่ alpha-beta pruning จะทำการตัด และ 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 เอกสารเกี่ยวกับขั้นตอนวิธีการหาปริภูมิสถานะในเกมแบบต่างๆ