State Machine
ผู้เล่นสองคน ฌาณกับโน้ต มีลูกเต๋าคนละลูก แต่ละคนทอยเต๋าของตัวเองและจดแต้มที่ออกแต่ละครั้งเป็นลำดับที่ต่อเนื่องกันไป ถ้าในลำดับของฌาณปรากฏเลข “12” เขาจะหยุดทันทีและนับจำนวนครั้งทั้งหมดที่ทอย ส่วนโน้ตจะหยุดทอยเมื่อมีเลข “11” เกิดขึ้นในลำดับ คุณผู้อ่านคิดว่าจำนวนครั้งที่ทอยระหว่างฌาณกับโน้ตใครจะมากน้อยกว่ากันครับ? หรือเท่ากัน?

ปัญหาข้อนี้เป็นปัญหาที่ผู้เขียนนำไปตั้งกระทู้เล่นกับเพื่อน ๆ ในเว็บบอร์ดของ pantip.com ห้องหว้ากอ เพราะคิดว่ามีแง่มุมที่น่าสนใจ และเมื่อผู้เขียนเฉลยปัญหาด้วยเทคนิคการนำ State Machine มาใช้คำนวณค่าคาดหมายของจำนวนครั้งที่แต่ละคนจะต้องทอย พบว่าเทคนิคนี้ช่วยลดทอนความซับซ้อนของการคำนวณและสร้างมุมมองอีกมุมหนึ่งได้อย่างสวยงาม จึงเป็นที่มาของบทความตอนนี้ ผู้เขียนจะนำเสนอ State Machine และการใช้ State Machine ช่วยแก้ปัญหาโจทย์

State Machine

ตัวอย่างยอดนิยมในการอธิบายเรื่องนี้คือตู้ขายสินค้าอัตโนมัติ สมมติว่าเรากำลังพูดถึงตู้ขายชา-กาแฟชนิดหยอดเหรียญ ผู้ซื้อสามารถเลือกได้ว่าต้องการเครื่องดื่มร้อนหรือเย็น เติมนมหรือไม่เติมนม หวานหรือไม่หวาน เมื่อผู้ซื้อหยอดเหรียญตามราคาสินค้าแล้วกดปุ่มเลือกสินค้า ซึ่งคุณอาจจะกดปุ่ม ชา/ร้อน/ไม่เติมนม/หวาน จากนั้นก็รอรับถ้วยกระดาษที่บรรจุชาร้อน เราสามารถวาดภาพกลไกอย่างง่ายภายในตู้ได้ว่าประกอบด้วย ท่อกาแฟ ท่อน้ำชา ท่อนม ท่อน้ำเชื่อม และท่อน้ำแข็ง โดยท่อเหล่านี้จะเปิดปิดตามคำสั่งที่ได้รับจากปุ่มกด เช่น ถ้าคุณกดปุ่มกาแฟ ท่อกาแฟก็จะเปิด, กดปุ่มหวาน ท่อน้ำเชื่อมเปิด หรือกดปุ่มเย็น ท่อน้ำแข็งเปิด กลไกดังกล่าวแสดงภาพอย่างง่ายของแบบจำลอง (model) ที่ประกอบด้วย ข้อมูลป้อนเข้า (input), ผลลัพธ์ (output) และกระบวนการ (process) ข้อมูลที่ป้อนเข้าได้แก่ปุ่มกด จากตัวอย่างเราอาจจะมีเพียง 5 ปุ่ม ชา (T), กาแฟ (C), เติมน้ำแข็ง (I), เติมนม (M), เติมน้ำเชื่อม (S) (ว่าโดยหลักการการออกแบบที่ดีแล้ว ชากับกาแฟควรใช้ปุ่มเดียวกัน โดยอาจจะกำหนด “กด” หมายถึงชา และ “ไม่กด” หมายถึงกาแฟ) ส่วนกระบวนการจะดูว่า input คืออะไร แล้วดำเนินการตาม input เช่น เปิดท่อนั้น ปิดท่อนี้ ผลที่ได้จากกระบวนการเราเรียกว่า output ซึ่งแบบจำลองดังกล่าวสามารถเขียนในรูปสมการอธิบายความสัมพันธ์อย่างง่ายได้ Z = f(T, C, I, M, S) เมื่อ Z คือ output และ Z ε {ชานมร้อนหวาน, ชานมร้อนจืด, ชานมเย็นหวาน, ชานมเย็นจืด, ชาร้อนหวาน, ชาร้อนจืด, ชาเย็นหวาน, ชาเย็นจืด, กาแฟนมร้อนหวาน, กาแฟนมร้อนจืด, กาแฟนมเย็นหวาน, กาแฟนมเย็นจืด, กาแฟดำร้อนหวาน, กาแฟดำร้อนจืด, กาแฟดำเย็นหวาน, กาแฟดำเย็นจืด} ถ้ากำหนดให้ “1” = กดปุ่ม และ “0” = ไม่กดปุ่ม จากโมเดล Z = f(T, C, I, M, S) จะพบว่า f(1, 0, 1, 1, 1) คือ ชานมเย็นหวาน เราเรียกวงจร (หรือกลไก) ที่สร้างจากโมเดลที่มีความสัมพันธ์ “output = f(input)” แบบนี้ว่าวงจร combination นอกจากวงจร combination ยังมีวงจรที่เป็นส่วนสำคัญอย่างยิ่งอีกส่วนหนึ่งในตู้ขายสินค้าอัตโนมัติ นั่นคือวงจร sequential ซึ่งวงจรนี้แหละครับ สร้างจากโมเดลที่เรียกว่า “State Machine”



