LÖVE

Posted: **Wed May 09, 2012 1:47 pm**

Hi,

I'm interested in the AI programming (learning, efficient, fast, intelligent).
I want to understand and write fast and memory saving functions (not 1001 if-statements...).

At the moment, I'm trying to program a little AI for Tic Tac Toe.
I cover the "AI has won/Player has won"-story with 16 ifs (certainly a low solution, but hey, we all began one time.

)

But now to the point...
I haven't enough mathematical and logical thinking (yet) to see a fast method (function) in this game structur (fields and their ID):

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

Facts:
+1 every field horizontally
+4 every field diagonal
+3 every field vertical

Is there a calculation/formula to do a fast AI?

Also, every field has an OWNER property (nil = nobody, 1 = player, 2 = AI), it's possibile to sort them before compare them?
(table.sort? - You know, I and tables, we aren't friends (yet))

Like in MySQL:

Code: Select all

SELECT *(all) WHERE OWNER ~= nil

So you could work only with those, who have an owner?

Or how would you solve my situation? With a totaly other AI?

Greets

Posted: **Wed May 09, 2012 3:05 pm**

I wrote an AI for Tic Tac Toe using minimax in Python: https://gist.github.com/888216#file_tictactoe.py

If you want, I can explain how it works.

Posted: **Wed May 09, 2012 3:11 pm**

one solution might be to use a lookup table:

Code: Select all

-- all possible winning states
lookup = {{1,2,3},
		{4,5,6},
		{7,8,9},
		{1,4,7},
		{2,5,8},
		{3,6,9},
		{1,5,9},
		{3,5,7}}

-- returns nil when there is no winner yet
function getWinner()
	-- lets check each state
	for i, v in ipairs(lookup) do
		if field[v[1]].owner == field[v[2]].owner and field[v[1]].owner == field[v[3]].owner then
			return field[v[1]].owner
		end
	end
end

edit: this is not an AI, this checks whether somebody has won or not, to replace with the 'if' solution

Posted: **Wed May 09, 2012 3:43 pm**

Check for Minimax algorithm, it can be used for AI in a Tic Tac Toe game.
But it'll need some skills to be implemented in Lua, though.

Posted: **Wed May 09, 2012 4:45 pm**

@Robin

Hm, I don't understand much of your code, it's written in a language I don't know.
Could you maybe explain the main function, the logical construction (course of the game)?
Also, is it possible to download/play your game (as *.exe, for Windows anyway)?

@eltain

Thanks for your "check for win" function. Very useful!
Another step to understand tables.

@Roland

Thank you. I'm going to grapple with it.

What do you exactly mean by "skills"? What's the difficulty?

Posted: **Wed May 09, 2012 5:34 pm**

Petunien wrote:
@Roland

Thank you. I'm going to grapple with it.

What do you exactly mean by "skills"? What's the difficulty?

Nothing really specific. The algorithm is easy to get, by itself.
Writing the whole stuff in lua will require a good understanding of the API, tables for example.

Posted: **Wed May 09, 2012 5:35 pm**

Petunien wrote:Hm, I don't understand much of your code, it's written in a language I don't know.
Could you maybe explain the main function, the logical construction (course of the game)?

It starts a game, with a human player named "Human", who uses "X", and a computer player named "James" who uses "O":

Code: Select all

Game(Human('X', "Human"), Heuristic('O', "James")).play()

After that each player goes a turn until the board is full or someone has won:

Code: Select all

while not self.board.winner() and not self.board.full():

When the human has a turn, at first the board is printed, then it will ask for a place to put your sign repeatedly, until you enter a valid place, after that it plays the move:

Code: Select all

def play(self, board):
    print(board)
    i = 0
    while i < 1 or i > 9 or board.get(i - 1):
        i = raw_input(self.name + ": ")
        i = i.isdigit() and int(i) or 0
    board.play(i - 1, self)

For the computer player, it will first try to figure out what the other player is if it doesn't know that yet, and then find the best move:

Code: Select all

def play(self, board):
    if not self.other.name:
        for i in range(9):
            x = board.get(i)
            if x and x != self:
                self.other = x
                break
    board.play(self.findmove(board), self)

In findmove, it will select position 0 (the top left corner) if the board is empty (because the corners are always the best place to start), and otherwise try minimax for each empty spot on the board:

Code: Select all

def findmove(self, board):
    if not any(board.inner): #empty board
        return 0

    for I in range(1, -3, -1): #default to minimax
        for i in range(9):
            if not board.get(i):
                b = board.copy()
                b.play(i, self)
                if self.minimax(b, min) > I:
                    return i

Minimax will first check for an endgame condition: if the current player won, return 1, if the enemy won, return -1, and if there is a draw, return 0:

Code: Select all

def minimax(self, board, f):
    if board.winner():
        return board.winner() == self and 1 or -1
    if board.full():
        return 0

Then we recursively call minimax, and check if we can force a win or are forced a lose, depending on which part of the algorithm we're running right now:

Code: Select all

    m = f == min and 1 or -1
    for p in range(9):
        if not board.get(p):
            b = board.copy()
            b.play(p, f == min and self.other or self)
            m = f(m, self.minimax(b, f == min and max or min))
            if m == (f == min and -1 or 1):
                return m
    return m

That's it!

Petunien wrote:Also, is it possible to download/play your game (as *.exe, for Windows anyway)?

You can download the file, and if you have Python 3, you can run it with that. Open cmd.exe, enter

Code: Select all

cd C:\whereever\you\put\the\file\
python3 tictactoe.py

Posted: **Wed May 09, 2012 6:47 pm**

Ok, thank you both!

But some things remain uncleared.

1) The Minixmax algorithm is something like a library, that I have to include and then I can work with it?
Or is it just a algorithm/function that is different in every language? So I have to write it manually?
Sorry for the bad question, but I really don't know.

