The chain shot challenge

[RobbeK]

Hi,

Coding something for the kids of the kids --
I already wrote the interface ,   the question is can we develop something that beats the human.

Kind of puzzle game :
Clicking stones of a certain colour, removes all the connected of the same colour (left, right, up , down connected).
The game has to be finished with as less as possible stones.
Clicking a not-connected square does not work (that would be too easy).

So, C , C++ , Basic ...  etc ... hackers , if interested ..  can we set up a bot competition ?

attached, a program that explains it all  -- do some left mouse-clicks -- but does not play itself (thinking about how to do it).
Graphics are still simple, but easy to change into sprites with sound etc ...   (that's the easy thing)

Anyone interested ??


best Rob
(doing it in NewLISP for the moment,   scripting , works fast and easy )

as usual ...   use USE THIS TO START ....   to remove the evil Java task after exit
..  again gives the same grid ,     ... new    a new random one.

the slightly difficult part of this code was :


(define (remove-blocks x y matchb)
  (if (!= matchb (board x y)) true
    (begin (setf (board x y) leeg)
       (remove-blocks (+ 1 x) y matchb)
       (remove-blocks x (+ 1 y) matchb)
       (remove-blocks (- x 1) y matchb)
       (remove-blocks x (- y 1) matchb))))

Quadruple recursion   

 

.

[JRS]

I would give it a shot if you post the TinyScheme code for it. (functions and value output) I will add the container (IUP) and canvas (SDL_gfx) with the data you provide.

Thanks Rob!

[Mike Lobanovsky]

Hi Rob,

Thanks, I was always fascinated by this particular game, kids or no kids.

Exactly what do you mean by "something that beats the human"? This game is all about a human vs. random number generator. The better the generator, the fewer chances for the human to clear the entire window. You can find the optimum strategy algo for the bot but it wouldn't guarantee the epic win either.

[JRS]

For those that want to play the game rather the write it, Klickety (SameGame) alternative.

Note: Installed from Ubuntu software center.



.

[RobbeK]

Hi ,

@ John, wouldn't it be better I rewrite it in Basic ?  (this way I can try the SB)
  (ps , Scheme does not have arrays (which I used here) but of course it can be done with vectors)
@ Mike :
  yes, play a puzzle and then the code tries to do it better ( I don't think it can be calculated to the end/bottom like some other games (well , it can -- be it will take too long )  , but I have some patterns in mind -- it should be unbeatable ..
if you like the game , I compiled it now with the Austin Kyoto CL , and made it variadic  (but limited here to max 20x20 and max 7 colours - as a joke one colour is included too   

best Rob   


.

[JRS]

John, wouldn't it be better I rewrite it in Basic ?  (this way I can try the SB)
  (ps , Scheme does not have arrays (which I used here) but of course it can be done with vectors)

Sorry, I misunderstood what you were after. I thought that this was a Lisp based challenge and not a general create a game effort.

The Script BASIC forum (and this one) has many examples of using the language and extension modules. Feel free to use any of those examples to bring you up to speed with SB.

I'm overwhelmed with BASM at the moment so I think I'm going to have to pass.

[Charles Pegge]

Great idea for seeding a game system. I'll give it a go, Rob.

Recursive logic for block of 8 x 8 cells:

Code: [Select]

  function GameLogic(sys i,optional a) as sys
  ===========================================
  '
  sys j,m,x,y
  if not i then exit sub
  x=cell[i].x
  y=cell[i].y
  if not a then
    a=cell[i].a
    if not a then
      exit sub
  end if
  end if
  '
  macro GameLogicAct()
    if cell[j].a=a then
      cell[j].a=0
      cell[i].a=0
      GameLogic j,a 'RECURSE
      m=1
    end if
  end macro
  '
  if x>1 then
    j=i-1
    GameLogicAct() 'LEFT
  end if
  if x<8 then
    j=i+1
    GameLogicAct() 'RIGHT
  end if
  if y>1 then
    j=i-8
    GameLogicAct() 'ABOVE
  end if
  if y<8 then
    j=i+8
    GameLogicAct() 'BELOW
  end if
  return m
  end function





.

[RobbeK]

Great Charles 

With a 10x10 grid and calculating it till the end , the number of "clusters" (those not empty and not single , those that can be removed) varies around 20 for full board.
At best we can expect something as 20! (probably more) posssibilities

that gives :

>
(lambda (n)
 (let ((acc 1))
  (for (i 1 n)
   (setq acc (* acc i))) acc))
 
> (fac 20)
2432902008176640000   

I already tried this algorithm (only one deep) :

from all possibilites take the one that produces the least single blocks (or most clusters) -- but of course it does not eleminate single blocks may be separated in a way they never will make contact with a "friend" -- so worthless to build any recursion/iteration on it ....
Thinking about a "brute force" method from a certain number of blocks (short processing time) and something Monte Carlo like.

best, Rob

[RobbeK]

Hi John,

I was just curious to see such problems solved in languages as basic/C/Fortran/Pascal etc ...

best Rob

[RobbeK]

Addendum for Charles,

Looking at your code , a trick (i use) is setting up a 10x10 grid (for your 8x8) where the borders are empty (zero) - in case of calculation (as there is no calculation on empty squares ) the algorithms   for exam. left right up down do not to be tested if on a border (pos 1 or 8  )   the neighbour is just an empty space    ( less calculations )

best Rob

(define (remove-blocks x y matchb)
  (if (!= matchb (board x y)) true
    (begin (setf (board x y) leeg)
       (remove-blocks (+ 1 x) y matchb)
       (remove-blocks x (+ 1 y) matchb)
       (remove-blocks (- x 1) y matchb)
       (remove-blocks x (- y 1) matchb))))       ;;   does not need any limit test --  full variadic !!!!  -- works on any grid of any size


ah yes, leeg means empty in my language (Flemish ; leer in German) , it means empty but that word is already in use by NewLISP , the true is just a void output, it has no meaning or use here

[Mike Lobanovsky]

2432902008176640000   

Hehe Rob,

In fact, I was waiting for you to come to that conclusion yourself in relation to your projected bot strategy. I presume both you and Charles do see the basic difference between what it means to find out which squares/balls to remove in response to the user click and to predict where to actually click in order to be able to ultimately remove all the balls in the window?

That's essentially very close to trying to pre-calculate the best strategy for all possible positions of chessmen on the chess board for the ultimate chess player program. They say they've been calculating it for over two decades already on the world's most powerful mainframe clusters but they have done it only for some 10 or 11 moves following the initial e2-e4 so far.

There's an Oriental parable about Nasreddin Hodja, his ass, and the amir:

Once Nasreddin had a bet with the amir that he could teach his ass to speak human language if the amir would give him a purse of 1,000 gold pieces. Overwhelmed with grief, Hodja's wife cried "Why did you do that? You're going to have your head chopped off!" "Stop that awful noise, woman," said Nasreddin. "I bargained for a term of 20 years. So, before the time comes, either the ass will be dead, or the amir, or I."

Still wanting to create the ultimate chain shot bot algorithm, Rob?

[Charles Pegge]

Not trying to compete with DeepBlue here

---

After recursively taking out the matching cells, the next task is compaction:

Vertical compaction:

Code: Text

1.   sub compact()
2.   ==============
3.   sys i,j,k,w,x,y
4.   for x=1 to 8
5.     i=56+x
6.     j=i
7.     k=j-8
8.     for y=8 to 2 step -1
9.       if cell[j].a then
10.         j-=8
11.       elseif cell[k].a then
12.         transfer cell[j],cell[k]
13.         j-=8
14.       end if
15.       k-=8
16.     next
17.   next
18.   end sub
19.  

I wonder if horizontal compaction would be desirable too? Maybe restricted to removing empty columns.




.

[RobbeK]

Hi Mike,

"Still wanting to create the ...  "  yep , or better, something that comes close.
Those 4x4 magic squares give 20922789888000 possibilites, it's a question of filtering/elemination --  iirc on your PC it took around 30 sec completely solving it .  But in this case it's much more difficult to filter out suspect positions.

In the mean time the best chess engines are over 3000 ELO -  Carlsen (the World Champ) has 2870 (?) are so - the highest ranking ever (more than Kasparov ever had).
But there's a kind of sadness on this computer chess -- unless it's in their opening book , no one of those engines will ever decide to play openings as the Kings gambit , the Latvian gambit , the Philidor defence etc ... the first two risky with an uncertain outcome , the latter not very active -- a human may have certain reasons to play such - Fischer, Spaski, Bronstein sometimes played the King's gambit, not for its strength but for the psychology behind it.
 
For endgames computers these days use Nalimov table bases (which produce the exact results) -- but have a look  --   for only 6 pieces on the board :
https://chessprogramming.wikispaces.com/Nalimov+Tablebases

As for these chess engines, there were some scandals previous years :  Rybka being based on the french chess engine "fruit" - the world champion computer chess -> stripped of all its official titles now ....   etc       

very interesting to read --    :   (Russian chess engines, not allowed to play in any competition ) ...

https://ivanhoe.wikispaces.com/

best Rob

[RobbeK]

Hi Charles,

I remove the empty columns  -- shifting to the left so they make contact again.
My code plays the game now , but not perfect -- but already sometimes it ends with an empty board  (2 from 10 tested).
(not yet good enough)


best Rob

(ok , i added the AI thing - use the button with the |     °(-_-)°       | , in the second frame.  (some tasks are uncoupled now , and the terminal window gives some information in manual mode (needed for statistics)   )

it's far from good, but a start  (and the interface removed from some tasks for the moment)
-- forgot to mention this one and previous runs in interpreted mode (nothing is compiled for the moment).


.

[Charles Pegge]

Hi Rob,

A strategic choice of compaction enhances the game:

left-click:   chainshot with vertical compaction
right-click: chainshot with horizontal compaction



16 x 16 cells

.