Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualParadigm Shifter

Posted 01 April 2013 - 03:01 AM

I'll just comment on the AI part (none of the AI except maybe tic tac toe can be done with a series of switch or if/else statements)

  • Go

Very hard, you can't use standard tree search (minimax and related algorithms) to generate lots of potential moves and evaluate how good they are after looking ahead, since the number of moves that can be made each turn is enormous (far more than in chess or checkers). This is an ongoing AI research problem and the best human players can still tonk the AI...

 

  • Hangman

This involves having a large dictionary of potential words if you want the computer to guess the word. Eliminate large parts of the dictionary after the result of each guess (best strategy is to try and eliminate the most words from the dictionary regardless of whether your guess is correct or not, also guess common letters first, etc.). If you see a new word, add it to the dictionary. Not too hard.

 

EDIT: You can use statistics for this, for each letter that is a potential guess calculate the expected value of the number of words that will be removed from the dictionary, and pick the one with the highest expected value.

 

  • Tic-Tac-Toe

Or "my first minimax algorithm implementation". Easy. You can also do it by hard coding in a perfect strategy, but that only applies to tic tac toe and not other 2 player games with perfect information like chess/checkers etc.

 

  • Chess

Hard to get it to play well, there are lots of forums about it and you probably want to ask Alvaro questions in the AI forum. Uses variants of minimax along with large databases of opening moves and endgame databases as well.

 

  • Connect Four

 

Minimax again should get this to play fairly well. It has been solved (i.e. computer algorithm exists which plays perfectly) recently

 

EDIT: I think the standard board size has been solved but larger boards still remain open research

 

  • Battleship

This is more about distributing your shots to find all the ships in the most optimal way but I suspect for every strategy there may be a counter strategy for ship placement...

 

  • Checkers

Easier than chess and harder than Connect 4, same sort of principles (i.e. minimax based) apply. I think this was solved fairly recently as well...


#3Paradigm Shifter

Posted 01 April 2013 - 03:00 AM

I'll just comment on the AI part (none of the AI except maybe tic tac toe can be done with a series of switch or if/else statements)

  • Go

Very hard, you can't use standard tree search (minimax and related algorithms) to generate lots of potential moves and evaluate how good they are after looking ahead, since the number of moves that can be made each turn is enormous (far more than in chess or checkers). This is an ongoing AI research problem and the best human players can still tonk the AI...

 

  • Hangman

This involves having a large dictionary of potential words if you want the computer to guess the word. Eliminate large parts of the dictionary after the result of each guess (best strategy is to try and eliminate the most words from the dictionary regardless of whether your guess is correct or not, also guess common letters first, etc.). If you see a new word, add it to the dictionary. Not too hard.

 

EDIT: You can use statistics for this, for each letter that is a potential guess calculate the expected value of the number of words that will be removed from the dictionary, and pick the one with the highest expected value.

 

  • Tic-Tac-Toe

Or "my first minimax algorithm implementation". Easy. You can also do it by hard coding in a perfect strategy, but that only applies to tic tac toe and not other 2 player games with perfect information like chess/checkers etc.

 

  • Chess

Hard to get it to play well, there are lots of forums about it and you probably want to ask Alvaro questions in the AI forum. Uses variants of minimax along with large databases of opening moves and endgame databases as well.

 

  • Connect Four

 

Minimax again should get this to play fairly well. It has been solved (i.e. computer algorithm exists which plays perfectly) recently

 

  • Battleship

This is more about distributing your shots to find all the ships in the most optimal way but I suspect for every strategy there may be a counter strategy for ship placement...

 

  • Checkers

Easier than chess and harder than Connect 4, same sort of principles (i.e. minimax based) apply. I think this was solved fairly recently as well...


#2Paradigm Shifter

Posted 01 April 2013 - 02:58 AM

I'll just comment on the AI part (none of the AI except maybe tic tac toe can be done with a series of switch or if/else statements)

  • Go

Very hard, you can't use standard tree search (minimax and related algorithms) to generate lots of potential moves and evaluate how good they are after looking ahead, since the number of moves that can be made each turn is enormous (far more than in chess or checkers). This is an ongoing AI research problem and the best human players can still tonk the AI...

 

  • Hangman

This involves having a large dictionary of potential words if you want the computer to guess the word. Eliminate large parts of the dictionary after the result of each guess (best strategy is to try and eliminate the most words from the dictionary regardless of whether your guess is correct or not, also guess common letters first, etc.). If you see a new word, add it to the dictionary. Not too hard.

 

  • Tic-Tac-Toe

Or "my first minimax algorithm implementation". Easy. You can also do it by hard coding in a perfect strategy, but that only applies to tic tac toe and not other 2 player games with perfect information like chess/checkers etc.

 

  • Chess

Hard to get it to play well, there are lots of forums about it and you probably want to ask Alvaro questions in the AI forum. Uses variants of minimax along with large databases of opening moves and endgame databases as well.

 

  • Connect Four

 

Minimax again should get this to play fairly well. It has been solved (i.e. computer algorithm exists which plays perfectly) recently

  • Battleship

This is more about distributing your shots to find all the ships in the most optimal way but I suspect for every strategy there may be a counter strategy for ship placement...

 

  • Checkers

Easier than chess and harder than Connect 4, same sort of principles (i.e. minimax based) apply. I think this was solved fairly recently as well...


#1Paradigm Shifter

Posted 01 April 2013 - 02:57 AM

I'll just comment on the AI part (none of the AI except maybe tic tac toe can be done with a series of switch or if/else statements)

  • Go

Very hard, you can't use standard tree search (minimax and related algorithms) to generate lots of potential moves and evaluate how good they are after looking ahead, since the number of moves that can be made each turn is enormous (far more than in chess or checkers)

 

  • Hangman

This involves having a large dictionary of potential words if you want the computer to guess the word. Eliminate large parts of the dictionary after the result of each guess (best strategy is to try and eliminate the most words from the dictionary regardless of whether your guess is correct or not, also guess common letters first, etc.). If you see a new word, add it to the dictionary. Not too hard.

 

  • Tic-Tac-Toe

Or "my first minimax algorithm implementation". Easy. You can also do it by hard coding in a perfect strategy, but that only applies to tic tac toe and not other 2 player games with perfect information like chess/checkers etc.

 

  • Chess

Hard to get it to play well, there are lots of forums about it and you probably want to ask Alvaro questions in the AI forum. Uses variants of minimax along with large databases of opening moves and endgame databases as well.

 

  • Connect Four

 

Minimax again should get this to play fairly well. It has been solved (i.e. computer algorithm exists which plays perfectly) recently

  • Battleship

This is more about distributing your shots to find all the ships in the most optimal way but I suspect for every strategy there may be a counter strategy for ship placement...

 

  • Checkers

Easier than chess and harder than Connect 4, same sort of principles (i.e. minimax based) apply. I think this was solved fairly recently as well...


PARTNERS