เกมค้นหาเป็นเกมผลรวมเป็นศูนย์ระหว่างผู้ค้นหาอย่างน้อยหนึ่งคนกับเป้าหมายที่อยู่กับที่หรือเคลื่อนที่ได้หนึ่งเป้าหมายขึ้นไป ซึ่งเกิดขึ้นในเซตที่เรียกว่าพื้นที่ค้นหา ผู้ค้นหาต้องตรวจจับหรือจับเป้าหมายภายใต้ข้อจำกัดของทรัพยากร ผู้ค้นหาสามารถเลือกวิถีการเคลื่อนที่ต่อเนื่องใดๆ ก็ได้ภายใต้ข้อจำกัดความเร็วสูงสุด ในฐานะแบบจำลองทางคณิตศาสตร์ เกมค้นหาสามารถนำไปใช้ในด้านต่างๆ เช่น เกมซ่อนหาที่เด็กๆ เล่น หรือการจำลองสถานการณ์ทางยุทธวิธีทางทหารบางอย่าง เช่น การต่อต้านเรือดำน้ำหรือการป้องกันภัยทางอากาศ ซึ่งยานพาหนะค้นหาจะกวาดล้างพื้นที่เพื่อสกัดกั้นศัตรูในอดีต^{[ 1 ]}ปัจจุบัน แบบจำลองเหล่านี้ขยายไปสู่ความปลอดภัยทางไซเบอร์ ซึ่งผู้ป้องกันจะสำรวจ "พื้นที่สถานะ" ของระบบและเครือข่ายเพื่อค้นหาการบุกรุกของศัตรู นอกจากนี้ยังใช้ในชีววิทยาเพื่อจำลองปฏิสัมพันธ์ระหว่างผู้ล่าและเหยื่อ^{[ 2 ] [ 3 ] [ 4 ]}ซึ่งผู้ล่าอาจมีทรัพยากรจำกัด (จำนวนชั่วโมงกลางวัน แรงจูงใจ^{[ 5 ]}เป็นต้น)

เกมค้นหาประกอบด้วย:

• พื้นที่ค้นหา X ซึ่งอาจเป็นโดเมนแบบยุคลิด กราฟ หรือพื้นที่สถานะที่เป็นนามธรรมมากกว่านั้น
• ผู้ค้นหาตั้งแต่หนึ่งคนขึ้นไป ซึ่งวิถีการเคลื่อนที่ของพวกเขาสามารถวัดได้เมื่อเทียบกับเวลา โดยอยู่ภายใต้ข้อจำกัดด้านความเร็วสูงสุดหรืองบประมาณการเคลื่อนที่
• ผู้ซ่อนตัวหรือเป้าหมายอย่างน้อยหนึ่งราย ไม่ว่าจะอยู่กับที่หรือเคลื่อนที่ได้ ซึ่งเลือกตำแหน่งเริ่มต้นหรือวิถีการเคลื่อนที่ภายใต้ข้อจำกัดของตนเอง
• ชุดกลยุทธ์สำหรับผู้ซ่อนและผู้ค้นหา
• กฎการตรวจจับ มักกำหนดเป็น "การจับภาพ" เมื่อระยะห่างระหว่างผู้ค้นหาและเป้าหมายน้อยกว่ารัศมีตรวจจับ หรือเมื่อถึงพื้นที่สังเกตการณ์แล้ว
• เกณฑ์การประเมินผลการปฏิบัติงาน เช่น ระยะเวลาในการตรวจจับ ความน่าจะเป็นในการตรวจจับก่อนถึงกำหนดเวลา หรือการผสมผสานระหว่างต้นทุนและผลตอบแทนโดยทั่วไป

โดยทั่วไปเกมจะเล่นภายใต้ความไม่แน่นอน: ผู้เล่นไม่จำเป็นต้องสังเกตตำแหน่งที่แน่นอนของกันและกันจนกว่าจะอยู่ในระยะการตรวจจับ แต่พวกเขาอาจมีข้อมูลบางส่วน^{[ 6 ]}กลยุทธ์อาจเป็นแบบบริสุทธิ์ แบบผสม แบบป้อนกลับ หรือแบบอิงข้อมูล ขึ้นอยู่กับโครงสร้างการสังเกตและพลวัตของเกม

