AI Contest - Minesweeper

This is a discussion on AI Contest - Minesweeper within the Contests Board forums, part of the Community Boards category; Um, I just thought... rand() uses an extremely reversible algorithm (linear congruential). All your mine-generation algorithms use rand() in some ...

  1. #16
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Um, I just thought...

    rand() uses an extremely reversible algorithm (linear congruential). All your mine-generation algorithms use rand() in some way, including the STL shuffle functions methinks. I *could* reverse the generation and discover your mines, without breaking any of the above rules, no?
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    Thats what I though but some other players could also be caling rand which might make it more difficult.

  3. #18
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    jafet, why are you giving the secret away? Quantum1024, why would they be running at the same time?
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  4. #19
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by Rashakil Fol
    jafet, why are you giving the secret away? Quantum1024, why would they be running at the same time?
    They will all be running "at the same time" ...well in the same loop and all 1000 loops are in same program without reseeding. Which means although you might can figure out the first iteration(more on that) it will be increasingly difficult to figure out later iterations.

    For you to figure out the first iteration, you'd have to know the seed, which for the actual test I probably would use a high resolution timer (milliseconds), then you'd have to know how my compiler implements rand() and seed(). Then you 'd have to recreate any rand() calls up to the point that I placed/shuffled the bombs which for the first iteration you won't have to take into account any other players calls to rand().

    there is one rule that I didn't mention because I am dual hosting this contest here and at cpp-home their contest FAQ states no globals/statics member variables and though I didn't mention it before I will now, because given the slim chance you did figure out the seed you won't be able to pass it to later iterations of your program.
    Last edited by Darryl; 04-08-2006 at 03:05 PM.

  5. #20
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    ...and remember how reputable computer scientists said breaking ciphers by timing hardware ticks was a big stupid waste of time?

    I'm not saying that it's practical, just theoretically possible.
    Last edited by jafet; 04-08-2006 at 04:43 PM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    no globals/statics member variables and though I didn't mention it before I will now, because given the slim chance you did figure out the seed you won't be able to pass it to later iterations of your program.
    I wonder if one can squeeze a singleton past the "no globals/statics" rule.

    ...and remember how reputable computer scientists said breaking ciphers by timing hardware ticks was a big stupid waste of time?
    Well, unless we are dealing with smartcards (or *cough* minesweeper games), things like network latency would make it "a big stupid waste of time".
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Even death may die... Dante Shamest's Avatar
    Join Date
    Apr 2003
    Location
    Malaysia
    Posts
    970
    Quote Originally Posted by laserlight
    I wonder if one can squeeze a singleton past the "no globals/statics" rule.
    I'm curious to know how you'd implement a singleton without them.

  8. #23
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Could I allocate a memory block off the heap and *forget* to return it? And pray hard it doesn't get written over...
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  9. #24
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Hmm, I need to check this board more often...
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #25
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    What ever happened to the spirit of good sportsmanship? I've noticed in every contest I host, someone is looking for loop-holes in the rules.

    The bottom line is that this is a contest to create an algorithm to play minesweeper and not a contest of who can get the highest score. Score is just a tool for judging your algorithm. Therefore a highscore in absence of a good algorithm sounds like a non-entry to me.

  11. #26
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Ok, ok, don't get stuffy over it, I'm not really gonna send you cheat entries!
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    I'm curious to know how you'd implement a singleton without them.
    That's the problem, one may have to twist namespaces to say that it isnt really a global.

    What ever happened to the spirit of good sportsmanship? I've noticed in every contest I host, someone is looking for loop-holes in the rules.
    Well, isnt creative thinking an objective of programming challenges?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Even death may die... Dante Shamest's Avatar
    Join Date
    Apr 2003
    Location
    Malaysia
    Posts
    970
    Quote Originally Posted by laserlight
    That's the problem, one may have to twist namespaces to say that it isnt really a global.
    Does this namespace twisting still use any static members though?
    Last edited by Dante Shamest; 04-11-2006 at 02:39 AM.

  14. #29
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,749
    Does this namespace twisting still use any static members though?
    Using a namespace to try and circumvent the restriction on globals is different from circumventing the restriction on statics. Of course, much much creative thinking is needed is dependent on the restrictions

    I suspect one of those singleton implementations designed to be threadsafe could be used, but I havent looked into them too closely.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #30
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by laserlight
    That's the problem, one may have to twist namespaces to say that it isnt really a global.


    Well, isnt creative thinking an objective of programming challenges?
    Sure, creatively think of a good algorithm :-0

    Look I'm am not trying to sound stuffy, and I have created programs that did figure out rand() in a contests and if you could do the same with mine, I'd certainly be interested (but not as your entry). That said, I think an easier approach would be to search programs heap space for the vector that stores the grid.

Page 2 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Action Game - AI Contest
    By Queatrix in forum Contests Board
    Replies: 4
    Last Post: 01-18-2007, 05:55 PM
  2. New AI contest: sign up
    By Sang-drax in forum Contests Board
    Replies: 20
    Last Post: 07-27-2005, 05:54 PM
  3. chess ai contest
    By Raven Arkadon in forum Contests Board
    Replies: 7
    Last Post: 07-09-2005, 06:38 AM
  4. AI Contest Proposal
    By MadCow257 in forum Contests Board
    Replies: 4
    Last Post: 03-13-2005, 02:27 PM
  5. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 10:35 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21