สมมติว่าค่ากาแฟหรือชาร้อน 5 บาท ถ้าเติมนมต้องเพิ่มเงินอีก 5 บาท ใส่น้ำเชื่อมเพิ่มเงินอีก 5 บาท ใส่น้ำแข็งก็เพิ่มเงินอีก 5 บาท และตู้ขายเครื่องดื่มตู้นี้รับเฉพาะเหรียญ 5 บาทเท่านั้น ถ้าคุณต้องการกาแฟนมเย็นหวาน คุณจะต้องเตรียมเหรียญ 5 บาท 4 เหรียญให้พร้อมก่อนที่จะไปยืนหน้าตู้ กรอบความสนใจของเราอยู่ที่ระบบนับเงินนะครับ เหรียญที่หยอดลงตู้จะผ่านวงจรตรวจจับเหรียญห้าบาท ถ้ามีเหรียญห้าไหลผ่าน วงจรจะส่งข้อความบอกว่า “ใช่เหรียญห้า” (Got 5 Baht = 1) แต่ถ้าเหรียญที่ผ่านไม่ใช่เหรียญห้า วงจรก็จะส่งข้อความบอกว่า “ไม่ใช่เหรียญห้า” (Got 5 Baht = 0) ซึ่งข้อความสองข้อความนี้จะเป็น input ให้กับระบบนับเงิน ส่วน output ของระบบนับเงินก็คือการยินยอมให้กดปุ่ม สมมติว่าคุณหยอดเงินแค่ 10 บาท ตู้ขายเครื่องดื่มก็จะยินยอมให้คุณกดปุ่มเพียง 2 ปุ่ม คือ ปุ่ม T หรือ C (เพื่อเลือกชาหรือกาแฟ) และปุ่มใดอีกปุ่มหนึ่งในกลุ่ม I, M, S (ถ้าอยากกดมากกว่านี้ก็ต้องจ่ายมากกว่านี้) ถ้าเราจะเขียนสมการความสัมพันธ์ของระบบนับเงินโดยเลียนแบบโมเดลของวงจร combination เราจะได้ Z = f(Got 5 Baht) และ Z ε {กดได้ 0 ปุ่ม, กดได้ 1 ปุ่ม, กดได้ 2 ปุ่ม, กดได้ 3 ปุ่ม, กดได้ 4 ปุ่ม} คงเห็นได้ไม่ยากว่า input เพียงตัวเดียวและเป็น input ที่มีเพียงสองสถานะ (digital input) คือ 1 (ใช่เหรียญห้า) และ 0 (ไม่ใช่เหรียญห้า) เพียงแค่นี้ไม่สามารถใช้กำหนด output ที่มีถึง 5 สถานะได้ ในความเป็นจริง เมื่อเราหยอดเหรียญห้าบาทเหรียญแรกลงไปแล้ว ตู้จะยอมให้เรากดได้ 1 ปุ่ม และเมื่อเราหยอดเหรียญห้าบาทเหรียญที่สอง ตู้จะยอมให้เรากดอีก 1 ปุ่ม และเมื่อเราหยอดเหรียญห้าบาทอีกเป็นเหรียญที่สาม ตู้ก็จะยอมให้เรากดเพิ่มอีก 1 ปุ่ม สังเกตตรงนี้ให้ดีนะครับ input ของการหยอดเหรียญแต่ละเหรียญเหมือนเดิม คือ “1” แต่ output ของการหยอดเหรียญแต่ละครั้งไม่เหมือนกัน คือ “กดได้ 1 ปุ่ม”, “กดได้ 2 ปุ่ม” และ “กดได้ 3 ปุ่ม” ตามลำดับ นั่นหมายความว่า output ไม่ได้ขึ้นอยู่กับ input เพียงอย่างเดียว แต่มันขึ้นอยู่กับสถานะ (state) ของมันขณะนั้นด้วย อาจเขียนความสัมพันธ์รูปทั่วไปอย่างง่าย “output = f(input, state)” คำว่า “สถานะ” ในตัวอย่างนี้หมายถึงจำนวนเงินสะสมที่หยอดตู้ ดังนั้นสถานะทั้งหมดที่เป็นไปได้คือ {มีเงิน 0 บาท, มีเงิน 5 บาท, มีเงิน 10 บาท, มีเงิน 15 บาท, มีเงิน ≥ 20 บาท} โมเดลที่เขียนความสัมพันธ์ในรูป “output = f(input, state)” คือ State Machine และวงจร (หรือกลไก) ที่สร้างจากโมเดลนี้เรียกว่าวงจร sequential จากตัวอย่างระบบนับเงินเราสามารถเขียน Z = f(Got 5 Baht, state) เช่น f(1, มีเงิน 15 บาท) คุณก็สามารถกดปุ่มได้ 3 ปุ่ม (เลือกชาหรือกาแฟ 1 ปุ่ม และเลือกกด I, M, S ได้อีก 2 ปุ่ม)

