Transcript Quoridor Classic Game Manager v.1.0

Quoridor Classic Game
Manager
Kevin Dickerson
April 2004
System Overview
• Goal
– Develop a system for managing games of Quoridor
Classic over a network
– Real-time interactive graphics
– Open network protocol
• Why
– To allow students a way to play Quoridor Classic
without having to write their own game manager!
– Hopefully nicer than old text-mode managers that
may have been confusing, hard to use
– Simplifies software development process for AI!
The Board Game
• “Real” board game for two
players
• A typical “western” (tile-based)
board game.
• 9x9 tiles
• Each player starts with 10
walls
• Each turn, a player moves his
pawn to an adjacent tile, or
places one wall on the board.
• Moves may be timed.
• Objective is to get to the
opposite side of the board first!
Quoridor Classic Game Manager
(QCGM)
• Fully implements the board game Quoridor
Classic’s rules for two players!
• Allows players to play “hotseat,” or through
a common network protocol.
• Allows anyone to write their own AI
module to control a client.
Special Use
• AI students will write their own client
software that will communicate with my
software.
• Simplified example of communication:
– Client 1: “move up”
– Client 2: “place a horizontal wall at tile x, y”
– Etc…
– QCGM does the validation!
Game Manager Software
• Has several modes:
– Stand-alone Server Mode
– Interactive Client/Server Mode
– Interactive Client Mode
Stand-alone Server Mode
• Two remote clients connect to the server.
The game may be observed, but not
interacted with.
Interactive Client/Server Mode
• The software acts as both server and
client for one or two players.
• Example:
– You are Player 1 (sitting at the server).
• When it is your turn, you click and drag objects to
make your move.
– Player 2 is a remote client.
• Player 2 is controlled via the network through
either another instance of QCGM, or by AI
software!
Interactive Client Mode
• Client connects to a remote server running
the QCGM software.
• You observe your opponent’s move until it
is your turn.
• You control only your game piece.
Components
Components
• Main Form
– OpenGL Pane
– Menu Bar
– Status Bar
• Start New Game Form
– Host a game
• Join Game Form
– Connect to remote server
• Console Form
– View traffic, messages
(Don’t worry, final version
will be much less purple!)
Algorithms Used
• Dijkstra’s algorithm
– Finds the shortest path from a source node to
all other nodes in a graph.
– Complexity:
• O(E lg V) if no nodes are “sealed off” by walls
• Where,
– |E| is the total number of edges in all adjacency lists
– and |V| is the number of vertices (or nodes)
Algorithms Used, cont.
• Dijkstra’s, continued:
– In QCGM, each tile is a node, the board is a
directed edge graph. Placing a wall removes
an edge!
– Chosen because players may “win” by
reaching any tile in a row across the edge of
the board.
• Side effect: If no walls left, computer may know
who will win before the players do!
Algorithms used, cont.
• Other algorithms I won’t cover today:
• Arcball (boring)
Built Using:
• Microsoft Visual Studio .NET 2003
• C#
• OpenGL (via “Tao Framework,” a C#
OpenGL wrapper)
• Windows Forms GUIs
• Asynchronous Sockets using TCP/IP
Software Features (i.e.
Requirements met)
•
•
•
•
Pretty nice 3D graphics (uses OpenGL)
Moveable camera uses “arcball” method
Click/drag interface for placing moves
Dijkstra’s shortest path algorithm for move
validation
• Sockets using TCP/IP to communicate
moves over an open (and documented)
network protocol
Difficulties Had
• This project was a black hole for time!
– Spent too much time learning C#,
Sockets/Networking, Visual Studio .NET
– Development of network model had a
tendency to lean towards more complicated
than simplified, several classes required
rewriting/significant changes
– I ended up writing about 90
classes/structures! (Is there such a thing as
too object-oriented?)
“Nice to Have” Features that Did
Not Make It
• “Tournament Mode”
– A number of clients connect all at once, and
are queued to play games. Results are
recorded.
• Cryptography
– Would unnecessarily complicate network
traffic! Not so nice to have after all…
Changes During Development
• Ditched internal “game protocol
communication” idea, just used OO
methods!
• Ditched message packets early on and
just used strings – much easier!
• Simplified network model (no
acknowledgement required)
Things I’d Like to Change
• A more solid network model.
– Right now it is not very forgiving! Errors tend
to lead to disconnections.
– I would probably use a “difference” network
protocol, where the server sends the state of
the board, rather than individual moves. Right
now, it is conceivably possible for moves to be
dropped on the client side.
Things I’d Like to Change (cont.)
• Better OpenGL Graphics
– Not necessary, but adding textures or lighting
would be nice!
• Game Records
– Would store in a chess-like move record with
tables rather than an array of commands.
Questions?