กลับไปหน้าบทความ

อ่าน 4 นาที

เกมการวางตำแหน่งที่ไม่เป็นธรรม

เกมตำแหน่ง

เกมตำแหน่งที่มีอคติ : 27–42เป็นรูปแบบหนึ่งของเกมตำแหน่งเช่นเดียวกับเกมตำแหน่งส่วนใหญ่ เกมนี้อธิบายโดยชุดของตำแหน่ง/จุด/องค์ประกอบ (X{\displaystyle X}) และตระกูลของเซตย่อย...

เกมการวางตำแหน่งที่ไม่เป็นธรรม

เกมตำแหน่งที่มีอคติ[ 1 ] [ 2 ] : 27–42เป็นรูปแบบหนึ่งของเกมตำแหน่งเช่นเดียวกับเกมตำแหน่งส่วนใหญ่ เกมนี้อธิบายโดยชุดของตำแหน่ง/จุด/องค์ประกอบ (X{\displaystyle X}) และตระกูลของเซตย่อย (เอฟ{\displaystyle {\mathcal {F}}}ซึ่งโดยทั่วไปเรียกว่าชุดที่ชนะ เกมนี้เล่นโดยผู้เล่นสองคนที่ผลัดกันเลือกองค์ประกอบจนกว่าองค์ประกอบทั้งหมดจะถูกเลือก ในขณะที่ในเกมมาตรฐาน ผู้เล่นแต่ละคนจะเลือกองค์ประกอบหนึ่งชิ้นต่อตา แต่ในเกมที่ไม่เป็นธรรม ผู้เล่นแต่ละคนจะเลือกองค์ประกอบจำนวนไม่เท่ากัน

กล่าวอย่างเป็นทางการมากขึ้น สำหรับจำนวนเต็มบวกสองจำนวนใดๆpและqเกมแบบ (p:q)-positional คือเกมที่ผู้เล่นคนแรกเลือก องค์ประกอบ pตัวต่อตา และผู้เล่นคนที่สองเลือก องค์ประกอบ qตัวต่อตา

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

ตัวอย่าง

ยกตัวอย่างเช่นเกมสามเหลี่ยมในเกมนี้ องค์ประกอบทั้งหมดคือขอบของกราฟสมบูรณ์ที่มีnจุดยอด และเซตที่ชนะคือสามเหลี่ยมทั้งหมด (=คลิกที่มี 3 จุดยอด) สมมติว่าเราเล่นเกมนี้ในรูปแบบเกมผู้สร้าง-ผู้ทำลาย กล่าวคือ เป้าหมายของผู้สร้าง (ผู้เล่นคนแรก) คือการเลือกสามเหลี่ยม และเป้าหมายของผู้ทำลาย (ผู้เล่นคนที่สอง) คือการป้องกันไม่ให้ผู้สร้างเลือกสามเหลี่ยม จากการวิเคราะห์กรณีอย่างง่าย สามารถพิสูจน์ได้ว่าผู้สร้างมีกลยุทธ์ที่ชนะเมื่อใดก็ตามที่nมีค่าอย่างน้อย 6 ดังนั้นจึงน่าสนใจที่จะถามว่าข้อได้เปรียบนี้สามารถเปลี่ยนแปลงได้หรือไม่โดยการให้ผู้ทำลายเลือกองค์ประกอบมากกว่า 1 รายการต่อตา

แท้จริงแล้วสามารถพิสูจน์ได้ว่า: [ 1 ]

  • สำหรับทุกๆq0.5n{\displaystyle q\leq 0.5{\sqrt {n}}}Maker ชนะเกมสามเหลี่ยม (1: q ) บน จุดยอดn จุด
  • สำหรับทุกๆq2n{\displaystyle q\geq 2{\sqrt {n}}}เบรกเกอร์ชนะเกมสามเหลี่ยม (1: q ) บน จุดยอดn จุด

เงื่อนไขแห่งชัยชนะสำหรับเบรกเกอร์

ในเกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบท Erdos-Selfridge ให้เงื่อนไขการชนะสำหรับ Breakerเงื่อนไขนี้สามารถขยายไปสู่เกมที่มีอคติได้ดังนี้: [ 3 ] [ 2 ] : 30–32

  • ถ้าอีเอฟ(1+q)|อี|/พี<1{\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<1}ดังนั้น Breaker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) เมื่อเล่นก่อน
  • ถ้าอีเอฟ(1+q)|อี|/พี<11+q{\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<{1 \over 1+q}}ดังนั้น Breaker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) แม้ว่าจะเล่นเป็นฝ่ายที่สองก็ตาม

กลยุทธ์นี้ใช้ฟังก์ชันศักยภาพซึ่งเป็นการขยายฟังก์ชันของ Erdos-Selfridge ศักยภาพของเซตที่ชนะ (ไม่แตก) Eที่มีองค์ประกอบที่ยังไม่ได้ถูกเลือก | E | ตัว ถูกกำหนดดังนี้(1+q)|อี|/พี{\displaystyle (1+q)^{-|E|/p}}ถ้า Maker ชนะเกม แสดงว่ามีเซตEที่มี | E |=0 ดังนั้นค่าศักยภาพของเซตนี้คือ 1 ดังนั้น เพื่อพิสูจน์ว่า Breaker ชนะ จึงเพียงพอที่จะพิสูจน์ว่าผลรวมศักยภาพสุดท้ายน้อยกว่า 1 อันที่จริง ตามสมมติฐาน ผลรวมศักยภาพในตาแรกของ Breaker น้อยกว่า 1 และถ้า Breaker เลือกองค์ประกอบที่ทำให้ค่าศักยภาพลดลงสูงสุดเสมอ ก็สามารถแสดงได้ว่าผลรวมศักยภาพจะลดลงอย่างอ่อนๆ เสมอ