เปรียบเทียบระหว่างวงจร combination หรือโมเดล output = f(input) กับวงจร sequential หรือโมเดล output = f(input, state) ได้ดังแผนภาพ



วิธีที่มีประสิทธิภาพวิธีหนึ่งในการบรรยาย State Machine1 คือการเขียนแผนภาพ State หรือ State Diagram2 ว่ากันตามตรง การแก้ปัญหาโจทย์ลำดับแต้มลูกเต๋าข้อนี้ ผู้อ่านไม่จำเป็นต้องรู้จัก State Machine ก็สามารถเรียนรู้ที่จะวาด State diagram ได้ แต่ผู้เขียนมีความเชื่อว่าถ้าเราเห็นภาพรวมของ State Machine ในมุมกว้าง ก็น่าจะมีประโยชน์และช่วยให้เกิดความกระจ่างในการกำหนด state มากยิ่งขึ้น การวาด state diagram สิ่งที่จำเป็นต้องรู้คือ state ทั้งหมด, input, output และปัจจัยที่ทำให้เกิดการเปลี่ยน state สัญลักษณ์ทั่วไปกำหนดให้วงกลมแทน state แต่ละ state และทิศทางของลูกศรแสดงการเปลี่ยน state จาก state ปลายลูกศรไปสู่ state หัวลูกศร บนเส้นลูกศรจะเขียน input/output กำกับ แผนภาพต่อไปนี้แสดง state diagram ของระบบนับเงินที่มี input คือ {ใช่เหรียญห้าบาท (1), ไม่ใช่เหรียญห้าบาท (0)}, output คือ {กดได้ 0 ปุ่ม, กดได้ 1 ปุ่ม, กดได้ 2 ปุ่ม, กดได้ 3 ปุ่ม, กดได้ 4 ปุ่ม} และ state ทั้งหมด ได้แก่ {มีเงิน 0 บาท, มีเงิน 5 บาท, มีเงิน 10 บาท, มีเงิน 15 บาท, มีเงิน ≥ 20 บาท}



