CS 410/510 Games: Getting Started

Getting Started In Combinatorial Games

PSU CS410/510GAMES Lecture 2
April 11, 2002

  • Game SE 1: Fundamentals
    • The Software Engineering ``Lifecycle''
      • Requirements Collection and Analysis: What are we doing?
      • Architecture and Detailed Design: How are we doing it?
      • Coding: Doing it
      • Verification and Validation: Did we do it?
      • Maintenance: Making it stay done
    • The Game SE Lifecycle
      • Requirements: Rules, Performance, System
      • Architecture: Common among most games
        • State representation (size vs. complexity vs. performance)
        • Search methodology (usually recursive DFS: iterations?)
        • UI (interactions with other components?)
      • Detailed Design: The missing piece
      • Coding
        • On the importance of constant/poly factors
        • Clean code
        • Instrumentation
      • Verification and Validation
        • Unit Test: very important
        • System Test: library of test cases
        • Inspection: individual and group
      • Maintenance
        • Most commercial and academic game software not reproducible!
        • Good maintenance: RCS/CVS, root cause analysis, refactoring
        • Verifying maintenance changes: regression testing
        • Nondeterminism and PRNGs
      • Special Considerations In Game SE
        • Bottlenecking: CPU vs. cache vs. RAM?
        • Correctness, completeness, V&V, and search
        • Asymptotic complexity matters!
        • Clarity
    • Example: Aces Up
      • What are we doing, really?
        • Upper-bounding the win rate
        • Nailing down the rules
      • How will we do it?
        • Architectural design
        • Detailed design: shuffle, search
      • Do it: coding Aces Up
      • Did we do it?: testing
        • Testing the shuffle
        • Testing the search: small cases
        • Validating against requirements
  • The Perfect Shuffle
    • Naive algorithms
      • swap every slot once: not even
      • riffle: min 14 riffles for randomness
      • attach random numbers and sort: clumsy
    • Doing it right in 3 easy steps
      • Requirements: defn ``random shuffle''?
        • uniform prob. of each card at each spot
        • implies inductive defn: first card random followed by random shuffle of remainder
      • 1: ``selection shuffle''
      • 2: avoiding the array slide
      • 3: avoiding the extra array
      • Shuffle implements definition
      • Up or down?
    • PRNGs and the limits of shuffling
      • LC and LFSR generators
      • Using enough bits
      • End effects
      • 2-player games and ``crypto shuffles''
      • ``Mental poker'' (Goldwasser & Micali)