พื้นที่ของเกมค้นหาได้รับการแนะนำในบทสุดท้ายของ หนังสือคลาสสิกของ Rufus Isaacsเรื่อง "Differential Games" ^{[ 7 ]}ซึ่ง Isaacs ศึกษาสถานการณ์การไล่ล่า-หลบหนีและการค้นหาด้วยข้อมูลบางส่วน

เกมเจ้าหญิงและสัตว์ประหลาดเกี่ยวข้องกับเป้าหมายที่เคลื่อนที่ ผู้ค้นหาต้องหา "เจ้าหญิง" ที่เคลื่อนที่ในช่วงเวลาหรือโดเมนที่มีทัศนวิสัยจำกัดและพลวัตต่อเนื่อง เกมนี้แสดงให้เห็นถึงความยากลำบากในการออกแบบกลยุทธ์ที่เหมาะสมที่สุดเมื่อวิถีการเคลื่อนที่ของผู้เล่นต่อเนื่องและข้อมูลมีจำกัดมาก สมมติว่าทั้งผู้ค้นหาและผู้ซ่อนไม่มีความรู้เกี่ยวกับการเคลื่อนที่ของผู้เล่นอีกฝ่ายจนกว่าระยะห่างระหว่างกันจะน้อยกว่าหรือเท่ากับรัศมีของการค้นพบ และในขณะนั้นเองการจับได้ก็จะเกิดขึ้น เกมนี้เป็นเกมผลรวมเป็นศูนย์ โดยผลตอบแทนคือเวลาที่ใช้ในการค้นหา กลยุทธ์ที่เป็นธรรมชาติในการค้นหาเป้าหมายที่อยู่กับที่ในกราฟ (ซึ่งส่วนโค้งมีความยาว) คือการหาเส้นโค้งปิดที่เล็กที่สุด L ที่ครอบคลุมส่วนโค้งทั้งหมดของกราฟ (L เรียกว่า เส้นทางการเดินทาง ของบุรุษไปรษณีย์จีน ) จากนั้นเดินทางผ่าน L ด้วยความน่าจะเป็น 1/2 สำหรับแต่ละทิศทาง กลยุทธ์นี้ดูเหมือนจะใช้ได้ผลดีหากกราฟเป็นกราฟออยเลอร์โดยทั่วไปแล้ว เส้นทางการเดินทางของบุรุษไปรษณีย์จีนแบบสุ่มนี้เป็นกลยุทธ์การค้นหาที่เหมาะสมที่สุดก็ต่อเมื่อกราฟประกอบด้วยชุดของกราฟออยเลอร์ที่เชื่อมต่อกันในโครงสร้างคล้ายต้นไม้^{[ 8 ]}ตัวอย่างกราฟที่ดูเหมือนจะง่ายแต่จริงๆ แล้วไม่ได้อยู่ในตระกูลนี้ ประกอบด้วยโหนดสองโหนดที่เชื่อมต่อกันด้วยส่วนโค้งสามส่วน การเดินทางแบบสุ่มของบุรุษไปรษณีย์ชาวจีน (เทียบเท่ากับการเดินทางผ่านส่วนโค้งทั้งสามในลำดับแบบสุ่ม) ไม่ใช่วิธีที่ดีที่สุด และวิธีที่ดีที่สุดในการค้นหาส่วนโค้งทั้งสามนี้มีความซับซ้อน^{[ 9 ]}

