Inclusion Criteria

DISEASE CHARACTERISTICS:

- Histologically proven stage IV melanoma

- Measurable disease

- At least 1 lesion must be a minimum of 1.0 cm in diameter

- Bone metastases are not considered to be measurable disease

- No prior radiotherapy to area of measurable disease unless there is clearly
progressive disease in this site or measurable disease exists outside the area
of prior radiotherapy

- HLA-A2 positive

- No brain disease by MRI or CT scan within 4 weeks prior to randomization

- Prior brain disease allowed if no evidence of active disease by 2 successive MRI
evaluations completed at least 3 months apart

PATIENT CHARACTERISTICS:

Age:

- 18 and over

Performance status:

- ECOG 0-1

Life expectancy:

- Not specified

Hematopoietic:

- WBC at least 4,000/mm^3

- Platelet count at least 100,000/mm^3

- Lymphocyte count greater than 700/mm ^3

Hepatic:

- SGOT no greater than 2 times upper limit of normal (ULN)

- Bilirubin no greater than 2 times ULN

- Alkaline phosphatase and lactic dehydrogenase no greater than 2 times ULN

Renal:

- Creatinine no greater than 1.8 mg/dL

Other:

- No significant detectable infection

- HIV negative

- No other malignancy within the past 5 years except:

- Any carcinoma in situ

- Lobular carcinoma in situ of the breast

- Carcinoma in situ of the cervix

- Atypical melanocytic hyperplasia

- Melanoma in situ

- Basal cell or squamous cell skin cancer

- No autoimmune disorders or conditions of immunosuppression

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception

PRIOR CONCURRENT THERAPY:

Biologic therapy:

- No prior MART-1:27-35, gp100:209-217 (210M), or tyrosinase:368-376 (370D) peptide

- Greater than 4 weeks since prior adjuvant immunotherapy, including sargramostim
(GM-CSF) or interferon alfa-2b

Chemotherapy:

- At least 4 weeks since prior chemotherapy (6 weeks for nitrosoureas or mitomycin)

Endocrine therapy:

- At least 2 weeks since prior and no concurrent systemic corticosteroids, including
oral steroids (i.e., prednisone, dexamethasone); continuous use of topical steroid
creams or ointments; or any inhalers containing steroids

Radiotherapy:

- See Disease Characteristics

- At least 4 weeks since prior radiotherapy for local control or palliation and
recovered

Surgery:

- Recovered from any prior major surgery