how to make Checkers AI 2 moves ahead - artificial-intelligence

I made a simple checkers game based on 2d arrays. I now want to make an AI for this. How do I make a function that looks 2 or 3 moves ahead and evaluate the best move based on this?

Related

How to calculate Heuristic values for minimax

I am developing a software for a board game (2 player) which has 10x4 cells and both the players have 9 pieces each. Initially, the pieces for player 1 will be at the top of the board and for player 2 all the pieces will be at the bottom of the board (similar to chess but a lot less complex!).
I have used MiniMax algorithm to calculate the next best move. Now, the algorithm itself seems to work fine. The problem that I am facing is in Heuristic value calculation.
If there is no best move found in the depth till I am searching (4 currently), my code simply takes the first step which it finds from the move list. That is probably because the score of all the moves are same till the depth of 4!
So, it just keeps stalling. Eg., it will move piece 1 from position A to B in 1st turn and in the 2nd turn it will move the same piece from position B to A.
It keeps on doing that until the opponent moves closer to my pieces.
Now, what I want would love to know is how do I make sure that if the opponent is NOT closing in, I do that instead of stalling.
Currently, I am calculating the heuristic values based on the difference between my pieces and opp pieces.
How to calculate the values such that those moves which lead to position closer to the opponent's pieces are selected? Appreciate your help! Thanks!

minimax for tic-tac-toe