ต่อไปผู้เขียนจะทำให้ State Machine ซับซ้อนขึ้นกว่าเดิมโดยการอัพเกรดตู้นี้ให้สามารถรับเหรียญ 10 บาทเพิ่มขึ้นอีกหนึ่งเหรียญ ฉะนั้น input จะเพิ่มขึ้นจากเดิม คือ 0 = ไม่ใช่เหรียญห้าบาท, 1 = ใช่เหรียญห้าบาท เป็น 0 = ไม่ใช่เหรียญห้าหรือไม่ใช่เหรียญสิบบาท, 1 = ใช่เหรียญห้าบาท, 2 = ใช่เหรียญสิบบาท



1State Machine ที่มีจำนวน state จำกัด มีชื่อเรียกว่า Finite State Machine (FSM) ถ้าหากคุณผู้อ่านมีโอกาสได้ค้นคว้าต่อในวิชา Digital Circuit คุณผู้อ่านจะพบว่า FSM มี 2 ชนิดได้แก่ Moore และ Mealy ซึ่งทั้งคู่แตกต่างกันที่การสร้าง output สำหรับ Moore ค่า output = f(state) ส่วน Mealy ค่า output = f(input, state) ถ้าคุณผู้อ่านเห็น output = f(state) ก็ไม่ต้องแปลกใจว่า input หายไปไหนนะครับ เพราะไม่ว่าอย่างไร state ก็ขึ้นอยู่กับ input นั่นแหละ สำหรับ diagram ที่ผู้เขียนวาดในบทความนี้ยึดตามแบบ Mealy

2State Diagram เมื่อพูดโดยรวม state diagram เป็น diagram ที่ใช้บรรยายพฤติกรรมของระบบ ซึ่งเจอบ่อยในวิชาสาขา Computer Science และ Digital Electronics บุคคลแรกที่บรรยาย FSM ด้วย state diagram คือ Taylor Booth (จากหนังสือ Sequential Machines and Automata Theory) นักคณิตศาสตร์ผู้มีผลงานโดดเด่นในทฤษฎี automata


ปัญหาลำดับแต้มจากการทอยเต๋า

กลับไปที่ผู้เล่นเกม ฌาณกับโน้ต ถ้าดูเพียงผิวเผินเหมือนกับโจทย์ถามเราว่าโอกาสเกิด “12” กับโอกาสเกิด “11” เท่ากันหรือไม่? อย่าหลงกลโจทย์แล้วรีบตอบว่าเท่ากันนะครับ แน่นอนว่าโอกาสเกิด “1” ตัวแรกของฌาณกับโน้ตเท่ากัน ระยะเวลาที่รอให้ออกแต้ม 1 (หรือจำนวนทีที่รอ) ก็ควรที่จะเท่ากัน สมมติว่าทั้งคู่ได้ 1 ตัวแรกมาครอบครองกันแล้ว ตอนนี้โน้ตกำลังรอ “1” ตัวที่สอง ซึ่งมีโอกาสเกิดขึ้นเท่ากับ 1/6 และฌาณก็รอ “2” มีโอกาสเกิดขึ้นเท่ากับ 1/6 เท่ากัน สำหรับทั้งคู่ โอกาสไม่ออก 1 ก็เท่ากับโอกาสที่ไม่ออก 2 คือ 5/6 ถ้าในการทอยครั้งนี้ โน้ตไม่ได้ “1” เขาจะต้องเริ่มต้นรอ “1” ตัวแรกใหม่ ในขณะที่ฌาน ถึงแม้ว่าในการทอยครั้งนี้จะไม่ได้ “2” แต่ถ้าฌาณได้ “1” เขาก็ยังสามารถคงสถานะรอ “2” เอาไว้เหมือนเดิมได้ จุดนี้เป็นข้อได้เปรียบของฌานที่ทำให้เราสามารถสรุปได้ว่า ฌาณจะใช้จำนวนครั้งที่ทอยน้อยกว่าโน้ต