โดยทั่วไป กรอบการทำงานที่เหมาะสมสำหรับการค้นหาโดเมนที่ไม่จำกัด เช่นในกรณีของอัลกอริธึมออนไลน์คือการใช้ฟังก์ชันต้นทุน แบบนอร์มาไลซ์ (เรียกว่าอัตราส่วนการแข่งขันในวรรณกรรมวิทยาศาสตร์คอมพิวเตอร์) วิถี มินิแม็กซ์สำหรับปัญหาประเภทนี้จะเป็นลำดับเรขาคณิตเสมอ (หรือฟังก์ชันเลขชี้กำลังสำหรับปัญหาต่อเนื่อง) ผลลัพธ์นี้ทำให้ได้วิธีการที่ง่ายในการค้นหาวิถีมินิแม็กซ์โดยการลดค่าพารามิเตอร์เดียว (ตัวสร้างลำดับนี้) แทนที่จะค้นหาทั่วทั้งพื้นที่วิถี เครื่องมือนี้ถูกใช้สำหรับปัญหาการค้นหาเชิงเส้น กล่าวคือ การค้นหาเป้าหมายบนเส้นอนันต์ ซึ่งได้รับความสนใจอย่างมากมาหลายทศวรรษและได้รับการวิเคราะห์เป็นเกมการค้นหา^{[ 10 ]}นอกจากนี้ยังถูกใช้เพื่อค้นหาวิถีมินิแม็กซ์สำหรับการค้นหาชุดของรังสีที่ตัดกัน การค้นหาที่เหมาะสมที่สุดในระนาบจะดำเนินการโดยใช้เกลียวเลขชี้กำลัง^{[ 9 ] [ 11 ] [ 12 ]} การค้นหาชุดของรังสีพร้อมกันได้รับการค้นพบอีกครั้งในวรรณกรรมวิทยาศาสตร์คอมพิวเตอร์ในชื่อ 'ปัญหาเส้นทางวัว' ^{[ 13 ]}

พวกเขาได้รับการพัฒนาเพิ่มเติมโดยShmuel Gal ^{[ 9 ] [ 11 ]}และSteve Alpern ^{[ 11 ]}ซึ่งได้พัฒนาพื้นฐานทางคณิตศาสตร์ของเกมการค้นหา โดยเฉพาะอย่างยิ่งสำหรับพื้นที่การค้นหาแบบต่อเนื่อง โครงสร้างข้อมูลที่หลากหลาย และเกณฑ์ความเหมาะสมแบบมินิแม็กซ์ ตั้งแต่ช่วงปี 1990-2000 เป็นต้นมา วรรณกรรมได้ขยายไปสู่รูปแบบต่างๆ ของเครือข่าย สภาพแวดล้อมแบบไม่ต่อเนื่อง และปัญหาที่ได้รับแรงบันดาลใจจากเศรษฐศาสตร์ ความปลอดภัย หรือหุ่นยนต์อัตโนมัติ

บทวิจารณ์ล่าสุดเสนอการจำแนกประเภทเกมการค้นหาโดยละเอียดตามกลยุทธ์ที่มีให้ผู้ค้นหาและเป้าหมาย^{[ 14 ]}

• ใน เกมค้นหา เป้าหมายคงที่ มีเพียงผู้ค้นหาเท่านั้นที่เคลื่อนที่ และเป้าหมายจะถูกกำหนดโดยการกระจายเริ่มต้นบนพื้นที่การค้นหา
• ใน เกมค้นหา เป้าหมายเคลื่อนที่ เป้าหมายจะเลือกเส้นทางการเคลื่อนที่อย่างกระตือรือร้น โดยมักอยู่ภายใต้ข้อจำกัดด้านความเร็วหรือลักษณะทางภูมิศาสตร์ ทำให้เกมเหล่านี้ใกล้เคียงกับเกมไล่ล่าและหลบหนี
• ใน เกม ที่มีข้อจำกัดด้านเส้นทางผู้เล่นทั้งสองต้องเคลื่อนที่ไปตามเส้นทางที่กำหนดไว้ เช่น เครือข่ายถนน ทางเดิน หรือเส้นทางเดินเรือ สำหรับผู้ค้นหา วิธีแก้ปัญหาที่ดีที่สุดมักเกี่ยวข้องกับกลยุทธ์การสำรวจแบบวนซ้ำหรือแบบสุ่ม บางครั้งอาจมีการสุ่มเวลาเพื่อหลีกเลี่ยงการคาดเดาได้
• ใน เกม ค้นหา-ค้นหาผู้ค้นหาหลายคนหรือเป้าหมายหลายคนจะโต้ตอบกัน เช่น หน่วยลาดตระเวนที่แข่งขันกัน หรือกลุ่มพันธมิตรป้องกันและโจมตีที่ประสานงานกัน

