MTG Engine compare

[frwololo]

If I understand it correctly, one way would be to have an evaluation function that would assign a number to a game state, and then lookahead that tries to maximize that number. Two basic problems are how to construct the function, and how to search the state space in game with incomplete information and random moves like shuffling.

The issue is not "how to search the state space in game with incomplete information and random moves like shuffling.". Technically, the AI could cheat since the "random" effect of shuffling is actually pseudo random and can be foreseen by the computer. The same goes for incomplete information.
But even assuming you take those into accounts (if you don't want the AI to "cheat"), the current major issue for a game such as magic is computing power. I haven't followed deckbot in a while, but last time I checked it was quite slow on a powerful computer. The AI was quite good though, so I'm guessing computing power is just an issue for me and my "333MHz + 20MB Ram" system

[Marek14]

If I understand it correctly, one way would be to have an evaluation function that would assign a number to a game state, and then lookahead that tries to maximize that number. Two basic problems are how to construct the function, and how to search the state space in game with incomplete information and random moves like shuffling.

The issue is not "how to search the state space in game with incomplete information and random moves like shuffling.". Technically, the AI could cheat since the "random" effect of shuffling is actually pseudo random and can be foreseen by the computer. The same goes for incomplete information.
But even assuming you take those into accounts (if you don't want the AI to "cheat"), the current major issue for a game such as magic is computing power. I haven't followed deckbot in a while, but last time I checked it was quite slow on a powerful computer. The AI was quite good though, so I'm guessing computing power is just an issue for me and my "333MHz + 20MB Ram" system

Recently, I reduced the thinking time on Botarena to a minimum (15 seconds) to get it to play faster. It still doesn't play too badly.

[FranAvalon]

Deckbot demands a lot of CPU power. In theory, as more powerfull cpu, better results will be optained and the AI will play better. Of course, you can you offset the power of the CPU for more processing time, but when you reaches more than 1 min of thinking time, that can be annoing.

... and IMHO your system is a bit slow

[nantuko84]

btw, in real life a player continue thinking on opponent's turn

[FranAvalon]

But for AI, the scenario changes every time that the player plays a land/spell/activates an ability. Some are small changes, but other are drastic ones, and all calculus done by AI before the big change is useless

[frwololo]

... and IMHO your system is a bit slow

Yeah, hopefully the next generations of portable game devices will have much more power

[FranAvalon]

I think so too

[telengard]

But for AI, the scenario changes every time that the player plays a land/spell/activates an ability. Some are small changes, but other are drastic ones, and all calculus done by AI before the big change is useless

Any background AI evaluation should be useful to some degree unless the action chosen hasn't been evaluated yet (in which case it's the same as not have done the background eval). There are exceptions though which I can see happening.

I plan on using background AI evaluation (to only a few plys) for ordering actions for optimal pruning. We'll see how well that works.

~telengard

[silly freak]

i think wizards has done a great job with Duels of the Playneswalkers - at least with the article talking about the background. They actually do AI asynchronously with an undo system, and synchronize every time the human player does a move (or ply if you prefer).

this looks like a great concept to me, it's the one i'm also following. you might like to look at my blog^^

@marek, about intelligence being a "special effect":

this is a great topic, and I like the analogy with turing machines (machines able to do any computation) and Conway's game of life (GoL). GoL is a cellular automaton with a rectangular grid where succeeding generations are calculated from the former ones, so it's fully predictable. However, with a grid big enough and the right pattern, it's possible to create a turing machine, so why not AI? Imagine this gigantic grid of cells "thinking" about its creator... YOU!

honestly, i think "artificial" doesn't fit. i don't think the brain is more "naturally" intelligent that anything we can build. intelligence is a property that can be achieved regardless of the medium, just like turing completeness*

*this is not a wikipedia link or something but a genious web comic

[Marek14]

i think wizards has done a great job with Duels of the Playneswalkers - at least with the article talking about the background. They actually do AI asynchronously with an undo system, and synchronize every time the human player does a move (or ply if you prefer).

this looks like a great concept to me, it's the one i'm also following. you might like to look at my blog^^

@marek, about intelligence being a "special effect":

this is a great topic, and I like the analogy with turing machines (machines able to do any computation) and Conway's game of life (GoL). GoL is a cellular automaton with a rectangular grid where succeeding generations are calculated from the former ones, so it's fully predictable. However, with a grid big enough and the right pattern, it's possible to create a turing machine, so why not AI? Imagine this gigantic grid of cells "thinking" about its creator... YOU!

honestly, i think "artificial" doesn't fit. i don't think the brain is more "naturally" intelligent that anything we can build. intelligence is a property that can be achieved regardless of the medium, just like turing completeness*

*this is not a wikipedia link or something but a genious web comic

The fun thing about Game of Life is that it is deterministic, but NOT predictable!

There is no general algorithm that can tell you the future state of arbitrary configuration - except for playing the game and finding out!

As for AI, think of it like this:

It took about 1-2 billion years before life appeared on this planet.
It took about 4.5 billion years before intelligence appeared.

The first computer was built less than one hundred years ago.
We already have artificial life programs, albeit primitive - but it took much less than one billion years.

Life has a tremendous head start, so it's not really fair holding things that were not achieved by computers yet against them We'll get there, eventually.

[frwololo]

However computer programs are always built for a purpose, which is not the case of living beings. We yet have to see a computer doing something because it's fun, or beautiful. Or because it's pissed:

The day you see an AI opponent, out of rage, throws its pint of beer at your face because you deckmilled it for the hundredth time, we can talk about intelligence.
but this will never happen because there is no industrial application for a machine with feelings, so close to no research on the subject is done.

[Chris H.]

If only Forge's AI was this tough and mean.

[Huggybaby]

Don't confuse emotion and intelligence. I think it's easier to simulate emotion than intelligence, and that mirrors real life too. Emotion comes from the primitive part of the brain.

[Marek14]

Don't confuse emotion and intelligence. I think it's easier to simulate emotion than intelligence, and that mirrors real life too. Emotion comes from the primitive part of the brain.

Exactly. There are two basic ways of achieving AI.

First is simulation - you know the inputs and outputs of real intelligence, and you try to make a machine which will give the same outputs to the same inputs. You don't care if the internal organization of machine is the same as the internal organization of intelligence.

Second way is emulation - you emulate the basic processes in brain, and hope that you get something which will behave in an intelligent way.

The first way has historically failed because it turns out you'd need an ENORMOUS amount of rules. The second way, on the other hand, requires an enormous computational capacity, but it's much easier to program - you only need low-level units, which is comparatively easy, and you trust the laws of emergence and complexity to do the rest.

The problem with emotions is that right now normal people want computer to do what they tell it to do. But who knows - in ten years, you might have, next to your mouse, an USB-connected piece of fur you can stroke when the computer does something you like, and make it purr

Personally, I think that the emotionless machines of the sci-fi are terrible PR. Can you imagine that one hundred years from now, robots might campaign to ban Terminator movies for supporting racism?

[mtgrares]

AI is just an illusion like special effects in a movie. AIs are very fragile.