ได้เวลาคำนวณตัวเลขออกมากันแล้วครับ ระหว่างจำนวนครั้งที่ทอยของฌาณกับโน้ต ใครจะได้เท่าไร? และมากน้อยกว่ากันเท่าไร? เริ่มจากเขียน state diagram สำหรับกลไกการรอ “11” ของโน้ต input คือแต้มที่ออกจากการทอยเต๋า {1, 2, 3, 4, 5, 6}, output มี 2 สถานะคือ {เล่นต่อ, จบเกม} และมี 3 states {รอ “1” ตัวที่ 1, รอ “1” ตัวที่ 2, หยุด}



ถ้ากำหนดให้ที่ state เริ่มต้น (S0) โน้ตจะต้องทอยเต๋า W ครั้งจึงจะได้ลำดับ “11” (S2) และโอกาสที่ทอยเต๋าได้ 1 เท่ากับ p = 1/6 เราสามารถเขียนความสัมพันธ์

W = (1-p)(W+1) + (p)[(1-p)(W+2) + 2p]

อธิบายสมการ: มีทางออกจาก S0 สองทาง ทางแรกคือกลับมายัง S0 ที่เดิม มีโอกาส 1-p และในเมื่อมันยังอยู่ที่ S0 ณ จุดนี้จึงใช้เวลารอเท่าเดิม (W) จนกว่าจะจบเกม (อย่าลืมว่าคุณต้องทอยเต๋าแล้ว 1 ครั้งจึงกลับมาที่จุดนี้ได้นะครับ) อีกทางคือไปต่อยัง S1 มีโอกาส p และที่ S1 มีโอกาส 1-p จะกลับไปที่ S0 (ถ้ากลับไปรอบนี้แปลว่าทอยเต๋ามาแล้ว 2 ครั้ง) และมีโอกาส p ที่จะถึง S2 (เราทอยเต๋า 2 ครั้ง)

เนื่องจากเป็นสมการตัวแปรเดียว สามารถแก้สมการได้ W = (1+p)/p2 = 42 ดังนั้นค่าคาดหมายจำนวนครั้งที่ทอยเต๋าของโน้ตเท่ากับ 42 ครั้ง ทำนองเดียวกัน วาด state diagram ของฌานได้ดังรูป



กำหนดให้ W0 แทนค่าคาดหมายของจำนวนครั้งที่ทอยเต๋าเมื่ออยู่ S0 กระทั่งได้ลำดับ “12” (หรือถึง S2), W1 แทนค่าคาดหมายจำนวนครั้งที่ทอยเต๋าเมื่ออยู่ S1 จนถึง S2 และ p แทนโอกาสทอยเต๋าได้แต้ม 1

W0 = (1-p)(W0+1) + (p)(W1+1)
W1 = (p)(W1+1) + (1-2p)(W0+1) + (p)(1)

แก้ระบบสมการหาค่า W0 = 36 ดังนั้นค่าคาดหมายจำนวนครั้งที่ทอยเต๋าของฌาณเท่ากับ 36 ครั้ง น้อยกว่าโน้ตถึง 6 ครั้ง เป็นไงบ้างครับ คุณผู้อ่านคิดว่าโจทย์ลักษณะนี้ ใช้ state diagram ช่วยให้เราเห็นภาพได้ชัดเจนยิ่งขึ้นและสามารถวิเคราะห์ความสัมพันธ์ได้ง่ายขึ้นบ้างมั้ยครับ?




Create Date : 12 กรกฎาคม 2552
Last Update : 12 กรกฎาคม 2552 11:47:16 น.
Counter : 6341 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

ศล
Location :
กรุงเทพ  Thailand

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด