Yurik changed the topic of #ocaml to: http://icfpcontest.cse.ogi.edu/ -- OCaml wins | http://www.ocaml.org/ | http://caml.inria.fr/oreilly-book/ | http://icfp2002.cs.brown.edu/ | SWIG now supports OCaml| Early releases of OCamlBDB and OCamlGettext are available
matkor has quit [Remote closed the connection]
TimFreeman has joined #ocaml
<whee> hooray, new pfc on kuro5hin
<whee> who wants to enter and destroy the millions of C entries there will likely be? :)
<Kinners> beats reading slashdot
<mellum> but C rulz!!!1!
<whee> attempting to think of a good way to internally represent everything at the moment
<mellum> Uhm, am I right in assuming this is the 32768th problem that one would solve with plain old minimax?
<whee> yes, you are
<whee> heh
<mellum> How interesting.
<whee> which is why there'd have to be a little more than just that to win
<mellum> well, then use MTD(f). I've made very good experience with it.
<mellum> I once wrote an implementation in C++, I always wanted to rewrite it in Ocaml to see how they compare in speed
<whee> I've never actually done a minimax or any algorithm like that before :\
<Kinners> look at some of the icfpcontest entries :)
<mellum> Anybody wants to rewrite mine in Ocaml? I pay for a round if it is only two times slower ;)
<whee> heh
<whee> right now I'm working on parsing and still deciding on an internal representation :\
<lament> oh, that's that stupid contest that takes into account the speed of implementations
<whee> yeah :\
<whee> that's always a problem with the pfcs
<whee> except with this one you could be pushing the limits on time and still win if the algorithm is good enough
<mellum> BTW, check http://www.cs.vu.nl/~aske/mtdf.html for the MTD(f) algorithm
TimFreeman has left #ocaml []
<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 };
<mellum> Field** fields_;
<mrvn> With a extra border of blocks?
<mellum> Of course :)
<mrvn> I just used
<mrvn> let read_board width height =
<mrvn> Array.init height (fun _ -> String.sub (read_line ()) 15 width)
<mrvn> The String.sub is to cut away the "04:23 <mellum> " part
<mrvn> I think i will write a little server app that plays two programs against each other according to the given rules and does some stats.
<mellum> Please do :)
<mrvn> But not tonight, time to sleep.
<whee> heh
<whee> I spent all that time watching tv :)
<async> how do you access program arguments?
<Kinners> Sys.argv
<mellum> Heh, my program is already doing pretty well
* whee just started his
<whee> did I mention I hate parsing?
<whee> heh
<Kinners> I'm going pretty slowly, have to keep going back to the ocaml reference manual
<whee> I haven't used ocaml in a while, same here :\
<whee> just looking at scanf now for handling that width/height crap
<whee> so how does scanf work? :)
<Kinners> let read_dimensions _ =
<Kinners> Scanf.scanf "%d %d" (fun w h -> (w,h));;
<whee> ah, it calls a function with the results
<whee> well, got parsing of the board out of the way :\
<whee> File "pfc11.ml", line 1, characters 668-669:
<whee> haha, camlp4 at it again
<mellum> heh, a 10x10 board makes it go pretty slow already
<mellum> It tends to cluster the move. But that seems sensible to do
<whee> hrmf, parsing really doesn't work
<whee> oddd :|
<whee> how are you reading from stdin Kinners?
<Kinners> just input_line
<Kinners> let line = input_line stdin in ...
<whee> really odd.
<whee> mine's actually getting eof afer it tries sto read a line
<whee> heh, bad typing :)
<whee> guess I can do input from the file instead :\
<whee> still doesn't work. what the hell
<whee> http://smaerty.ath.cx/pfc11.ml <- what's wrong with this?
<whee> it's getting eof on the read_line ()
<whee> err, I think I reversed width and height
<mellum> Hehe, I did that too :)
<whee> still doesn't fix the problem
<whee> it does the scanf, goes to parse_line, read_line () gets eof. meh.
<Kinners> try without the \n in scanf?
<whee> tried that
<whee> it should leave on the channel whatever it doesn't eat, and I want it to eat the newline
<whee> but that still doesn't fix it :\
<whee> gah, got it. off by ones :(
<Kinners> ah, I just realised that code is using the alt syntax, I wondered what the value keyword was doing in there :)
<whee> haha
<whee> for some crazy reason it doesn't work right when I pipe the file
<Kinners> mine appears to work, I'll put it up
<whee> I think it's being buffered and the program exits before it parses or something
<whee> this is really zany.
<Kinners> what about the w-1, h-1, is your array to small?
<whee> your code is nicer too :\
<Kinners> it's had makeup applied a few times :)
<whee> hrrrrrrrrfmm
<whee> if I type in the board, it works. using cat or < it just hits eof
<whee> heh
<Kinners> on linux?
<whee> no
<Kinners> win32?
<whee> OS X
<Kinners> ah
<Kinners> I'm in qnx
<Kinners> ack, I had the rows/columns switched too :)
<whee> hah
<whee> this is crazy
<whee> I can't even use open_in and have it read the thing
<whee> it only works if I use stdin and type it
<Kinners> it's not some line ending problem?
<whee> don't see how it could be
<whee> looks fine to me :\
<whee> lemme try this on linux
<whee> nope, same exact behavior
<whee> wait, yours doesn't work either
<whee> heh
<Kinners> can you put yours up again?
<whee> running it and typing the board works, cat board | ./pfc11 and ./pfc11 < board don't.
<whee> same behavior on the one you posted
<mellum> Wow, all in color!
<whee> both in OS X and gentoo
<whee> does yours work with pipes?
<whee> (on your machine)
<Kinners> whee: with cat << EOF | ./pfc11, cat test | ./pfc11 and ./pfc11 < test
<whee> yours works?
<whee> er
<Kinners> yours works on my machine
<whee> blah, I bet it's a bug in cvs ocaml.
<Kinners> I'm using plain old 3.06 (with slight changes for qnx)
<whee> :\
<mellum> Well, I've posted my entry now...
<mellum> maybe that will stop me from wasting more time with this :)
Yurik has joined #ocaml
<Yurik> re
Yurik has quit [Read error: 104 (Connection reset by peer)]
Kinners has left #ocaml []
Yurik has joined #ocaml
<Yurik> re
Yurik has quit [Read error: 104 (Connection reset by peer)]
redcrosse has quit ["tootles"]
Yurik has joined #ocaml
Yurik has quit [Read error: 54 (Connection reset by peer)]
Yurik has joined #ocaml
Yurik_ has joined #ocaml
Yurik has quit [Read error: 104 (Connection reset by peer)]
Yurik_ has quit [Read error: 104 (Connection reset by peer)]
matkor has joined #ocaml
lament has quit ["Did you know that God's name is ERIS, and that He is a girl?"]
matkor has quit [Read error: 60 (Operation timed out)]
mellum has quit [Read error: 110 (Connection timed out)]
matkor has joined #ocaml
mellum has joined #ocaml
doubleukay has joined #ocaml
doubleukay has quit [Client Quit]
docelic|away has quit ["Client Exiting"]
docelic has joined #ocaml
docelic has quit [Remote closed the connection]
<polin8> has anyone used OSP (ocaml server pages) on unix?
docelic has joined #ocaml
mattam has joined #ocaml
steele has quit [Read error: 54 (Connection reset by peer)]
steele has joined #ocaml
<whee> time to see if I can track down this IO bug in cvs :\
* whee thinks its scanf
merriam has quit [Excess Flood]
merriam has joined #ocaml
async has quit ["Lost terminal"]
mattam_ has joined #ocaml
mattam has quit [Read error: 110 (Connection timed out)]
<iusris> join #python
* iusris laughs
mrvn_ has joined #ocaml
matkor has quit ["Client Exiting"]
matkor has joined #ocaml
mrvn has quit [Read error: 60 (Operation timed out)]
rox has joined #ocaml
mattam_ is now known as mattam
__mattam__ has joined #ocaml
mattam has quit [Read error: 54 (Connection reset by peer)]
rox is now known as rox|beworben
lament has joined #ocaml
matkor has quit [Remote closed the connection]
lament has quit ["Did you know that God's name is ERIS, and that He is a girl?"]
lament has joined #ocaml
Kinners has joined #ocaml