2) Robin, you wrote it in Python, is it difficult to "translate" it bzw. write it in Lua/LÖVE?

3) Are all 255,168 (Wikipedia) game-situations covered with Minimax?

4) How does it work with network?
Are there "normal" values like numbers, true/false and so on, that can be sent and further processed to/by another PC as well?

Edit: Yeah, some of the questions sound naive and unnecessary, but I would like to have certainty.

Posted: **Wed May 09, 2012 7:11 pm**

Petunien wrote:Ok, thank you both!

But some things remain uncleared.

1) The Minixmax algorithm is something like a library, that I have to include and then I can work with it?
Or is it just a algorithm/function that is different in every language? So I have to write it manually?
Sorry for the bad question, but I really don't know.

2) Robin, you wrote it in Python, is it difficult to "translate" it bzw. write it in Lua/LÖVE?

3) Are all 255,168 (Wikipedia) game-situations covered with Minimax?

4) How does it work with network?
Are there "normal" values like numbers, true/false and so on, that can be sent and further processed to/by another PC as well?

Questions 1 through 3) Minimax is a simple agorithm, and a algorithm is not language-relevant. Then is possible to do the same thing in Lua.
You have have to understand how works minimax (i found lots of examples of Tic-Tac-Toe sources using Minimax over the Net, just google, also take a closer look at what Robin did) and then write it on your own.
It should be that hard to write...

About Network, that beyond my scope.I guess you will have to setup two clients and a server (using LuaSocket or LuBE)...Setup one game board. And each time one player performs an action, a signal corresponding to that action will be send to the server and update the board drawing on the other client's screen, and vice-versa...

Posted: **Wed May 09, 2012 7:21 pm**

Roland_Yonaba wrote: Questions 1 through 3) Minimax is a simple agorithm, and a algorithm is not language-relevant. Then is possible to do the same thing in Lua.
You have have to understand how works minimax (i found lots of examples of Tic-Tac-Toe sources using Minimax over the Net, just google, also take a closer look at what Robin did) and then write it on your own.
It should be that hard to write...

Ok, thank you. I'll do that.

But it's a good feel, that I could come back with more questions.

(I'm sure.)

Roland_Yonaba wrote: About Network, that beyond my scope.I guess you will have to setup two clients and a server (using LuaSocket or LuBE)...Setup one game board. And each time one player performs an action, a signal corresponding to that action will be send to the server and update the board drawing on the other client's screen, and vice-versa...

Yeah, exactly how I meant it. This would be possible with a few of variables and values. Sounds easy.

LÖVE

Tic Tac Toe - AI (efficient algorithm?)

Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)

Re: Tic Tac Toe - AI (efficient algorithm?)