มุมมองที่เป็นเอกภาพระหว่างเกมค้นหาและเกมไล่ล่า-หลบหนี มองว่าระบบที่เป็นปฏิปักษ์กันหลายระบบเป็นลำดับของขั้นตอนต่างๆ ได้แก่ ขั้นตอนการซ่อนตัวและค้นหา (ซ่อนหา) ขั้นตอนการไล่ล่า-หลบหนีหลังจากตรวจพบ และขั้นตอนการจับกุมหรือการปะทะที่เป็นไปได้ แต่ละขั้นตอนมีข้อมูล พลวัต และโครงสร้างผลตอบแทนของตัวเอง^{[ 15 ] [ 16 ]}

การตัดสินใจที่เกิดขึ้นในระหว่างขั้นตอนการค้นหาจะเป็นตัวกำหนดเงื่อนไขเริ่มต้นของการไล่ล่า เช่น ระยะทาง มุมการสกัดกั้น หรือพลังงานที่เหลืออยู่

แนวโน้มปัจจุบันคือการศึกษาเกมค้นหาแบบไดนามิกที่ผู้เล่นเรียนรู้^{[ 17 ]}หรือปรับตัวระหว่างเกมแทนที่จะมีความรู้เบื้องต้นที่สมบูรณ์เกี่ยวกับสภาพแวดล้อม กรอบการทำงานนี้มีความเกี่ยวข้องเมื่อผู้ค้นหาสะสมประสบการณ์เกี่ยวกับพฤติกรรมเป้าหมายทั่วไปหรือคุณสมบัติของภูมิประเทศอย่างค่อยเป็นค่อยไป โมเดลไฮบริดผสมผสานทฤษฎีเกมกับเทคนิคการเรียนรู้ เช่น การเรียนรู้แบบเสริมแรงหรือการเรียนรู้แบบเบย์เซียนเพื่อปรับกลยุทธ์การค้นหาและการซ่อนตัวอย่างต่อเนื่อง

การวิเคราะห์เชิงทฤษฎีของเกมการค้นหาอาศัยเครื่องมือจากทฤษฎีเกมการหาค่าเหมาะสมที่สุดและการควบคุมที่เหมาะสมที่สุด สำหรับแบบจำลองที่ง่าย สามารถหาคำตอบเชิงวิเคราะห์ได้โดยใช้ประโยชน์จากสมมาตร ข้อโต้แย้งเรื่องการเชื่อมโยง หรือการแปลงทางเรขาคณิต

อย่างไรก็ตาม ปัญหาที่สมจริงส่วนใหญ่จำเป็นต้องใช้วิธีการเชิงตัวเลขหรือวิธีการประมาณ เช่น การเขียนโปรแกรมเชิงพลวัตแบบไม่ต่อเนื่อง อัลกอริทึมการวนซ้ำค่า หรือแผนการกึ่งลากรางจ์ ความท้าทายเกิดขึ้นจากมิติที่สูงของปริภูมิสถานะ พลวัตที่ไม่เป็นเชิงเส้น และโครงสร้างข้อมูลที่ซับซ้อน เทคนิคการเร่งความเร็ว เช่น การแยกเฟส การตัดแต่ง หรือการประมาณค่าแบบฮิวริสติก ช่วยลดการระเบิดเชิงการจัดเรียงในขณะที่ยังคงรักษาความเหมาะสมที่สุดไว้ได้ในบางกรณี