<whee>
bah. wish the input didn't include the size of the board
<whee>
not that it matters, it's just useless :)
lament has quit ["Did you know that God's name is ERIS, and that He is a girl?"]
<mellum>
Oh well, I'm kinda bored. I think I'll give this game a try, too
<whee>
I'm going to go with a haskell implementation now that I think about it
<whee>
I just feel more comfortable there at the moment :|
<whee>
plus that turns the whole parsing routine into two lines, which I like :)
<mellum>
"You may assume fewer than 1000 rows, and fewer than 1000 columns." Wow, now that is extremely helpful
<whee>
heh
<whee>
I think the idea behind that was to let people know there's no real limit on board size
<whee>
how well would your algorithm scale in that case?
<mellum>
Well, it has a hash table of positions
<mellum>
One can cheat there, though, and use only a hash of the board as key
<mellum>
With a small probability, you're looking up the wrong board, then, but with a good hahs function, that is unlikely
<whee>
oh, well that sucks
<whee>
hard to do a quick check on available positions using a list of lists :)
<mellum>
Well, that's what your get for using a pure functional language ;)
<whee>
:p
<whee>
haskell has arrays, but I've never actually used them :\
* whee
has an idea
<whee>
nevermind, wouldn't work anyway :\
<mellum>
Well, that's what your get for using a pure functional language ;)
<whee>
:P
<whee>
bleh, guess I'll use ocaml :)
<whee>
probably would be easier
<whee>
except the parsing part; I hate parsing with ocaml :\
<async>
is there a site with lots of ocaml snippets?
<whee>
there's a bit on ocaml.org
<async>
yeah and theres always sourceforge
mattam has joined #ocaml
<mrvn>
Is there a winning strategy for the game? Anyone know?
<whee>
I'd imagine you'd want your own pieces in the corners and edges first
<mrvn>
Why?
<whee>
places where you don't limit the amount of open spaces you get
<whee>
putting a piece dead center removes four spots for you, while a corner removes two
<mrvn>
Oh, it must be directly adjacent, not just the same row.
<mrvn>
In the middle of 4 + would be best. :)
<mrvn>
20 seconds for a move could be hard, esspecially at the start
<whee>
well ideally you'd keep track of how long you've taken while computing
<whee>
and then if time's up, just spit out the best one so far
<mrvn>
of cause.
<mrvn>
code size doesn't seem to matter, right?
<Kinners>
and you can store info between moves
<whee>
no
<whee>
Kinners: another reason I think there's a better chance of an ocaml one winning
<whee>
really easy to marshal a structure compared to a C program
<Kinners>
yeah
<mrvn>
whee: mmap(fd, addr, size);
<mrvn>
whee: Whats there to marshal?
<whee>
things!
<whee>
heh
<mrvn>
Its not like you have to make it compatible to different cpus or code versions
<mrvn>
And with mmap you save yourself the marshaling and unmarschaling
<mrvn>
I think on Alpha or esspecially sparc you would realy loose with ocaml. The compiler (or the non existence of a compiler) slows you down.
<Kinners>
if you wanted to store a tree on disk, using mmap you'd have to fix-up the pointers though right?
<mrvn>
Kinners: Nope. you can eigther use ofrfsets into an array (short to save space?) or just pointer. The next time you just mmap it to the same spot and all pointers are valid.
<mrvn>
-r
<mrvn>
Of cause you can't have a pointer pointing out of the mmap.
<Kinners>
right
<Kinners>
writing bug free programs and implementing the right algorithm/s is a very good strategy anyway
<mrvn>
esspecially not using too much time and not too little.
<mrvn>
I wonder if it does any good looking ahead a few steps.
<mrvn>
With a 1000x1000 field you can't look far anyway.
<mrvn>
A move only affects its immidiate neighbourhoud. You could probably precalculate all 5x5 game positions and figure out the best move. Then scann all 5x5 subtiles of the board and do the best move.
<Kinners>
you'd want to look ahead towards the end of the game where there are fewer moves you can make
<whee>
mrvn: that gets further complicated by the + positions
<mrvn>
If you have no place to put your marker its a draw, right?
<whee>
plus remember that this program gets restarted every move, so it'd have to be quick there too
<mrvn>
whee: as I said, just mmap the data structures and they get demand page loaded when needed on the next move.
<Kinners>
4 ** 25 is a big number :)
<mellum>
It would be useful to know what sizes are to be *expected*. Does he really want to feed 1000x1000 boards?
<mrvn>
At least once.
<whee>
I bet he will, to get rid of entries with algorithms that scale horribly
<Kinners>
yep
<mrvn>
to see if it crashes
<mellum>
Well, that will make for a looong game if each move is 8 seconds
<whee>
indeed, heh
<mrvn>
remembering the move for all 5x5 boards would be 640 TB. Thats a bit excessive.
<whee>
just mmap the structure and ;)
<mrvn>
whee: No problem there (on alpha) but sending in the source.
<mrvn>
Hmm, one could generate the data on compile time
<whee>
I wonder how long a game with a board size of 1000*1000 would take
<mrvn>
92 days at most
<whee>
haha
<mrvn>
You need at least 1/9 of the board filled I guess so that would be 10 days minimum
<whee>
I suggest having one of the clients suicide and lose on their second move
<mrvn>
Actually more like 1/5th
<mrvn>
With 1000x1000 just placing a random move thats not suicide is probably outlast the alottet timeframe.
<mellum>
Hmm, even "choose any non immediately losing move" would last long
<mrvn>
Thats what I ment
<Kinners>
maybe he'll make a lot of squares unavailable
<mellum>
That'd be silly.
<mrvn>
If you have a line from one side of the board to the other side thats free of - you practically have two boards of smaller size.
<mrvn>
You could play that like 2 simultanious games
<Kinners>
mellum: sillier than having a game take for ever?
<mellum>
Kinners: No, that's silly, too.
<mrvn>
Should safe a lot of recomputing if you know only one of two parts has changed.
<mellum>
I'll assume reasonably-sized boards
* mellum
uses a goto and laughs manically
<mrvn>
args, read_int realy sucks.
<mellum>
mrvn: You needed some funny native_int thing, or what was the problem?
<mrvn>
I just want to read an int from stdin. read_int reads in one line and tries to convert that to int
<mellum>
Evil.
<mellum>
std::cin >> ysize >> xsize; ;)
<mrvn>
no, ocaml
mattam has quit ["zZz"]
<mrvn>
How do I get a random number in ocaml?
lament has joined #ocaml
<Kinners>
mrvn: Random.int bound or Random.float bound basically
<mrvn>
Is the Random.self_init good under linux?
<Kinners>
no idea
<mellum>
8 seconds is really fucking few. You can barely touch the whole memory once in that time...
<mrvn>
with 1000x1000?
<mellum>
the 1G the testing machine has
<Kinners>
mrvn: it uses gettimeofday or time xor getppid and getpid
<mrvn>
Kinners: should use /dev/random
<mellum>
mrvn: why? time xor getppid and getpid should be uniqe
<mrvn>
you could have a pid wraparound in under a second :)
<Kinners>
mrvn: you could read /dev/random into an int array and use Random.full_init rand_array
Kinners has left #ocaml []
<mrvn>
Unbound value Random.int
<mellum>
full_init?
<mrvn>
Somehow Random doesn want to work
<mrvn>
Works find in the ocaml shell.
<mrvn>
-d
<mellum>
Maybe you need to link the unix lib, or so
<mrvn>
Nope, its a compile error. Not even linking yet.
<mrvn>
Ok, my first solution is done. Work in ht ehsell but doesn't compile.
<mrvn>
the shell even
<mellum>
Whee, mine isn't quite done
<mrvn>
Damn, I think I know why Random.int doesn't work. The file is called random.ml so it looks inside itself.
<mrvn>
./random <start.board
<mellum>
he he
<mrvn>
5 5
<mrvn>
-----
<mrvn>
-----
<mrvn>
-----
<mrvn>
-X---
<mrvn>
-----
<mellum>
Ah, mine works now, too
<mellum>
O----
<mellum>
-----
<mellum>
-----
<mellum>
-X---
<mellum>
-----
<mrvn>
Mine doesn't, it freezes up if it can't win.
<mrvn>
s/win/make a move
<mellum>
That's lame.
<mrvn>
5 5
<mrvn>
XOXOX
<mrvn>
OXOX-
<mrvn>
-O--O
<mrvn>
X-XOX
<mrvn>
OXOXO
<mrvn>
It scans the board from a random position until it finds a place where it can place its marker.
<mellum>
Well, it should be doable to return any move if it can't find something
<mellum>
Wanna play a game against mine? :)
<mrvn>
It would loose.
Kinners has joined #ocaml
<mrvn>
(returning any move)
<mellum>
mrvn: you don't know, mine might have a bug
<mrvn>
Mine now quits with "Fatal error: exception Rand.Loose"
<mrvn>
5 5
<mrvn>
-----
<mrvn>
-----
<mrvn>
-----
<mrvn>
----X
<mrvn>
-----
<mrvn>
ups
<mrvn>
Ha, i just won my first game against mellum. :)
<Kinners>
I just learnt how to use the Scanf module, I've got a bit of catching up to do :)
<mrvn>
I have a dirty read_int function using Nativeint.to_int (Nativeint.of_string s)
<mrvn>
Wie stellst du dein Brett da?
<mrvn>
aehm, how do you represent your board?
<mellum>
enum Field { EMPTY, PLAYER_X, PLAYER_O, BLOCK };