About AIR

• Restarting after the founder moved to DC.

About AIR

• Restarting after the founder moved to DC.

• Project focused, mentoring focused.

About AIR

• Restarting after the founder moved to DC.

• Project focused, mentoring focused.

• We're interested in the nitty gritty.

• Used a new language? Great.
• Used a cool library? Fine.

About AIR

• Restarting after the founder moved to DC.

• Project focused, mentoring focused.

• We're interested in the nitty gritty.

• Used a new language? Great.

• Used a cool library? Fine.

• Tell us what you built with it.

Tic-Tac-Toe

• A game of Tic-Tac-Toe.

Tic-Tac-Toe

• A game of Tic-Tac-Toe.

• With AI! (wow)

Tic-Tac-Toe

• A game of Tic-Tac-Toe.

• With AI! (wow)

• We remember Tic Tac Toe, right?

Tic-Tac-Toe

• A game of Tic-Tac-Toe.

• With AI! (wow)

• We remember Tic Tac Toe, right?

• It's a special case of m,n,k games.

• But specifics are pedagogically helpful.

• Disclaimer: I have not tried my algorithm on arbitrary m,n,k games.

Enter Tock

• Tock on github.

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

• The following objects:

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

• The following objects:

  • Board

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

• The following objects:

  • Board

  • Human, Computer, SuperComputer

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

• The following objects:

  • Board

  • Human, Computer, SuperComputer

  • TicTacToe

Enter Tock

• Tock on github.

• Loose feature overview:

  1. Any mixture of 2 Human/Computer/SuperComputer players.

  2. Any NxN board size. (Diagonal wins only supported on odd boards.)

  3. Some tests I guess. (Yeah, not really a feature.)

• The following objects:

  • Board

  • Human, Computer, SuperComputer

  • TicTacToe

  • Menu

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

• Final Disclaimer: I wrote all this code in about 5 hours Sunday and last night.

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

• Final Disclaimer: I wrote all this code in about 5 hours Sunday and last night.

The core idea is pretty simple actually ...

1. Write a scoring function for your game state.

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

• Final Disclaimer: I wrote all this code in about 5 hours Sunday and last night.

The core idea is pretty simple actually ...

1. Write a scoring function for your game state.

2. Recursively enumerate all possible future game states.

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

• Final Disclaimer: I wrote all this code in about 5 hours Sunday and last night.

The core idea is pretty simple actually ...

1. Write a scoring function for your game state.

2. Recursively enumerate all possible future game states.

3. ???

Enter Minimax (jk Negamax)

• Disclaimer: I threw these slides together this afternoon. Expect whiteboarding.

• Final Disclaimer: I wrote all this code in about 5 hours Sunday and last night.

The core idea is pretty simple actually ...

1. Write a scoring function for your game state.

2. Recursively enumerate all possible future game states.

3. ???

4. PROFIT!

Uhhh....

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

• Those states have their own future states based on the opponent's move and so on.

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

• Those states have their own future states based on the opponent's move and so on.

• We build the "Game Tree" then we just have to walk up and down it and figure out the move with the "best score".

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

• Those states have their own future states based on the opponent's move and so on.

• We build the "Game Tree" then we just have to walk up and down it and figure out the move with the "best score".

• Recursion is a natural fit for tree traversal.

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

• Those states have their own future states based on the opponent's move and so on.

• We build the "Game Tree" then we just have to walk up and down it and figure out the move with the "best score".

• Recursion is a natural fit for tree traversal.

• Not a super common technique in Ruby. You can blow the stack if you're not careful.

Okay

• Every "Game State" can lead to a number of possible future states based on how a player chooses to move.

• Those states have their own future states based on the opponent's move and so on.

• We build the "Game Tree" then we just have to walk up and down it and figure out the move with the "best score".

• Recursion is a natural fit for tree traversal.

• Not a super common technique in Ruby. You can blow the stack if you're not careful.

• (Recent Rubies do support Tail Call Optimization, not sure how involved this is.)

Game Theory

• Y'all saw A Beautiful Mind, right?

Game Theory

• Y'all saw A Beautiful Mind, right?

• Minimax works because Tic Tac Toe is a Zero-Sum game with perfect information.

Game Theory

• Y'all saw A Beautiful Mind, right?

• Minimax works because Tic Tac Toe is a Zero-Sum game with perfect information.

• God we are so smart.

So I've heard of Minimax, Why Negamax?

• Really just a coding simplification.

• Has to do with how we track the scores for alternating players.

How to Test Negamax Mo Betta

1. Test prevention of forks. If the opponent forks, we've lost already.

   (Sidebar: How many ways can you set up a fork?)

How to Test Negamax Mo Betta

1. Test prevention of forks. If the opponent forks, we've lost already.

   (Sidebar: How many ways can you set up a fork?)

2. Test that we block opponent wins.

How to Test Negamax Mo Betta

1. Test prevention of forks. If the opponent forks, we've lost already.

   (Sidebar: How many ways can you set up a fork?)

2. Test that we block opponent wins.

3. Test that we take available wins.

Optimization

• Well, run Rubinius (currently not installable on Yosemite T_T).

Optimization

• Well, run Rubinius (currently not installable on Yosemite T_T).

• Or rewrite it in: C, Lisp, OCaml, etc.

Optimization

• Well, run Rubinius (currently not installable on Yosemite T_T).

• Or rewrite it in: C, Lisp, OCaml, etc.

• "Here's a nickel kid, get yerself a real programming language."

Optimization

• Well, run Rubinius (currently not installable on Yosemite T_T).

• Or rewrite it in: C, Lisp, OCaml, etc.

• "Here's a nickel kid, get yerself a real programming language."

• ^^ #jerk

Optimization, pt. 2

Use a better algorithm!

• Look into Alpha-Beta Pruning.

Optimization, pt. 2

Use a better algorithm!

• Look into Alpha-Beta Pruning.

• Look into Principal Variation Search.

Optimization, pt. 2

Use a better algorithm!

• Look into Alpha-Beta Pruning.

• Look into Principal Variation Search.

• Both are fundamentally about limiting how much of the Game Tree you have to search.

Questions?