Can A Machine Think?

[armjan]

ok, we need our top phd ppl on this,

 

rules of game...

10 pencils,

u r playing against an algorithm named Larry

u can remove 1,2 or 3 pencils at each move

last one left with a pencil loses, that simple!

 

play quick game with Larry

 

curious to c how many of u find a hack and exploit it.

 

hint 1: don't be too greedy

hint 2: what goes around, comes around

hint 3: Larry is as good as u allow him to be

Edited April 10, 2005 by armjan

[vava]

Why does Larry always forfeit?

[armjan]

Why does Larry always forfeit?

style_images/master/snapback.png

u'r good.

u'r really good.

larry only quits if he knows that u will win.

it will be clear after the first move who the winner is, and so there is no point to continue; thus he quits.

and there is only one way for him to lose.

 

this version of larry is not equiped with a machine learning alg, and for this problem, it won't matter. So he is really dumb b/c once u found a hack, u can continue to exploit it.

Edited April 10, 2005 by armjan

[Azat]

this really has nothing to do with AI... But yes machines for sure can think

[DominO123]

u'r good.

u'r really good.

larry only quits if he knows that u will win.

it will be clear after the first move who the winner is, and so there is no point to continue; thus he quits.

and there is only one way for him to lose.

 

this version of larry is not equiped with a machine learning alg, and for this problem, it won't matter. So he is really dumb b/c once u found a hack, u can continue to exploit it.

style_images/master/snapback.png

 

True, now can you tell why? Mathematcally speaking?

Edited April 11, 2005 by QueBeceR

[armjan]

True, now can you tell why? Mathematcally speaking?

style_images/master/snapback.png

tell what?

[DominO123]

tell what?

style_images/master/snapback.png

 

Why there is one way?

[armjan]

Why there is one way? 

style_images/master/snapback.png

for the sake of completeness, Larry is a version of a math game called

nim.

 

this is a very old problem that has been studied extensively.

 

hand waivy proof for Larry:

can be played with any # of objts, so let's work our way up and u will notice a pattern.

 

let n=# of objts

trivial case:

n=2,3, or 4

easy. take all but one and u win since larry left w/ 1.

 

n=5

if i take 1, 4 left, larry takes 3 =>Loss

if i take 2, 3 left, larry takes 2 =>Loss

if i take 3, 2 left, larry takes 1 =>Loss

so i am hosed either way. i'll come back to this.

any player reduced to this sad state will lose.

 

n=6

if i take 1, 5 left, which by above means larry losses

if i take 2, 4 left, larry takes 3 =>Loss

if i take 3, 3 left, larry takes 2 =>Loss

 

 

n=7

if i take 1, 6 left, larry takes 1 =>5 left, Loss, c above.

if i take 2, 5 left, larry losses.

if i take 3, 4 left, larry takes 3 =>Loss

 

n=8

if i take 1, 7 left, larry takes 2 =>Loss

if i take 2, 6 left, larry takes 1=>Loss

if i take 3, 5 left, larry losses

 

 

n= 9

if i take 1, 8 left, larry takes 3=>Loss

if i take 2, 7 left, larry takes 2=>Loss

if i take 3, 6 left, larry takes 1=>Loss

 

 

n=10

if i take 1, 9 left, larry losses

if i take 2, 8 left, larry takes 3=>Loss

if i take 3, 7 left, larry takes 2=>Loss

only way to win is to take 1, leaving larry with 9 which shown above to be loss.

 

here is what we can take to the bank...

in a sequence of natural #'s, every fourth number ie(1,5,9,...is a losing state).

 

 

Charles Bouton stated a rigorous soln to NIM in general.

the spirit of the proof was something to the order of the following...

 

-express the number of objects in each pile in binary form

-add the coefficients of the powers of 2.

-then remove as many objs from a pile to leave sum of the coefficients of each power of 2 an even number

-when opponent draws, they r bound to upset such an arrangement

-must not leave an even number of piles containing one coin each.

Edited April 11, 2005 by armjan

[armjan]

this really has nothing to do with AI...  But yes machines for sure can think

style_images/master/snapback.png

 

i got this problem from...

a cognitive sciences research dept in AI.

 

Larry, version of NIM, relates to game theory and so naturally, yes, game theory has to do with AI.

some instructors choose to focus on AI from the perspective of search/find heuristics, but it is certainly not limited to that, ie. natural language processing for instance.

 

I would agree that machines do what u tell them or the side-effects resulting but not more.

Edited April 11, 2005 by armjan

[Nakharar]

I knew this was flawed.

[Sip]

Pretty easy but cool problem this NIM ... yah the game is over as soon as a player gets to a number of the form '4n+1' where n is a non negative integer. When your opponent gets to a '4n+1' type number, you just keep bringing her down using 4s .. If she subtracts x, you subtract 4-x and continue until she is left with 1.

 

Solution:

--------------

1. Starting value is a 4n+1 number - Starting player loses.

2. Starting value is a 4n+2 number - Starting player must do -1.

3. Starting value is a 4n+3 number - Starting player must do -2.

4. Starting value is a 4n+4 number - Starting player must do -3.

 

In 2, 3, and 4, any other move and it's a guaranteed loss for the starting player.

 

Also note that 4n+5 just repeats since we can substitute n with n+1 and do the above. Problem solved.

[Harut]

we used to play this game back in armenian 20 yrs ago with matchsticks...

[ExtraHye]

we used to play this game back in armenian 20 yrs ago with matchsticks...

style_images/master/snapback.png

You played this game when you were 2?