เมื่อแต่ละเซ็ตที่ชนะมีเค{\displaystyle k}สำหรับค่าk ที่กำหนดไว้ เงื่อนไขการชนะของ Breaker จะลดรูปเหลือดังนี้: |เอฟ|<(q+1)เค/พี{\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}}(เมื่อเล่นครั้งแรก) หรือ|เอฟ|<(q+1)เค/พี1{\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}}(เมื่อเล่นเป็นคนที่สอง) เงื่อนไขนี้ค่อนข้างเข้มงวด: มีเซตตระกูลk -uniform ที่มี|เอฟ|=(q+1)เค/พี1{\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}ชุดที่ผู้สร้างชนะ[ 4 ]

เงื่อนไขแห่งชัยชนะสำหรับเมกเกอร์

ในเกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบทของ Beck ให้เงื่อนไขการชนะสำหรับฝ่าย Makerโดยใช้ระดับคู่ของไฮเปอร์กราฟ ซึ่งแสดงด้วย2{\displaystyle d_{2}}เงื่อนไขนี้สามารถนำไปใช้กับเกมที่มีอคติได้ดังนี้: [ 3 ]

ถ้าอีเอฟพี+qพี|อี|>พี2q2(พี+q)32|X|{\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}ดังนั้น Maker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) เมื่อเล่นก่อน

เงื่อนไขแห่งชัยชนะสำหรับ Avoider

ในเกม Avoider-Enforcer ที่มีอคติ เงื่อนไขต่อไปนี้รับประกันว่า Avoider มีกลยุทธ์ที่ชนะ: [ 2 ] : 47–49

  • ถ้าอีเอฟ(1+1/พี)พี|อี|<1{\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|}<1}จากนั้น Avoider จะชนะเกม (p:q) เมื่อเล่นก่อน ภายใต้กฎทั้งแบบเข้มงวดและแบบโมโนโทนิก นี่เกือบจะพอดี: มีตระกูลเกม (p:q) ที่ไม่มีที่สิ้นสุดซึ่งนิพจน์นี้มีค่ามากกว่า 1 เล็กน้อยและ Enforcer ชนะ[ 5 ]โดยเฉพาะอย่างยิ่งในเกมที่ไม่ลำเอียง เงื่อนไขจะกลายเป็นอีเอฟ21|อี|<1{\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|}<1}ถ้ากราฟเป็น แบบ k -uniform เงื่อนไขจะกลายเป็น|เอฟ|<(1+1/พี)เค1{\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}เป็นเรื่องน่าทึ่งที่เงื่อนไขนี้ไม่ขึ้นอยู่กับค่า qเลย
  • ถ้าเซตที่ชนะแต่ละเซตมีสมาชิกไม่เกิน k ตัว และ อีเอฟ(1+qพีเค)พี|อี|<1{\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}<1}จากนั้น Avoider จะชนะเกม (p:q) เมื่อเล่นก่อน[ 6 ]

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Biased_positional_game&oldid=1308970540 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ เกมการวางตำแหน่งที่ไม่เป็นธรรม

เกมตำแหน่งที่มีอคติ : 27–42เป็นรูปแบบหนึ่งของเกมตำแหน่งเช่นเดียวกับเกมตำแหน่งส่วนใหญ่ เกมนี้อธิบายโดยชุดของตำแหน่ง/จุด/องค์ประกอบ (X{\displaystyle X}) และตระกูลของเซตย่อย...

ตัวอย่าง

ยกตัวอย่างเช่น เกมสามเหลี่ยม ในเกมนี้ องค์ประกอบทั้งหมดคือขอบของ กราฟสมบูรณ์ ที่มี n จุดยอด และเซตที่ชนะคือสามเหลี่ยมทั้งหมด (=คลิกที่มี 3 จุดยอด) สมมติว่าเราเล่นเกมนี้ในรูปแบบ เกมผู้สร้าง-ผู้ทำลาย กล่าว คือ เป้าหมายของผู้สร้าง (ผู้เล่นคนแรก)...

เงื่อนไขแห่งชัยชนะสำหรับเบรกเกอร์

ใน เกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบท Erdos-Selfridge ให้ เงื่อนไขการชนะสำหรับ Breaker เงื่อนไขนี้สามารถขยายไปสู่เกมที่มีอคติได้ดังนี้: [ 3 ] [ 2 ] : 30–32

เงื่อนไขแห่งชัยชนะสำหรับเมกเกอร์

ในเกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบทของ Beck ให้ เงื่อนไขการชนะสำหรับฝ่าย Maker โดยใช้ระดับคู่ของไฮเปอร์กราฟ ซึ่งแสดงด้วย ง 2 {\displaystyle d_{2}} เงื่อนไขนี้สามารถนำไปใช้กับเกมที่มีอคติได้ดังนี้: [ 3 ]