ห้องทดลอง
Scrabble Engine

Node, edge และ terminal flag

การ insert CAT เริ่มจาก root แล้วเดินหรือสร้าง edge C, A และ T จากนั้น mark T เป็น terminal การ insert CAR ใช้ C และ A ร่วมกัน สร้าง R แล้ว mark terminal การค้นคำสำเร็จเมื่อ edge ครบทุกตัวและ node สุดท้ายเป็น terminal ส่วน prefix search ไม่ต้องตรวจ terminal

INSERT(word):
  node = root
  for ch in word:
    node = node.child.get_or_create(ch)
  node.terminal = true

CONTAINS(word):
  follow every edge; return final.terminal

การเดินบนกระดานต่างจาก lookup อย่างไร

ที่ช่องว่าง traversal แตกกิ่งเฉพาะ child ที่มีใน rack และผ่าน cross-check mask ส่วนช่องที่มีตัวอยู่แล้วจะเดินตามตัวนั้นโดยไม่ใช้ rack ดังนั้น state ประกอบด้วย Trie node, ตำแหน่งกระดาน, multiset ที่เหลือ, ตัวที่วาง และสถานะว่าครอบ anchor แล้วหรือยัง

EXTEND(node, square, rack):
  if square is fixed: follow its one edge
  else for child in node.children:
    if rack has child AND crossMask allows child:
      consume tile; recurse
  emit only terminal states covering an anchor

Complexity: exact lookup เป็น O(L) แต่ move generation เป็น output-sensitive ขึ้นกับจำนวน anchor A, branching b, rack states และคำตอบ Z ไม่ใช่เพียง O(L)

Anagram key จากจำนวนเฉพาะ

กำหนดจำนวนเฉพาะต่างกันให้แต่ละตัว A=2, B=3, C=5, …, Z=101 แล้วคูณ prime ของทุกตัว ทฤษฎีการแยกตัวประกอบเฉพาะทำให้ anagram มีผลคูณเดียวกัน เช่น ABBA และ BABA เท่ากับ 2²×3²=36 ส่วน multiset อื่นให้จำนวนเต็มอื่น

primeKey("LISTEN")
= p[L] × p[I] × p[S] × p[T] × p[E] × p[N]
= primeKey("SILENT")

วิธีนี้เหมาะสำหรับการสอน แต่ผลคูณ 64-bit อาจ overflow และการ mod ด้วยขนาดตารางทำให้เกิด collision จึงยังต้องเปรียบเทียบ signature ต้นฉบับเมื่อ key ชนกัน

Representation ที่ระบบจริงใช้

Engine เก็บจำนวนตัวอักษร 26 ค่า เนื่องจาก count ต่อตัวมีขนาดเล็ก จึง pack count 4-bit สองค่าต่อหนึ่ง byte ทำให้ 26 ค่าเป็น key 13 bytes ที่ไม่เสียข้อมูล จากนั้น FNV-1a 64-bit เลือก slot ใน open-addressed table, ใช้ linear probing เมื่อชน และเปรียบเทียบครบทั้ง 13 bytes ก่อนยอมรับ hit

offset = 1469598103934665603
for byte in packedSignature:
  hash = (hash XOR byte) × 1099511628211
slot = hash AND (capacity − 1)
while occupied AND key != storedKey:
  slot = (slot + 1) AND (capacity − 1)

Average: probe O(1) เมื่อควบคุม load factor; Worst case: O(M) หาก clustering บังคับให้ไล่ตาราง

กำหนดตำแหน่ง rack เป็น 0…R−1 จำนวนเต็ม mask m เลือกตำแหน่ง i เมื่อ bit i เป็น 1 การวนจาก 1 ถึง 2ᴿ−1 สร้าง position subset ที่ไม่ว่างครบหนึ่งครั้ง จากนั้น canonical signature รวมกรณีที่ต่างกันเพียงสลับตัวอักษรซ้ำ

for mask = 1 .. (1 << R) - 1:
  counts = [0] × 26; blanks = 0
  for i = 0 .. R - 1:
    if mask & (1 << i):
      add rack[i] to counts or blanks
  signatures.add(counts, blanks)

เลือก Leave-one-out หรือ bit mask?

ทำไมใช้ WITHOUT ROWID?

ปกติ SQLite มี integer rowid ซ่อนอยู่และมี primary-key index แยก แต่ signature BLOB เป็นทั้ง identity และ access path อยู่แล้ว WITHOUT ROWID จึงเก็บแถวใน primary-key B-tree ลด identity และ lookup ที่ซ้ำซ้อน

Database กับ runtime hash table

SQLite durable, portable และ rebuild ง่าย แต่ B-tree lookup เป็น O(log S) ไม่ใช่ hash จริง เมื่อ worker เริ่มทำงานจึงโหลดทุกแถวเข้า compact NumPy arrays และ open-addressed table SQLite เป็น source of truth ส่วน in-memory tableเป็น hot read path

การสุ่มแบบไม่คืนกลับ

การหยิบตัวอักษรไม่เป็นอิสระ เพราะหยิบ S หนึ่งตัวแล้วโอกาส S ตัวต่อไปเปลี่ยน Binomial จึงเป็นเพียง approximation ส่วน Hypergeometric นับ rack ขนาด d จาก unseen N ตัวที่มี useful tile K ตัวได้ตรงกับการสุ่มแบบไม่คืนกลับ

P(X=x) = C(K,x) C(N−K,d−x) / C(N,d)
P(X≥1) = 1 − C(N−K,d) / C(N,d)

สำหรับ extension หลายตัว เช่น ING Engine ใช้ multivariate count โดย I, N และ G ที่ต้องใช้ต้องมีครบ และ blank เป็นทรัพยากรทดแทน

Expected value ไม่ใช่สิ่งที่จะเกิดแน่นอน

การตอบโต้ 40 คะแนนที่มีโอกาส 0.20 ให้ Risk EV 8 ไม่ได้ทำนายว่าคู่แข่งจะได้ 8 คะแนน แต่หมายถึงโจทย์เทียบเท่าที่เล่นซ้ำเสียเฉลี่ย 8 คะแนน Variance ยังสำคัญ: policy แบบ risk-neutral เปรียบเทียบค่าเฉลี่ย ส่วน risk-averse อาจลงโทษ tail loss หรือ conditional value-at-risk

สัญญาของ public endpoint

POST /pages/scrabble-api.php
Content-Type: application/json

{
  "board": [15 strings × 15 cells],
  "rack": "AEINRST",
  "limit": 20,
  "engine": "trie" | "sqlite-hash" | "memory-hash"
          | "compact-numba" | "prime-product",
  "adversarial": true
}

response คืน identity ของ lexicon, timing, engine statistics, unseen probabilities และรายการ moves แต่ละ move มีพิกัด ทิศทาง ตัวที่วางใหม่ คะแนน และ heuristic decomposition เมื่อร้องขอ

สัญญาของ worker ภายใน

GET  /health
→ status, backend, signatures,
  table_bytes, startup_ms

POST /candidates
{ "board": [...], "rack": "AEINRST" }
→ words, hash_lookups, hash_hits,
  signature_ms, hash_query_ms,
  worker_ms, cache_hit

FastAPI ตรวจว่ากระดานมี 15 แถว ASCII และ rack ยาว 1–7 ตัว worker โหลด 237,740 signatures ครั้งเดียวตอน lifespan startup และ JIT-compile Numba probe ครั้งเดียว จากนั้น request ปกติไม่ rebuild index