I'm trying to solve tic-tac-toe with a simple minimax algorithm. Simple, but should cover a lot of the language. What I have so far:
The board is represented as an array of 9 (unbound) variables, that are either set to x or o.
The win condition is then basically: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. etc for all eight variants. draw is just a simple check whether all variables are bound.
The move clauses are also simple: move(Player, [X|_], 0, 0) :- var(X), X=Player., again for all possible positions (I'll leave code reuse open for a later program :) ).
Now I can generate all possible moves by simple backtracking: move(Player, Board, X, Y). which should basically be all what I need for minimax (obviously a simple utility function that returns 1 if the computer wins, 0 in case of a draw and -1 if the human wins, that's easy). I just have no idea how to implement it and all examples I find on the net are rather complicated and not well explained.
Note I'm fine with n^2 or worse runtime behavior - it's really not about efficiency. And yes I do know how to write minimax in lisp, python, java - just no idea how to "port" that code to prolog.
Well, as you already have your move/4 predicate, I would start with collecting all moves that are possible:
findall(X-Y, move(Player, Board, X, Y), Moves)
And then it's simply a matter of assessing each move, isn't it? For that I would write a predicate like board_player_move_value/4 that, given a board and a move of a given player, determines how good the move is for this player. It is this predicate that likely depends on further moves that are possible (for the other player) at this stage, and this is where minimax takes place. For example, if this move wins the game, it's a good move. If the other player can win in the next move, it's a bad move etc. I would use this predicate to build a collection of terms of the form Value-Move, use keysort/2 to sort them, and then pick one of the moves with the best value, where "best" depends on whether I'm trying to find a move for the minimizing or the maximizing player.

How to approach writing five-in-a-row Tic Tac Toe game AI?

I was challenged by coworker into creating a Tic Tac Toe game AI that plays five-in-a-row games (not the traditional 3). My initial thoughts are that I create a "scoreboard", i.e. every cell in the game gets a score between 0 and infinite. The AI finds shapes and determines which places hold how much value and give score to the cells. In the end, highest scored cell is the choice.
Is there a better way to approach this problem?
5x5 Tic-Tac-Toe might still be small enough to solve directly, depending on your time constraints, if you're clever about the board symmetries. Oddly enough, I just wrote a description of the general technique last night, for this question:
How to code simple AI for a windows phone board game?
If not, that's still a good starting point. The next most obvious thing to me would be to change the board evaluation function and search only as deep in the tree as is feasible for your time constraints. The idea is that you, as a human, might have some ideas about what strong and weak positions are. So, as a guess, we know five in a row wins, so assign X wins as +5 and O wins as -5. One way to win is to get four in a row prior to that, so if X has four in a row, that might be worth 4, and if O has four in a row, that might be worth -4. The idea is that if you can't search all the way down the tree, you search as far as you can with the minimax technique, confident that you're working your way toward a strong position.
That board eval function is only an example. Coming up with a good board evaluation function can be tricky, and the one I described misses some obvious details.
Another thing to try is to use a genetic algorithm and neural networks to evolve the board evaluation function. Now the idea is to feed board positions into neural networks, which do the board evaluations, and let them play according to the technique I described above, tournament style. Then, after tournament rounds, new neural networks are created (through genetic algorithm) from the winners and losers are eliminated. The board evaluation function evolves naturally.

Dot Game and Dynamic Programming

I'm trying to solve a variant of the dot game with dynamic programming.
The regular dot game is played with a line of dots. Each player takes either one or two dots at their respective end of the line and the person who is left with no dots to take wins.
In this version of the game, each dot has a different value. Each player takes alternate turns and takes either dot at either end of the line. I want to come up with a way to use dynamic programming to find the max amount that the first player is guaranteed to win.
I'm having problems grasping my head around this and trying to write a recurrence for the solution. Any help is appreciated, thanks!
Take a look at this site: http://people.csail.mit.edu/bdean/6.046/dp/, especially problem number 10:
Optimal Strategy for a Game. Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
It's exactly what you want if I'm reading your post right. The solution is pretty simple and it's explained very well there in my opinion.

What algorithm would you use to solve a very large tic-tac-toe game?

A small (3x3, 4x4) tic-tac-toe can be easily solved by considering all the cases. But for example, you have a 30x30 tic-tac-toe. What algorithm would you use to decide the next best move in that case?
Minimax + alpha-beta pruning is one way that I know.
Is there some other way that is more efficient/not more efficient but cooler?
I know it would not be a very interesting game to play. I said 30x30 just to ask what I wanted to i.e. which algorithms work best at these sort of games where the number of cases to consider for a perfect solution is very very high and thus not feasible.
I don't think this is probably a very fruitful problem. Reason being:
If the number of marks in a row you need to win is high, the game will (it seems to me) be drawn at any reasonable level of skill, because it's much easier to prevent a possible victory than to achieve one yourself. For example, if you need 20-in-a-row to win on a 30x30 board, all you need to prevent victory is a mark on each row and column roughly near the middle of the board, and a mark near the middle of each long diagonal.
If the number of marks in a row you need to win is low, I suspect that the extra space on the board isn't going to make much of a difference in strategy, and the only sensible strategy for the second player to defend will involve playing near your opponent. As a result, some kind of alpha-beta method is fine.
For the asian game of Go, which is difficult for computers for the same reasons that are troubling you for 30x30 tic-tac-toe (note that I am not saying that 30x30 tic-tac-toe is as difficult as Go and that more direct techniques do not apply), the Monte Carlo tree search has given good results recently.
Take a look at Gomoku or Five in a row. There are a number of general strategies on the web. The wikipedia article also has a good paper on threat based search with gomoku that you might look at.
You can use Rule-based system
Rules are faster then any tree search algorithms and can be mixed with them.
You can create rules by yourself or use (for example) a Genetic algorithm
Wouldn't it be alright to use a greedy algorithm that searches the neighboring space of the last move and tries to put down a block in any empty space inline with an adjacent opponent piece? As long as the player can't win, you sort of do win.
Alpha Beta is absolutely the best thing you can use. Importance in Alpha beta is in its evaluation function. Which not return only 1/0/-1 (win/nothing/lost) (from one player point of view) but also qualty of position.
Check this article (he uses tic-tac-toe but mostly chess as example game)
http://www.fierz.ch/strategy1.htm
Place the first token on row 3 column 3. If the opponent places his token on row 3, place the next token on row 2, column 3, otherwise on row 3, column 2. Your should be able to figure out the next (winning) move.
If the opponent starts, choose an empty 4x4 block and start in the middle like outlined above. If the opponent completes his triple before you, you lose.
I would dare to say, that this is an optimal strategy for 4x4 boards and above.

Resources