xo

A Ruby library for Tic-tac-toe.

Performance of the Minimax Algorithm

require 'benchmark'
require 'xo'

# Empty grid
g = XO::Grid.new

puts Benchmark.measure { XO::AI.minimax(g, :x) }
# => 0.000000   0.000000   0.000000 (  0.000463)
# => O(1) time due to caching

# One spot taken
g[1, 1] = :x

puts Benchmark.measure { XO::AI.minimax(g, :o) }
# => 0.000000   0.000000   0.000000 (  0.000216)
# => O(1) time due to caching

# Two spots taken
g[1, 3] = :o

puts Benchmark.measure { XO::AI.minimax(g, :x) }
# => 0.690000   0.000000   0.690000 (  0.695095)
# => Worst-case time, performance only improves from here on as the grid gets filled

Testing

You can run:

  • All tests: rake test
  • One test: ruby -Ilib -Ispec spec/path_to_spec_file.rb

TODO

  1. Write documentation.
  2. Show example usage.
  3. Write an example Tic-tac-toe command-line game client.

Contributing

If you'd like to contribute a feature or bugfix: Thanks! To make sure your fix/feature has a high chance of being included, please read the following guidelines:

  1. Post a pull request.
  2. Make sure there are tests! I will not accept any patch that is not tested. It's a rare time when explicit tests aren't needed. If you have questions about writing tests for xo, please open a GitHub issue.

License

xo is Copyright © 2014 Dwayne R. Crooks. It is free software, and may be redistributed under the terms specified in the MIT-LICENSE file.